fork download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5.  
  6. template <typename t>
  7. class minPriorityQueue {
  8.     int size, currentPosition;
  9.     int *position;
  10.     t *data;
  11.     bool (*compare)(t data1, t data2);
  12. public:
  13.  
  14.     minPriorityQueue(int size, bool (*func1)(t data1, t data2), int *position) {
  15.         this->size = size;
  16.         currentPosition = 1;
  17.         data = new t[size];
  18.         compare = func1;
  19.         this->position = position;
  20.     }
  21.  
  22.     void swapPositionValue(int parent, int temp) {
  23.         if (position != NULL) {
  24.             int tempPosition = position[data[parent]];
  25.             position[data[parent]] = position[data[temp]];
  26.             position[data[temp]] = tempPosition;
  27.         }
  28.     }  
  29.  
  30.     void insert(t data) {
  31.         (this->data)[currentPosition] = data;
  32.         if(position != NULL) {
  33.             t temp = data[currentPosition];
  34.             position[temp] = currentPosition;
  35.         }
  36.         heapifyUp();
  37.         currentPosition++;
  38.     }
  39.  
  40.      t & operator [](int k) {
  41.         return data[k];
  42.     }
  43.  
  44.     t minElement() {
  45.         t ans = data[1];
  46.         data[1] = data[--currentPosition];
  47.         position[(data[currentPosition])] = 1;
  48.         this->heapifyDown();
  49.         return ans;
  50.     }
  51.  
  52.     void heapifyDown() {
  53.         int current = 1;
  54.         int leftChild = 2*current, rightChild = leftChild + 1;
  55.         while(leftChild < currentPosition) {
  56.             if(rightChild < currentPosition) {
  57.                 if(compare(data[leftChild], data[current]) && compare(data[rightChild], data[current])) {
  58.                     return;
  59.                 } else if(!compare(data[leftChild], data[rightChild])) {
  60.                     t tempNode = data[leftChild];
  61.                     data[leftChild] = data[current];
  62.                     data[current] = tempNode;
  63.                     current = leftChild;
  64.                     swapPositionValue(current, leftChild);
  65.                 } else {
  66.                     t tempNode = data[rightChild];
  67.                     data[rightChild] = data[current];
  68.                     data[current] = tempNode;
  69.                     current = rightChild;
  70.                     swapPositionValue(current, rightChild);
  71.                 }
  72.             } else {
  73.                 if(compare(data[leftChild], data[current])) {
  74.                     return;
  75.                 } else {
  76.                     t tempNode = data[leftChild];
  77.                     data[leftChild] = data[current];
  78.                     data[current] = tempNode;
  79.                     current = leftChild;
  80.                     swapPositionValue(current, leftChild);
  81.                 }
  82.             }
  83.             leftChild = 2*current;
  84.             rightChild = leftChild + 1;
  85.         }
  86.     }
  87.  
  88.     void heapifyUp() {
  89.         int temp = currentPosition;
  90.         int parent = temp / 2;
  91.         while(parent != 0) {
  92.             if(compare(data[parent], data[temp])) {
  93.                 t tempNode = data[parent];
  94.                 data[parent] = data[temp];
  95.                 data[temp] = tempNode;
  96.                 swapPositionValue(parent, temp);
  97.             } else {
  98.                 break;
  99.             }
  100.             temp = parent;
  101.             parent = parent / 2;
  102.         }
  103.     }
  104.  
  105.     void heapifyUp(int k) {
  106.         int temp = k;
  107.         int parent = temp / 2;
  108.         while(parent != 0) {
  109.             if(compare(data[parent], data[temp])) {
  110.                 t tempNode = data[parent];
  111.                 data[parent] = data[temp];
  112.                 data[temp] = tempNode;
  113.                 swapPositionValue(parent, temp);
  114.             } else {
  115.                 break;
  116.             }
  117.             temp = parent;
  118.             parent = parent / 2;
  119.         }
  120.     }
  121.  
  122.     bool isEmpty() {
  123.         if(currentPosition == 1)
  124.             return true;
  125.         return false;
  126.     }
  127.  
  128.     ~minPriorityQueue() {
  129.         delete [] data;
  130.     }
  131.  
  132. };
  133.  
  134.  
  135.  
  136. class graph{
  137.  
  138. protected:
  139.     class Node {
  140.     public:
  141.         int data;
  142.         int weight;
  143.         Node() {}
  144.         Node(int data) {
  145.             this->data = data;
  146.             this->weight = INT_MAX;
  147.         }
  148.         friend ostream & operator << (ostream & yo, Node d) {
  149.             yo << d.data;
  150.             return yo;
  151.         }
  152.         friend int& operator [](int *a, Node i) {
  153.             return a[i.data];
  154.         }
  155.     };
  156. private:
  157.     bool **a;
  158.     const int numberOfNodes;
  159.  
  160.     static bool compareNode(Node node1, Node node2) {
  161.         if(node1.weight > node2.weight)
  162.             return true;
  163.         return false;
  164.     }
  165.  
  166. public:
  167.  
  168.     graph(int numberOfNodes) : numberOfNodes(numberOfNodes){
  169.         a = new bool *[numberOfNodes];
  170.         for(int i = 0; i < numberOfNodes; i++) {
  171.             a[i] = new bool[numberOfNodes]();
  172.         }
  173.         this->createGraph();
  174.     }
  175.  
  176.     void singleSourceShortestPath(int source) {
  177.         int *parent = new int[numberOfNodes]();
  178.         int *position = new int[numberOfNodes]();
  179.         minPriorityQueue<Node> q(100, &compareNode, position);
  180.  
  181.         Node newNode(source);
  182.         newNode.weight = 0;
  183.         parent[source] = source;
  184.         q.insert(newNode);
  185.  
  186.         for(int i = 0; i < numberOfNodes; i++) {
  187.             if (i != source) {
  188.                 Node newNode(i);
  189.                 parent[i] = -1;
  190.                 q.insert(newNode);
  191.             }
  192.         }
  193.  
  194.         while(!q.isEmpty()) {
  195.             Node temp = q.minElement();
  196.             position[temp.data] = -1;
  197.             for(int i = 0; i < numberOfNodes; i++) {
  198.                 if(a[temp.data][i] && position[i] != -1) {
  199.                     Node changeNode = q[position[i]];
  200.                     if((temp.weight + a[temp.data][i]) < changeNode.weight) {
  201.                         changeNode.weight = temp.weight + a[temp.data][i];
  202.                         q.heapifyUp(position[i]);
  203.                         parent[i] = temp.data;
  204.                     }
  205.                 }
  206.             }
  207.         }
  208.  
  209.         delete [] parent;
  210.         delete [] position;
  211.     }
  212.  
  213.     void createGraph() {
  214.         addEdge(0,2);
  215.         addEdge(1,0);
  216.         addEdge(5,0);
  217.         addEdge(1,5);
  218.         addEdge(3,1);
  219.         addEdge(3,2);
  220.         addEdge(5,4);
  221.         addEdge(4,2);
  222.     }
  223.  
  224.     void addEdge(int start, int end) {
  225.         if(start >= numberOfNodes || start < 0 || end >= numberOfNodes || end < 0)
  226.             return;
  227.         a[start][end] = true;
  228.     }
  229.  
  230.     ~graph() {
  231.         for(int i = 0; i < this->numberOfNodes; i++) {
  232.             delete [] a[i];
  233.         }
  234.         delete [] a;
  235.     }
  236. };
  237.  
  238. int main(int argc, char** argv) {
  239.  
  240.     graph g1(6);
  241.     g1.singleSourceShortestPath(3);
  242.     return 0;
  243. }
  244.  
  245.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:152:47: error: 'int& operator[](int*, graph::Node)' must be a nonstatic member function
         friend int& operator [](int *a, Node i) {
                                               ^
prog.cpp: In instantiation of 'void minPriorityQueue<t>::insert(t) [with t = graph::Node]':
prog.cpp:184:25:   required from here
prog.cpp:33:26: error: no match for 'operator[]' (operand types are 'graph::Node' and 'int')
             t temp = data[currentPosition];
                          ^
prog.cpp:34:21: error: no match for 'operator[]' (operand types are 'int*' and 'graph::Node')
             position[temp] = currentPosition;
                     ^
prog.cpp: In instantiation of 't minPriorityQueue<t>::minElement() [with t = graph::Node]':
prog.cpp:195:38:   required from here
prog.cpp:47:17: error: no match for 'operator[]' (operand types are 'int*' and 'graph::Node')
         position[(data[currentPosition])] = 1;
                 ^
prog.cpp: In instantiation of 'void minPriorityQueue<t>::swapPositionValue(int, int) [with t = graph::Node]':
prog.cpp:113:47:   required from 'void minPriorityQueue<t>::heapifyUp(int) [with t = graph::Node]'
prog.cpp:202:48:   required from here
prog.cpp:24:40: error: no match for 'operator[]' (operand types are 'int*' and 'graph::Node')
             int tempPosition = position[data[parent]];
                                        ^
prog.cpp:25:46: error: no match for 'operator[]' (operand types are 'int*' and 'graph::Node')
             position[data[parent]] = position[data[temp]];
                                              ^
prog.cpp:25:21: error: no match for 'operator[]' (operand types are 'int*' and 'graph::Node')
             position[data[parent]] = position[data[temp]];
                     ^
prog.cpp:26:21: error: no match for 'operator[]' (operand types are 'int*' and 'graph::Node')
             position[data[temp]] = tempPosition;
                     ^
stdout
copy 
Standard output is empty
https://ideone.com/GRQHHZ
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!