Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<math.h>
- using namespace std;
- class Node {
- private:
- int v;
- float w;
- Node* next;
- public:
- Node() {
- v = 0;
- w = 0;
- next = NULL;
- }
- int getV() const {
- return v;
- }
- float getW() const {
- return w;
- }
- Node* getNext() const {
- return next;
- }
- void setV(int d) {
- v = d;
- }
- void setW(float d) {
- w = d;
- }
- void setNext(Node* ptr) {
- next = ptr;
- }
- };
- struct info {
- int Vertex1;
- int Vertex2;
- float weight;
- };
- info* BuildGraph(int NumEdge, int NumNode) {
- info* arrayOfStructures = new info[NumEdge];
- int v1, v2;
- float w;
- for (int i = 0; i < NumEdge; i++)
- {
- cout << "Please Enter Edge" << i + 1 << " And Its Weight In The Order (Vertex1, Vertex1, Weight):" << endl;
- cin >> v1;
- while (v1 <= 0 || v1 > NumNode) {
- cout << "Invalid Value >>> Try Again >>>The Vertex Value Should Be Between 1 And " << NumNode << endl;
- cin >> v1;
- }
- cin >> v2;
- while (v2 <= 0 || v2 > NumNode) {
- cout << "Invalid Value >>> Try Again >>>The Vertex Value Should Be Between 1 And " << NumNode << endl;
- cin >> v2;
- }
- cin >> w;
- // store at array of structures:
- arrayOfStructures[i].Vertex1 = v1;
- arrayOfStructures[i].Vertex2 = v2;
- arrayOfStructures[i].weight = w;
- }
- return arrayOfStructures;
- }
- float** storeAtMatrix(info* arrayOfStructures, int NumEdge, int NumNode) {
- //store at matrix:
- float** matrix = new float* [NumNode];
- for (int i = 0; i < NumNode; i++)
- matrix[i] = new float[NumNode];
- for (int i = 0; i < NumNode; i++) {
- int v1 = i + 1;
- for (int j = 0; j < NumNode; j++) {
- int v2 = j + 1;
- int k;
- for (k = 0; k < NumEdge; k++) {
- if ((arrayOfStructures[k].Vertex1 == v1 && arrayOfStructures[k].Vertex2 == v2) || (arrayOfStructures[k].Vertex2 == v1 && arrayOfStructures[k].Vertex1 == v2))
- {
- matrix[i][j] = arrayOfStructures[k].weight;
- break;
- }
- else continue;
- }
- if (k == NumEdge)
- {
- matrix[i][j] = 0;
- }
- }
- }
- return matrix;
- }
- Node** storeAtArrayOfLinkedLists(info* arrayOfStructures, int NoEdge, int NoNode) {
- //store at array of linked lists:
- Node** a = new Node * [NoNode];
- for (int i = 0; i < NoNode; i++)
- a[i] = NULL;
- for (int i = 0; i < NoNode; i++)
- for (int j = 0; j < NoEdge; j++) {
- if (i + 1 == arrayOfStructures[j].Vertex1)
- {
- Node* p = new Node;
- p->setV(arrayOfStructures[j].Vertex2);
- p->setW(arrayOfStructures[j].weight);
- p->setNext(NULL);
- if (a[i] == NULL) { a[i] = p; p->setNext(NULL); }
- else {
- Node* q = a[i];
- while (q->getNext() != NULL) q = q->getNext();
- q->setNext(p);
- p->setNext(NULL);
- }
- }
- else if (i + 1 == arrayOfStructures[j].Vertex2)
- {
- Node* p = new Node;
- p->setV(arrayOfStructures[j].Vertex1);
- p->setW(arrayOfStructures[j].weight);
- p->setNext(NULL);
- if (a[i] == NULL) { a[i] = p; p->setNext(NULL); }
- else {
- Node* q = a[i];
- while (q->getNext() != NULL) q = q->getNext();
- q->setNext(p);
- p->setNext(NULL);
- }
- }
- }
- return a;
- }
- void intersection(info* arrayOfStructuresA, info* arrayOfStructuresB, int numEdgeA, int numEdgeB)
- {
- info* C = new info[numEdgeA+numEdgeB];
- for (int i = 0; i <numEdgeA+numEdgeB ; i++)
- {
- 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)
- {
- C[i].Vertex1 = arrayOfStructuresA[i].Vertex1;
- C[i].Vertex2 = arrayOfStructuresA[i].Vertex2;
- C[i].weight = arrayOfStructuresA[i].weight;
- cout << " " << C[i].Vertex1 << " " << C[i].Vertex2 << " " << C[i].weight << endl;
- cout << endl;
- }
- }
- }
- /*void intersection(info* arrayOfStructuresA, info* arrayOfStructuresB, int numEdgeA, int numEdgeB)
- {
- for (int i = 0; i < numEdgeA; i++) {
- for (int j = 0; j < numEdgeB; j++) {
- 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) {
- cout << '(' << arrayOfStructuresB[j].Vertex1 << ',' << arrayOfStructuresB[j].Vertex2 << ')';
- }
- }
- }
- cout << endl;
- }*/
- void highestDegree(Node** a, int numNode) {
- Node* p;
- int j = 0;
- int* count = new int[numNode];
- for (int i = 0; i < numNode; i++)
- {
- int c = 0;
- p = a[i];
- while(p) {
- p = p->getNext();
- c++;
- }
- j++;
- count[j] = c;
- }
- // Loop to store largest number to a[0]
- int max = count[0];
- for (int i = 1; i < numNode; i++)
- {
- // Change < to > if you want to find the smallest element
- if (max < count[i])
- max = count[i];
- }
- //cout << "highestDegree = " << count[0];
- cout << endl << "The vertex (vertices) with the highest degree in graph : ";
- for (int i = 0; i < numNode; i++) {
- if (count[i]== max) { cout << i + 1 << ','; }
- }
- cout << "with the degree of\n" << max << endl;
- }
- void lowestDegree(Node** a, int numNode) {
- Node* p;
- int* count = new int[numNode];
- for (int i = 0; i < numNode; i++)
- {
- int c = 0;
- p = a[i];
- if (p != NULL) {
- p = p->getNext();
- c++;
- }
- count[i] = c;
- }
- // Loop to store lowest number to count[0]
- for (int i = 1; i < numNode; i++)
- {
- // Change < to > if you want to find the smallest element
- if (count[0] > count[i])
- count[0] = count[i];
- }
- cout << "lowestDegree = " << count[0];
- }
- int main() {
- cout << "^^^^^^^^^^Hallo In A Program ^^^^^^^^^^" << endl;
- int NumEdgeA;
- int NumNodeA;
- int NumEdgeB;
- int NumNodeB;
- cout << "Please Enter The Number Of Nodes or Gragh A" << endl;
- cin >> NumNodeA;
- while (NumNodeA <= 0) {
- cout << "Invalid Value >>> Try Again: " << endl;
- cin >> NumNodeA;
- }
- cout << "Please Enter The Number Of Edges Of Graph A" << endl;
- cin >> NumEdgeA;
- while (NumEdgeA < 0) {
- cout << "Invalid Value >>> Try Again: " << endl;
- cin >> NumEdgeA;
- }
- cout << "Please Enter The Number Of Nodes or Gragh B" << endl;
- cin >> NumNodeB;
- while (NumNodeB <= 0) {
- cout << "Invalid Value >>> Try Again: " << endl;
- cin >> NumNodeB;
- }
- cout << "Please Enter The Number Of Edges Of Graph B" << endl;
- cin >> NumEdgeB;
- while (NumEdgeB < 0) {
- cout << "Invalid Value >>> Try Again" << endl;
- cin >> NumEdgeB;
- }
- info* arrayOfStructuresA = BuildGraph(NumEdgeA, NumNodeA);
- float** matrixA = storeAtMatrix(arrayOfStructuresA, NumEdgeA, NumNodeA);
- Node** a = storeAtArrayOfLinkedLists(arrayOfStructuresA, NumEdgeA, NumNodeA);
- cout << "Enter Edege (Graph)" << endl;
- info* arrayOfStructuresB = BuildGraph(NumEdgeB, NumNodeB);
- float** matrixB = storeAtMatrix(arrayOfStructuresB, NumEdgeB, NumNodeB);
- Node** b = storeAtArrayOfLinkedLists(arrayOfStructuresB, NumEdgeB, NumNodeB);
- int choice, flag = 0;
- do {
- cout << endl << "Please Select One Of The Following:" << endl
- << "1. Output The Graph A From The Array Of Lists" << endl
- << "2. Output The Graph A From The Matrix" << endl
- << "3. Output The Graph A From The Array Of Structures" << endl
- << "4.Output The Graph B From The Array Of Lists" << endl
- << "5. Output The Graph B From The Matrix" << endl
- << "6. Output The Graph B From The Array Of Structures" << endl
- << "7 - Output The Intersection Between Both Graphs " << endl
- << "8 - Is Graph(A) A Subgraph Of Graph(B) " << endl
- << "9- Is Graph (B) A Subgraph Of Graph (A)? " << endl
- << "10- Display The Vertex (Vertices) With The Highest Degree From Graph A." << endl
- << "11- Display The Vertex (Vertices) With The Lowest Degree From Graph A." << endl
- << "12- Display The Vertex (Vertices) With The Highest Degree From Graph B." << endl
- << "13- Display The Vertex (Vertices) With The Lowest Degree From Graph B. " << endl
- << "14. Exit Program. " << endl;
- cout << "enter your choice: ";
- cin >> choice;
- int max, sum;
- int* g = new int[NumNodeA];
- int* F = new int[NumNodeB];
- switch (choice) {
- case 1:
- cout << "Array Of List: " << endl;
- for (int i = 0; i < NumNodeA; i++) {
- Node* q = a[i];
- while (q != NULL) {
- cout << "Edge (" << i + 1 << "," << q->getV() << ") has the weight of " << q->getW() << endl;
- q = q->getNext();
- }
- }
- break;
- case 2:
- cout << "Gragh Of The Matrix" << endl;
- for (int i = 0; i < NumNodeA; i++)
- for (int j = 0; j < NumNodeA; j++) {
- if (matrixA[i][j] != 0)
- cout << "Edge (" << i + 1 << "," << j + 1 << ") has the weight of " << matrixA[i][j] << endl;
- }
- break;
- case 3: //3- Output the graph from the array of structures
- for (int i = 0; i < NumEdgeA; i++) {
- cout << i << " v1: " << arrayOfStructuresA[i].Vertex1;
- cout << " v2: " << arrayOfStructuresA[i].Vertex2;
- cout << " weight: " << arrayOfStructuresA[i].weight << endl;
- }
- for (int i = 0; i < NumEdgeA; i++)
- {
- cout << "Edge (" << arrayOfStructuresA[i].Vertex1 << "," << arrayOfStructuresA[i].Vertex2 << ") has the weight of " << arrayOfStructuresA[i].weight << endl;
- if (arrayOfStructuresA[i].Vertex2 != arrayOfStructuresA[i].Vertex1)
- cout << "Edge (" << arrayOfStructuresA[i].Vertex2 << "," << arrayOfStructuresA[i].Vertex1 << ") has the weight of " << arrayOfStructuresA[i].weight << endl;
- }
- break;
- case 4:
- for (int i = 0; i < NumNodeB; i++) {
- Node* q = b[i];
- while (q != NULL) {
- cout << "Edge (" << i + 1 << "," << q->getV() << ") has the weight of " << q->getW() << endl;
- q = q->getNext();
- }
- }
- break;
- case 5:
- for (int i = 0; i < NumNodeB; i++)
- for (int j = 0; j < NumNodeB; j++) {
- if (matrixB[i][j] != 0)
- cout << "Edge (" << i + 1 << "," << j + 1 << ") has the weight of " << matrixB[i][j] << endl;
- }
- break;
- case 6:
- for (int i = 0; i < NumEdgeB; i++) {
- cout << i << " v1: " << arrayOfStructuresB[i].Vertex1;
- cout << " v2: " << arrayOfStructuresB[i].Vertex2;
- cout << " weight: " << arrayOfStructuresB[i].weight << endl;
- }
- for (int i = 0; i < NumEdgeB; i++)
- {
- cout << "Edge (" << arrayOfStructuresB[i].Vertex1 << "," << arrayOfStructuresB[i].Vertex2 << ") has the weight of " << arrayOfStructuresB[i].weight << endl;
- if (arrayOfStructuresB[i].Vertex2 != arrayOfStructuresB[i].Vertex1)
- cout << "Edge (" << arrayOfStructuresA[i].Vertex2 << "," << arrayOfStructuresB[i].Vertex1 << ") has the weight of " << arrayOfStructuresB[i].weight << endl;
- }
- break;
- case 7:
- intersection(arrayOfStructuresA, arrayOfStructuresA, NumEdgeA, NumEdgeB);
- break;
- case 8:
- flag = 0;
- for (int i = 0; i < NumEdgeA; i++) {
- for (int j = 0; j < NumEdgeB; j++) {
- 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) {
- flag++;
- }
- }
- }
- if (flag == NumEdgeA)
- cout << endl << "Graph (A) Is A Subgraph Of Graph (B) Yes" << endl;
- else
- cout << endl << "Graph (A) Is Not A Subgraph Of Graph (B) No" << endl;
- break;
- case 9:
- flag = 0;
- for (int i = 0; i < NumEdgeA; i++) {
- for (int j = 0; j < NumEdgeB; j++) {
- 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) {
- flag++;
- }
- }
- }
- if (flag == NumEdgeB)
- cout << "Graph (B) Is A Subgraph Of Graph (A) Yes" << endl;
- else
- cout << "Graph (B) Is Not A Subgraph Of Graph (A) no\n";
- break;
- case 10:
- for (int i = 0; i < NumNodeA; i++) {
- g[i] = 0; sum = 0;
- for (int j = 0; j < NumNodeA; j++) {
- if (matrixA[i][j] != 0) {
- sum++;
- }
- }g[i] = sum;
- }
- max = g[0];
- for (int i = 0; i < NumNodeA; i++) {
- if (g[i] > max) {
- max = g[i];
- }
- }
- cout << endl << "The vertex (vertices) with the highest degree in graph A: ";
- for (int i = 0; i < NumNodeA; i++) {
- if (g[i] == max) { cout << i + 1 << ','; }
- }
- cout << "with the degree of" << max << endl;
- break;
- case 11:
- for (int i = 0; i < NumNodeA; i++) {
- g[i] = 0; sum = 0;
- for (int j = 0; j < NumNodeA; j++) {
- if (matrixA[i][j] != 0) {
- sum++;
- }
- }g[i] = sum;
- }
- max = g[0];
- for (int i = 0; i < NumNodeA; i++) {
- if (g[i] < max) {
- max = g[i];
- }
- }
- cout << endl << "The vertex (vertices) with the LOWEST degree in graph A: ";
- for (int i = 0; i < NumNodeA; i++) {
- if (g[i] == max) { cout << i + 1 << ','; }
- }
- cout << "with the degree of" << max << endl;
- break;
- case 12:
- for (int i = 0; i < NumNodeB; i++) {
- F[i] = 0; sum = 0;
- for (int j = 0; j < NumNodeB; j++) {
- if (matrixB[i][j] != 0) {
- sum++;
- }
- }F[i] = sum;
- }
- max = F[0];
- for (int i = 0; i < NumNodeB; i++) {
- if (F[i] > max) {
- max = F[i];
- }
- }
- cout << endl << "The vertex (vertices) with the highest degree in graph B: ";
- for (int i = 0; i < NumNodeB; i++) {
- if (F[i] == max) { cout << i + 1 << ','; }
- }
- cout << "with the degree of" << max << endl;
- break;
- case 13:
- for (int i = 0; i < NumNodeB; i++) {
- F[i] = 0; sum = 0;
- for (int j = 0; j < NumNodeB; j++) {
- if (matrixB[i][j] != 0) {
- sum++;
- }
- }F[i] = sum;
- }
- max = F[0];
- for (int i = 0; i < NumNodeB; i++) {
- if (F[i] < max) {
- max = F[i];
- }
- }
- cout << endl << "The vertex (vertices) with the highest degree in graph B: ";
- for (int i = 0; i < NumNodeB; i++) {
- if (F[i] == max) { cout << i + 1 << ','; }
- }
- cout << "with the degree of" << max << endl;
- break;
- default:
- cout << "Error Choice" << endl;
- }
- } while (choice != 14);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement