daily pastebin goal
8%
SHARE
TWEET

graph.cpp

a guest Jan 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "graph.h"
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. graph::graph(int size)
  6. {
  7.     matrixSize = size;
  8.  
  9.     vertexNames = new int[matrixSize];
  10.     for (int i = 0; i < matrixSize; i++)
  11.         vertexNames[i] = -1;
  12.  
  13.     adjacencyMatrix = new bool*[matrixSize];
  14.     for (int i = 0; i < matrixSize; i++)
  15.         adjacencyMatrix[i] = new bool[matrixSize];
  16.     for (int i = 0; i < matrixSize; i++)
  17.         for (int j = 0; j < matrixSize; j++)
  18.             adjacencyMatrix[i][j] = false;
  19.  
  20.     currentVertexNumber = 0;
  21.     edgeNumber = 0;
  22. }
  23.  
  24. graph::~graph()
  25. {
  26.     for (int i = 0; i < matrixSize; i++)
  27.         delete[] adjacencyMatrix[i];
  28.     delete[] adjacencyMatrix;
  29.  
  30.     delete[] vertexNames;
  31. }
  32.  
  33. void graph::getGraphInfo()
  34. {
  35.     cout << "  ";
  36.     for (int i = 0; i < matrixSize; i++)
  37.     {
  38.         if (vertexNames[i] >= 0)
  39.             cout << vertexNames[i] << " ";
  40.     }
  41.     cout << "\n";
  42.  
  43.     for (int i = 0; i < matrixSize; i++)
  44.     {
  45.         if (vertexNames[i] < 0)
  46.             continue;
  47.  
  48.         cout << vertexNames[i] << " ";
  49.         for (int j = 0; j < matrixSize; j++)
  50.         {
  51.             if (vertexNames[j] >= 0)
  52.                 cout << adjacencyMatrix[i][j] << " ";
  53.         }
  54.         cout << "\n";
  55.     }
  56.     cout << "\n";
  57. }
  58.  
  59. int graph::searchVertex(int vertexName)
  60. {
  61.     int index = -1;
  62.     for (int i = 0; i < matrixSize; i++)
  63.         if (vertexNames[i] == vertexName)
  64.         {
  65.             index = i;
  66.             break;
  67.         }
  68.     return index;
  69. };
  70.  
  71. void graph::insertVertex(int vertexName)
  72. {
  73.     if (currentVertexNumber == matrixSize)
  74.     {
  75.         //cout << "Matrix is full\n";
  76.         return;
  77.     }
  78.  
  79.     if (searchVertex(vertexName) != -1)
  80.     {
  81.         //cout << "Vertex is already in the graph\n";
  82.         return;
  83.     }
  84.    
  85.     for (int i = 0; i < matrixSize; i++)
  86.         if (vertexNames[i] < 0)
  87.         {
  88.             vertexNames[i] = vertexName;
  89.             currentVertexNumber++;
  90.             return;
  91.         }
  92. }
  93.  
  94. void graph::insertEdge(int firstVertexName, int secondVertexName)
  95. {
  96.     if ((searchVertex(firstVertexName) != -1) && (searchVertex(secondVertexName) != -1))
  97.     {
  98.         adjacencyMatrix[searchVertex(firstVertexName)][searchVertex(secondVertexName)] = true;
  99.        
  100.         edgeNumber++;
  101.     }
  102.     else
  103.     {
  104.         /*if (searchVertex(firstName) == -1)
  105.             cout << "Vertex " << firstName << " is not in the graph\n";
  106.  
  107.         if (searchVertex(secondName) == -1)
  108.             cout << "Vertex " << secondName << " is not in the graph\n";*/
  109.     }
  110.     return;
  111. }
  112.  
  113. void graph::removeVertex(int vertexName)
  114. {
  115.     if (searchVertex(vertexName) != -1)
  116.     {
  117.         for (int i = 0; i < matrixSize; i++)
  118.             for (int j = 0; j < matrixSize; j++)
  119.             {
  120.                 if ((i == searchVertex(vertexName)) || (j == searchVertex(vertexName)))
  121.                     adjacencyMatrix[i][j] = 0;
  122.             }
  123.         vertexNames[searchVertex(vertexName)] = -1;
  124.         currentVertexNumber--;
  125.     }
  126.     /*else
  127.         cout << "There is no this vertex in the graph\n";*/
  128. }
  129.  
  130. void graph::removeEdge(int firstVertexName, int secondVertexName)
  131. {
  132.     if (searchVertex(firstVertexName) == -1)
  133.     {
  134.         //cout << "Vertex " << firstName << " is not in the graph\n";
  135.         return;
  136.     }
  137.  
  138.     if (searchVertex(secondVertexName) == -1)
  139.     {
  140.         //cout << "Vertex " << secondName << " is not in the graph\n";
  141.         return;
  142.     }
  143.  
  144.     adjacencyMatrix[searchVertex(firstVertexName)][searchVertex(secondVertexName)] = 0;
  145.    
  146. }
  147.  
  148. void graph::depthFirstSearch(int vertexName)
  149. {
  150.     bool *used = new bool[currentVertexNumber];
  151.     for (int i = 0; i < currentVertexNumber; i++)
  152.         used[i] = false;
  153.    
  154.     struct edge
  155.     {
  156.         int firstVertex, secondVertex;
  157.     };
  158.     edge *list = new edge[edgeNumber * 2];
  159.     int currentEdgeNumber = 0;
  160.  
  161.     int currentVertex;
  162.     currentVertex = vertexName;
  163.  
  164.     while (true)
  165.     {
  166.         used[searchVertex(currentVertex)] = true;
  167.  
  168.         for (int i = 0; i < currentVertexNumber; i++)
  169.         {
  170.             if (adjacencyMatrix[searchVertex(currentVertex)][i])
  171.             {
  172.                 list[currentEdgeNumber].firstVertex = currentVertex;
  173.                 list[currentEdgeNumber].secondVertex = vertexNames[i];
  174.                 currentEdgeNumber++;
  175.             }
  176.         }
  177.  
  178.         if (currentEdgeNumber > 0)
  179.         {
  180.             cout << currentVertex << " ";
  181.             for (int i = 0; i < currentEdgeNumber; i++)
  182.                 cout << "(" << list[i].firstVertex << ", " << list[i].secondVertex << ") ";
  183.             cout << endl;
  184.         }
  185.  
  186.         while (currentEdgeNumber > 0)
  187.         {
  188.             currentVertex = list[currentEdgeNumber - 1].secondVertex;
  189.             currentEdgeNumber--;
  190.             if (!used[searchVertex(currentVertex)])
  191.                 break;        
  192.         }
  193.  
  194.         if (currentEdgeNumber == 0)
  195.         {
  196.             int flag = false;
  197.             // проверка, что смежные вершины помечены
  198.             for (int i = 0; i < currentVertexNumber; i++)
  199.             {
  200.                 if (adjacencyMatrix[searchVertex(currentVertex)][i])
  201.                 {
  202.                     if (!used[i])
  203.                     {
  204.                         flag = true;
  205.                         break;
  206.                     }
  207.                     else
  208.                         continue;
  209.                 }
  210.             }
  211.  
  212.             if (flag)
  213.                 continue;
  214.             else
  215.             {
  216.                 if (!used[searchVertex(currentVertex)])
  217.                 {
  218.                     cout << currentVertex << " ";
  219.                     for (int i = 0; i < currentEdgeNumber; i++)
  220.                         cout << "(" << list[i].firstVertex << ", " << list[i].secondVertex << ") ";
  221.                     cout << endl;
  222.                 }
  223.                 break;
  224.             }
  225.         }
  226.     }
  227.  
  228.     delete[] list;
  229.     delete[] used;
  230. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top