Advertisement
Guest User

lllll

a guest
Feb 16th, 2020
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.59 KB | None | 0 0
  1. #include<iostream>
  2. #include<math.h>
  3. using namespace std;
  4. class Node {
  5. private:
  6.     int v;
  7.     float w;
  8.     Node* next;
  9. public:
  10.     Node() {
  11.         v = 0;
  12.         w = 0;
  13.         next = NULL;
  14.     }
  15.     int getV() const {
  16.         return v;
  17.     }
  18.     float getW() const {
  19.         return w;
  20.     }
  21.     Node* getNext() const {
  22.  
  23.         return next;
  24.     }
  25.     void setV(int d) {
  26.         v = d;
  27.     }
  28.     void setW(float d) {
  29.         w = d;
  30.     }
  31.     void setNext(Node* ptr) {
  32.         next = ptr;
  33.     }
  34. };
  35. struct info {
  36.     int Vertex1;
  37.     int Vertex2;
  38.     float weight;
  39.  
  40. };
  41. info* BuildGraph(int NumEdge, int NumNode) {
  42.     info* arrayOfStructures = new info[NumEdge];
  43.     int v1, v2;
  44.     float w;
  45.     for (int i = 0; i < NumEdge; i++)
  46.     {
  47.         cout << "Please Enter Edge" << i + 1 << " And Its Weight In The Order (Vertex1, Vertex1, Weight):" << endl;
  48.         cin >> v1;
  49.         while (v1 <= 0 || v1 > NumNode) {
  50.             cout << "Invalid Value >>> Try Again >>>The Vertex Value Should Be Between 1 And " << NumNode << endl;
  51.             cin >> v1;
  52.         }
  53.         cin >> v2;
  54.         while (v2 <= 0 || v2 > NumNode) {
  55.             cout << "Invalid Value >>> Try Again >>>The Vertex Value Should Be Between 1 And " << NumNode << endl;
  56.             cin >> v2;
  57.         }
  58.         cin >> w;
  59.         // store at array of structures:
  60.         arrayOfStructures[i].Vertex1 = v1;
  61.         arrayOfStructures[i].Vertex2 = v2;
  62.         arrayOfStructures[i].weight = w;
  63.     }
  64.     return arrayOfStructures;
  65. }
  66. float** storeAtMatrix(info* arrayOfStructures, int NumEdge, int NumNode) {
  67.     //store at matrix:
  68.     float** matrix = new float* [NumNode];
  69.     for (int i = 0; i < NumNode; i++)
  70.         matrix[i] = new float[NumNode];
  71.  
  72.     for (int i = 0; i < NumNode; i++) {
  73.         int v1 = i + 1;
  74.         for (int j = 0; j < NumNode; j++) {
  75.  
  76.             int v2 = j + 1;
  77.             int k;
  78.             for (k = 0; k < NumEdge; k++) {
  79.                 if ((arrayOfStructures[k].Vertex1 == v1 && arrayOfStructures[k].Vertex2 == v2) || (arrayOfStructures[k].Vertex2 == v1 && arrayOfStructures[k].Vertex1 == v2))
  80.                 {
  81.                     matrix[i][j] = arrayOfStructures[k].weight;
  82.                     break;
  83.                 }
  84.                 else continue;
  85.             }
  86.             if (k == NumEdge)
  87.             {
  88.                 matrix[i][j] = 0;
  89.             }
  90.         }
  91.  
  92.     }
  93.     return matrix;
  94. }
  95.  
  96. Node** storeAtArrayOfLinkedLists(info* arrayOfStructures, int NoEdge, int NoNode) {
  97.     //store at array of linked lists:
  98.     Node** a = new  Node * [NoNode];
  99.     for (int i = 0; i < NoNode; i++)
  100.         a[i] = NULL;
  101.  
  102.     for (int i = 0; i < NoNode; i++)
  103.         for (int j = 0; j < NoEdge; j++) {
  104.             if (i + 1 == arrayOfStructures[j].Vertex1)
  105.             {
  106.                 Node* p = new Node;
  107.                 p->setV(arrayOfStructures[j].Vertex2);
  108.                 p->setW(arrayOfStructures[j].weight);
  109.                 p->setNext(NULL);
  110.                 if (a[i] == NULL) { a[i] = p;  p->setNext(NULL); }
  111.                 else {
  112.                     Node* q = a[i];
  113.                     while (q->getNext() != NULL) q = q->getNext();
  114.                     q->setNext(p);
  115.                     p->setNext(NULL);
  116.                 }
  117.  
  118.             }
  119.  
  120.             else if (i + 1 == arrayOfStructures[j].Vertex2)
  121.             {
  122.                 Node* p = new Node;
  123.                 p->setV(arrayOfStructures[j].Vertex1);
  124.                 p->setW(arrayOfStructures[j].weight);
  125.                 p->setNext(NULL);
  126.                 if (a[i] == NULL) { a[i] = p;  p->setNext(NULL); }
  127.                 else {
  128.                     Node* q = a[i];
  129.                     while (q->getNext() != NULL) q = q->getNext();
  130.                     q->setNext(p);
  131.                     p->setNext(NULL);
  132.                 }
  133.             }
  134.         }
  135.     return a;
  136. }
  137. void intersection(info* arrayOfStructuresA, info* arrayOfStructuresB, int numEdgeA, int numEdgeB)
  138. {
  139.  
  140.    
  141.     info* C = new info[numEdgeA+numEdgeB];
  142.     for (int i = 0; i <numEdgeA+numEdgeB ; i++)
  143.     {
  144.         if (arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[i].Vertex2 && arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[i].Vertex2 && arrayOfStructuresA[i].weight == arrayOfStructuresB[i].weight|| arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[i].Vertex2 && arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[i].Vertex1 && arrayOfStructuresA[i].weight == arrayOfStructuresB[i].weight)
  145.        
  146.         {
  147.    
  148.  
  149.             C[i].Vertex1 = arrayOfStructuresA[i].Vertex1;
  150.             C[i].Vertex2 = arrayOfStructuresA[i].Vertex2;
  151.             C[i].weight = arrayOfStructuresA[i].weight;
  152.            
  153.        
  154.            
  155.         cout << " " << C[i].Vertex1 << "     " << C[i].Vertex2 << "     " << C[i].weight << endl;
  156.     cout << endl;
  157.        
  158.     }
  159. }
  160. }
  161.  
  162. /*void intersection(info* arrayOfStructuresA, info* arrayOfStructuresB, int numEdgeA, int numEdgeB)
  163. {
  164.     for (int i = 0; i < numEdgeA; i++) {
  165.         for (int j = 0; j < numEdgeB; j++) {
  166.             if (arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[j].Vertex1 && arrayOfStructuresA[i].weight == arrayOfStructuresB[j].weight && arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[j].Vertex2 || arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[j].Vertex2 && arrayOfStructuresA[i].weight == arrayOfStructuresB[j].weight && arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[j].Vertex1) {
  167.                 cout << '(' << arrayOfStructuresB[j].Vertex1 << ',' << arrayOfStructuresB[j].Vertex2 << ')';
  168.             }
  169.         }
  170.     }
  171.     cout << endl;
  172. }*/
  173. void  highestDegree(Node** a, int numNode) {
  174.     Node* p;
  175.     int j = 0;
  176.     int* count = new int[numNode];
  177.     for (int i = 0; i < numNode; i++)
  178.     {
  179.         int c = 0;
  180.         p = a[i];
  181.         while(p) {
  182.             p = p->getNext();
  183.             c++;
  184.         }
  185.         j++;
  186.         count[j] = c;
  187.  
  188.     }
  189.     // Loop to store largest number to a[0]
  190.     int max = count[0];
  191.     for (int i = 1; i < numNode; i++)
  192.     {
  193.         // Change < to > if you want to find the smallest element
  194.         if (max < count[i])
  195.         max  = count[i];
  196.     }
  197.     //cout << "highestDegree = " << count[0];
  198.  
  199.     cout << endl << "The vertex (vertices) with the highest degree in graph : ";
  200.     for (int i = 0; i < numNode; i++) {
  201.         if (count[i]== max) { cout << i + 1 << ','; }
  202.     }
  203.     cout << "with the degree of\n" << max << endl;
  204.  
  205. }
  206. void  lowestDegree(Node** a, int numNode) {
  207.     Node* p;
  208.     int* count = new int[numNode];
  209.     for (int i = 0; i < numNode; i++)
  210.     {
  211.         int c = 0;
  212.         p = a[i];
  213.         if (p != NULL) {
  214.             p = p->getNext();
  215.             c++;
  216.         }
  217.         count[i] = c;
  218.  
  219.     }
  220.     // Loop to store lowest number to count[0]
  221.     for (int i = 1; i < numNode; i++)
  222.     {
  223.         // Change < to > if you want to find the smallest element
  224.         if (count[0] > count[i])
  225.             count[0] = count[i];
  226.     }
  227.     cout << "lowestDegree = " << count[0];
  228.  
  229. }
  230.  
  231. int main() {
  232.     cout << "^^^^^^^^^^Hallo In A Program ^^^^^^^^^^" << endl;
  233.     int NumEdgeA;
  234.     int NumNodeA;
  235.     int NumEdgeB;
  236.     int NumNodeB;
  237.     cout << "Please Enter The Number Of Nodes or Gragh A" << endl;
  238.     cin >> NumNodeA;
  239.     while (NumNodeA <= 0) {
  240.         cout << "Invalid Value >>> Try Again: " << endl;
  241.         cin >> NumNodeA;
  242.     }
  243.  
  244.  
  245.     cout << "Please Enter The Number Of Edges Of Graph A" << endl;
  246.     cin >> NumEdgeA;
  247.     while (NumEdgeA < 0) {
  248.         cout << "Invalid Value >>> Try Again:  " << endl;
  249.         cin >> NumEdgeA;
  250.     }
  251.  
  252.  
  253.     cout << "Please Enter The Number Of Nodes or Gragh B" << endl;
  254.     cin >> NumNodeB;
  255.     while (NumNodeB <= 0) {
  256.         cout << "Invalid Value >>> Try Again:  " << endl;
  257.         cin >> NumNodeB;
  258.     }
  259.  
  260.  
  261.     cout << "Please Enter The Number Of Edges Of Graph B" << endl;
  262.     cin >> NumEdgeB;
  263.     while (NumEdgeB < 0) {
  264.         cout << "Invalid Value >>> Try Again" << endl;
  265.         cin >> NumEdgeB;
  266.     }
  267.     info* arrayOfStructuresA = BuildGraph(NumEdgeA, NumNodeA);
  268.     float** matrixA = storeAtMatrix(arrayOfStructuresA, NumEdgeA, NumNodeA);
  269.     Node** a = storeAtArrayOfLinkedLists(arrayOfStructuresA, NumEdgeA, NumNodeA);
  270.     cout << "Enter Edege (Graph)" << endl;
  271.     info* arrayOfStructuresB = BuildGraph(NumEdgeB, NumNodeB);
  272.     float** matrixB = storeAtMatrix(arrayOfStructuresB, NumEdgeB, NumNodeB);
  273.     Node** b = storeAtArrayOfLinkedLists(arrayOfStructuresB, NumEdgeB, NumNodeB);
  274.     int choice, flag = 0;
  275.     do {
  276.         cout << endl << "Please Select One Of The Following:" << endl
  277.             << "1. Output The Graph A From The Array Of Lists" << endl
  278.             << "2. Output The Graph  A From The Matrix" << endl
  279.             << "3. Output The Graph A From The Array Of Structures" << endl
  280.             << "4.Output The Graph B From The Array Of Lists" << endl
  281.             << "5. Output The Graph  B From The Matrix" << endl
  282.             << "6. Output The Graph B From The Array Of Structures" << endl
  283.             << "7 - Output The Intersection Between Both Graphs " << endl
  284.             << "8 - Is Graph(A) A Subgraph Of Graph(B) " << endl
  285.             << "9- Is Graph (B) A Subgraph Of Graph (A)? " << endl
  286.             << "10- Display The Vertex (Vertices) With The Highest Degree From Graph A." << endl
  287.             << "11- Display The Vertex (Vertices) With The Lowest Degree From Graph A." << endl
  288.             << "12- Display The Vertex (Vertices) With The Highest Degree From Graph B." << endl
  289.             << "13- Display The Vertex (Vertices) With The Lowest Degree From Graph B. " << endl
  290.             << "14. Exit Program. " << endl;
  291.         cout << "enter your choice:   ";
  292.         cin >> choice;
  293.         int max, sum;
  294.         int* g = new int[NumNodeA];
  295.         int* F = new int[NumNodeB];
  296.         switch (choice) {
  297.  
  298.         case 1:
  299.             cout << "Array Of List: " << endl;
  300.             for (int i = 0; i < NumNodeA; i++) {
  301.                 Node* q = a[i];
  302.                 while (q != NULL) {
  303.                     cout << "Edge (" << i + 1 << "," << q->getV() << ")  has the weight of " << q->getW() << endl;
  304.                     q = q->getNext();
  305.                 }
  306.             }
  307.             break;
  308.  
  309.         case 2:
  310.             cout << "Gragh Of The Matrix" << endl;
  311.             for (int i = 0; i < NumNodeA; i++)
  312.                 for (int j = 0; j < NumNodeA; j++) {
  313.                     if (matrixA[i][j] != 0)
  314.                         cout << "Edge (" << i + 1 << "," << j + 1 << ")  has the weight of " << matrixA[i][j] << endl;
  315.  
  316.                 }
  317.             break;
  318.  
  319.         case 3: //3- Output the graph from the array of structures
  320.  
  321.  
  322.  
  323.             for (int i = 0; i < NumEdgeA; i++) {
  324.                 cout << i << " v1: " << arrayOfStructuresA[i].Vertex1;
  325.                 cout << "  v2: " << arrayOfStructuresA[i].Vertex2;
  326.                 cout << "  weight: " << arrayOfStructuresA[i].weight << endl;
  327.             }
  328.  
  329.             for (int i = 0; i < NumEdgeA; i++)
  330.             {
  331.                 cout << "Edge (" << arrayOfStructuresA[i].Vertex1 << "," << arrayOfStructuresA[i].Vertex2 << ")  has the weight of " << arrayOfStructuresA[i].weight << endl;
  332.                 if (arrayOfStructuresA[i].Vertex2 != arrayOfStructuresA[i].Vertex1)
  333.                     cout << "Edge (" << arrayOfStructuresA[i].Vertex2 << "," << arrayOfStructuresA[i].Vertex1 << ")  has the weight of " << arrayOfStructuresA[i].weight << endl;
  334.             }
  335.  
  336.             break;
  337.  
  338.         case 4:
  339.             for (int i = 0; i < NumNodeB; i++) {
  340.                 Node* q = b[i];
  341.                 while (q != NULL) {
  342.                     cout << "Edge (" << i + 1 << "," << q->getV() << ")  has the weight of " << q->getW() << endl;
  343.                     q = q->getNext();
  344.                 }
  345.             }
  346.  
  347.             break;
  348.  
  349.         case 5:
  350.  
  351.  
  352.             for (int i = 0; i < NumNodeB; i++)
  353.                 for (int j = 0; j < NumNodeB; j++) {
  354.                     if (matrixB[i][j] != 0)
  355.                         cout << "Edge (" << i + 1 << "," << j + 1 << ")  has the weight of " << matrixB[i][j] << endl;
  356.  
  357.                 }
  358.             break;
  359.  
  360.  
  361.  
  362.         case 6:
  363.  
  364.             for (int i = 0; i < NumEdgeB; i++) {
  365.                 cout << i << " v1: " << arrayOfStructuresB[i].Vertex1;
  366.                 cout << "  v2: " << arrayOfStructuresB[i].Vertex2;
  367.                 cout << "  weight: " << arrayOfStructuresB[i].weight << endl;
  368.             }
  369.  
  370.             for (int i = 0; i < NumEdgeB; i++)
  371.             {
  372.                 cout << "Edge (" << arrayOfStructuresB[i].Vertex1 << "," << arrayOfStructuresB[i].Vertex2 << ")  has the weight of " << arrayOfStructuresB[i].weight << endl;
  373.                 if (arrayOfStructuresB[i].Vertex2 != arrayOfStructuresB[i].Vertex1)
  374.                     cout << "Edge (" << arrayOfStructuresA[i].Vertex2 << "," << arrayOfStructuresB[i].Vertex1 << ")  has the weight of " << arrayOfStructuresB[i].weight << endl;
  375.             }
  376.             break;
  377.  
  378.         case 7:
  379.             intersection(arrayOfStructuresA, arrayOfStructuresA, NumEdgeA, NumEdgeB);
  380.             break;
  381.  
  382.  
  383.         case 8:
  384.             flag = 0;
  385.             for (int i = 0; i < NumEdgeA; i++) {
  386.                 for (int j = 0; j < NumEdgeB; j++) {
  387.                     if (arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[j].Vertex1 && arrayOfStructuresA[i].weight == arrayOfStructuresB[j].weight && arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[j].Vertex2 || arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[j].Vertex1 && arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[j].Vertex2 && arrayOfStructuresA[i].weight == arrayOfStructuresB[j].weight) {
  388.                         flag++;
  389.                     }
  390.                 }
  391.             }
  392.  
  393.             if (flag == NumEdgeA)
  394.                 cout << endl << "Graph (A) Is A Subgraph Of Graph (B) Yes" << endl;
  395.  
  396.             else
  397.                 cout << endl << "Graph (A) Is Not A Subgraph Of Graph (B) No" << endl;
  398.  
  399.             break;
  400.  
  401.  
  402.         case 9:
  403.  
  404.             flag = 0;
  405.             for (int i = 0; i < NumEdgeA; i++) {
  406.                 for (int j = 0; j < NumEdgeB; j++) {
  407.                     if (arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[j].Vertex1 && arrayOfStructuresA[i].weight == arrayOfStructuresB[j].weight && arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[j].Vertex2 || arrayOfStructuresA[i].Vertex2 == arrayOfStructuresB[j].Vertex1 && arrayOfStructuresA[i].Vertex1 == arrayOfStructuresB[j].Vertex2) {
  408.                         flag++;
  409.                     }
  410.                 }
  411.             }
  412.             if (flag == NumEdgeB)
  413.                 cout << "Graph (B) Is A Subgraph Of Graph (A) Yes" << endl;
  414.  
  415.             else
  416.                 cout << "Graph (B) Is Not A Subgraph Of Graph (A) no\n";
  417.  
  418.             break;
  419.  
  420.  
  421.  
  422.  
  423.         case 10:
  424.            
  425.             for (int i = 0; i < NumNodeA; i++) {
  426.                 g[i] = 0; sum = 0;
  427.                 for (int j = 0; j < NumNodeA; j++) {
  428.  
  429.                     if (matrixA[i][j] != 0) {
  430.  
  431.                         sum++;
  432.                     }
  433.  
  434.                 }g[i] = sum;
  435.             }
  436.             max = g[0];
  437.             for (int i = 0; i < NumNodeA; i++) {
  438.                 if (g[i] > max) {
  439.                     max = g[i];
  440.                 }
  441.             }
  442.             cout << endl << "The vertex (vertices) with the highest degree in graph A: ";
  443.             for (int i = 0; i < NumNodeA; i++) {
  444.                 if (g[i] == max) { cout << i + 1 << ','; }
  445.             }
  446.             cout << "with the degree of" << max << endl;
  447.  
  448.             break;
  449.  
  450.  
  451.         case 11:
  452.  
  453.            
  454.  
  455.             for (int i = 0; i < NumNodeA; i++) {
  456.                 g[i] = 0; sum = 0;
  457.                 for (int j = 0; j < NumNodeA; j++) {
  458.  
  459.                     if (matrixA[i][j] != 0) {
  460.  
  461.                         sum++;
  462.                     }
  463.  
  464.                 }g[i] = sum;
  465.             }
  466.             max = g[0];
  467.             for (int i = 0; i < NumNodeA; i++) {
  468.                 if (g[i] < max) {
  469.                     max = g[i];
  470.                 }
  471.             }
  472.             cout << endl << "The vertex (vertices) with the LOWEST degree in graph A: ";
  473.             for (int i = 0; i < NumNodeA; i++) {
  474.                 if (g[i] == max) { cout << i + 1 << ','; }
  475.             }
  476.             cout << "with the degree of" << max << endl;
  477.             break;
  478.  
  479.  
  480.  
  481.         case 12:
  482.  
  483.             for (int i = 0; i < NumNodeB; i++) {
  484.                 F[i] = 0; sum = 0;
  485.                 for (int j = 0; j < NumNodeB; j++) {
  486.  
  487.                     if (matrixB[i][j] != 0) {
  488.  
  489.                         sum++;
  490.                     }
  491.  
  492.                 }F[i] = sum;
  493.             }
  494.             max = F[0];
  495.             for (int i = 0; i < NumNodeB; i++) {
  496.                 if (F[i] > max) {
  497.                     max = F[i];
  498.                 }
  499.             }
  500.             cout << endl << "The vertex (vertices) with the highest degree in graph B: ";
  501.             for (int i = 0; i < NumNodeB; i++) {
  502.                 if (F[i] == max) { cout << i + 1 << ','; }
  503.             }
  504.             cout << "with the degree of" << max << endl;
  505.  
  506.  
  507.             break;
  508.  
  509.         case 13:
  510.  
  511.             for (int i = 0; i < NumNodeB; i++) {
  512.                 F[i] = 0; sum = 0;
  513.                 for (int j = 0; j < NumNodeB; j++) {
  514.  
  515.                     if (matrixB[i][j] != 0) {
  516.  
  517.                         sum++;
  518.                     }
  519.  
  520.                 }F[i] = sum;
  521.             }
  522.             max = F[0];
  523.             for (int i = 0; i < NumNodeB; i++) {
  524.                 if (F[i] < max) {
  525.                     max = F[i];
  526.                 }
  527.             }
  528.             cout << endl << "The vertex (vertices) with the highest degree in graph B: ";
  529.             for (int i = 0; i < NumNodeB; i++) {
  530.                 if (F[i] == max) { cout << i + 1 << ','; }
  531.             }
  532.             cout << "with the degree of" << max << endl;
  533.  
  534.  
  535.             break;
  536.         default:
  537.             cout << "Error Choice" << endl;
  538.         }
  539.     } while (choice != 14);
  540.  
  541.  
  542. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement