SHARE
TWEET

Graph Shamsur Rahman

a guest Mar 20th, 2017 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define White 0
  5. #define Gray 2
  6. #define Black 3
  7.  
  8. int row, col;
  9. int **graph;
  10.  
  11. class Graph
  12. {
  13. private:
  14.     bool** adjacencyMatrix;
  15.     int vertexCount;
  16. public:
  17.  
  18.     Graph(int vertexCount)
  19.     {
  20.  
  21.         this->vertexCount = vertexCount;
  22.         adjacencyMatrix = new bool*[vertexCount];
  23.  
  24.         for (int i = 0; i < vertexCount; i++)
  25.         {
  26.             adjacencyMatrix[i] = new bool[vertexCount];
  27.             for (int j = 0; j < vertexCount; j++)
  28.                 adjacencyMatrix[i][j] = false;
  29.         }
  30.     }
  31.  
  32.     Graph(const char* filename, int vertexCount)
  33.     {
  34.  
  35.         this->vertexCount = vertexCount;
  36.         adjacencyMatrix = new bool*[vertexCount];
  37.  
  38.         ifstream file;
  39.         file.open(filename, ios::in);
  40.  
  41.         if( !file)
  42.         {
  43.             cout << "\nError: Cannot open file\n";
  44.             return;
  45.         }
  46.  
  47.         if(file.is_open())
  48.         {
  49.             for (int i = 0; i < vertexCount; i++)
  50.             {
  51.  
  52.                 adjacencyMatrix[i] = new bool[vertexCount];
  53.  
  54.                 for (int j = 0; j < vertexCount; j++)
  55.                     file>>adjacencyMatrix[i][j];
  56.             }
  57.         }
  58.     }
  59.  
  60.  
  61.     ~Graph()
  62.     {
  63.         for (int i = 0; i < vertexCount; i++)
  64.             delete[] adjacencyMatrix[i];
  65.         delete[] adjacencyMatrix;
  66.     }
  67.  
  68.     void runDFS(int u, int state[])
  69.     {
  70.  
  71.         state[u] = Gray;
  72.  
  73.         for (int v = 0; v < vertexCount; v++)
  74.  
  75.             if (isEdge(u, v) && state[v] == White)
  76.  
  77.                 runDFS(v, state);
  78.  
  79.         state[u] = Black;
  80.         cout<<u<<",";
  81.     }
  82.  
  83.     void DFS()
  84.     {
  85.  
  86.         int *state = new int[vertexCount];
  87.  
  88.         for (int i = 0; i < vertexCount; i++)
  89.             state[i] = White;
  90.  
  91.         runDFS(0, state);
  92.  
  93.         delete [] state;
  94.  
  95.     }
  96.  
  97.     void display()
  98.     {
  99.         int u,v;
  100.  
  101.         for(u=0; u<vertexCount; ++u)
  102.         {
  103.             cout << "\nadj[" << (char) (u+65) << "] -> ";
  104.             for(v=0; v<vertexCount; ++v)
  105.             {
  106.                 cout << " " << adjacencyMatrix[u][v];
  107.             }
  108.         }
  109.         cout << "\n\n";
  110.     }
  111.  
  112.     void writeFile()
  113.     {
  114.         FILE *p;
  115.         p = fopen("graph.txt", "w+");
  116.         int u,v;
  117.  
  118.         for(u=0; u<vertexCount; ++u)
  119.         {
  120.             for(v=0; v<vertexCount; ++v)
  121.             {
  122.                 fprintf(p, "%d ",  adjacencyMatrix[u][v]);
  123.             }
  124.             fprintf(p, "\n");
  125.         }
  126.         fclose(p);
  127.     }
  128.  
  129.     bool isEdge(int i, int j)
  130.     {
  131.         if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount)
  132.             return adjacencyMatrix[i][j];
  133.         else
  134.             return false;
  135.     }
  136.  
  137.     void removeEdge(int i, int j)
  138.     {
  139.         if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount)
  140.         {
  141.             adjacencyMatrix[i][j] = false;
  142.             adjacencyMatrix[j][i] = false;
  143.         }
  144.     }
  145.  
  146.     void addEdge(int i, int j)
  147.     {
  148.         if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount)
  149.         {
  150.             adjacencyMatrix[i][j] = true;
  151.             adjacencyMatrix[j][i] = true;
  152.         }
  153.     }
  154. };
  155.  
  156.  
  157. int main()
  158. {
  159.     graph = new int*[row];
  160.     for (int i = 0; i < row; i++)
  161.     {
  162.         graph[i] = new int[col];
  163.     }
  164.  
  165.     for (int i = 0; i < row; i++)
  166.     {
  167.         for (int j = 0; j < col; j++)
  168.         {
  169.             graph[i][j] = 0;
  170.         }
  171.     }
  172.  
  173.  
  174.     Graph* A = new Graph(5);
  175.  
  176.     printf("Task 1:\n");
  177.  
  178.     A->addEdge(0,3);
  179.     A->addEdge(1,3);
  180.     A->addEdge(1,4);
  181.     A->addEdge(2,4);
  182.     A->addEdge(3,0);
  183.     A->addEdge(3,1);
  184.     A->addEdge(3,4);
  185.     A->addEdge(4,1);
  186.     A->addEdge(4,2);
  187.     A->addEdge(4,3);
  188.  
  189.     A->display();
  190.  
  191.     printf("Task 2:\n");
  192.  
  193.     A->writeFile();
  194.  
  195.     printf("\nA file named graph.txt is generated\n");
  196.  
  197.     printf("\nFinal task:\n\nReading the graph.txt file:\n\n");
  198.  
  199.     Graph* B = new Graph("graph.txt", 5);
  200.  
  201.     B->display();
  202.  
  203.     return 0;
  204.  
  205. }
RAW Paste Data
Top