fueanta

DFS [ Depth First Search ]

Nov 30th, 2017
137
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class DFS
  2. {
  3.     Graph* _graph;
  4.  
  5.     // properties
  6.     int* _parent;
  7.     int* _color;
  8.     int* _root;
  9.     int _cycleCount;
  10.  
  11.     // timing
  12.     int* _startTime;
  13.     int* _endTime;
  14.     int _globalTime;
  15.  
  16.     // topology
  17.     struct TopoNode
  18.     {
  19.         int value;
  20.         int endTime;
  21.     };
  22.     struct cmp
  23.     {
  24.         bool operator() (const TopoNode* left, const TopoNode* right) const
  25.         {
  26.             return left->endTime < right->endTime;
  27.         }
  28.     };
  29.     std::priority_queue<TopoNode*, vector<TopoNode*>, cmp>*
  30.         topological_queue;
  31.     int* _topological_list;
  32.  
  33.     void init();
  34.     void dfs_Visit(int, int);
  35.     void print_Cycle(int, int);
  36.  
  37.     // ssc
  38.     int stronglyConnectedComponents();
  39.     void scc_Visit(int, int);
  40. public:
  41.     DFS(Graph*);
  42.     ~DFS();
  43.  
  44.     void depthFirstSearch();
  45.     void print_TOL(); // topological order list
  46.     void print_SCC();
  47.     void print_Details();
  48. };
  49.  
  50. DFS::DFS(Graph * graph)
  51. {
  52.     this->_graph = graph;
  53.     this->init();
  54. }
  55.  
  56. DFS::~DFS()
  57. {
  58.     delete[] this->_color;
  59.     delete[] this->_root;
  60. //  delete[] this->_topological_list;
  61.  
  62.     delete[] this->_parent;
  63.     delete[] this->_startTime;
  64.     delete[] this->_endTime;
  65. //  delete this->topological_queue;
  66. }
  67.  
  68. void DFS::init()
  69. {
  70.     this->_parent = new int[this->_graph->getVertexCount()];
  71.     this->_color = new int[this->_graph->getVertexCount()];
  72.     this->_root = new int[this->_graph->getVertexCount()];
  73.     this->_startTime = new int[this->_graph->getVertexCount()];
  74.     this->_endTime = new int[this->_graph->getVertexCount()];
  75.     this->_topological_list = new int[this->_graph->getVertexCount()];
  76.  
  77.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  78.     {
  79.         this->_parent[i] = this->_color[i] = this->_root[i]
  80.             = this->_startTime[i] = this->_endTime[i] = -1;
  81.     }
  82.  
  83.     this->topological_queue
  84.         = new std::priority_queue<TopoNode*, vector<TopoNode*>, cmp>();
  85.     this->_globalTime = _cycleCount = 0;
  86. }
  87.  
  88. void DFS::depthFirstSearch()
  89. {
  90.     cout << "\nInitializing dfs...\n";
  91.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  92.     {
  93.         if (this->_color[i] == -1)
  94.         {
  95.             dfs_Visit(i, i);
  96.         }
  97.     }
  98.  
  99.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  100.     {
  101.         this->_topological_list[i] = this->topological_queue->top()->value;
  102.         this->topological_queue->pop();
  103.     }
  104.     delete this->topological_queue;
  105. }
  106.  
  107. void DFS::dfs_Visit(int componentHead, int node)
  108. {
  109.     this->_color[node] = 0;
  110.     this->_root[node] = componentHead;
  111.     this->_startTime[node] = ++this->_globalTime;
  112.  
  113.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  114.     {
  115.         if (this->_graph->hasEdgeBetween(node, i))
  116.         {
  117.             if (this->_color[i] == -1)
  118.             {
  119.                 this->_parent[i] = node;
  120.                 this->dfs_Visit(componentHead, i);
  121.             }
  122.             else if (this->_color[i] == 0)
  123.             {
  124.                 cout << "\nCycle " << ++this->_cycleCount << " : { ";
  125.                 this->print_Cycle(i, node);
  126.                 cout << " }" << endl;
  127.             }
  128.         }
  129.     }
  130.  
  131.     this->_color[node] = 1;
  132.     this->_endTime[node] = ++this->_globalTime;
  133.    
  134.     TopoNode* t_node = new TopoNode();
  135.     t_node->value = node; t_node->endTime = this->_globalTime;
  136.     this->topological_queue->push(t_node);
  137. }
  138.  
  139. void DFS::print_Cycle(int i, int j)
  140. {
  141.     if (i == j)
  142.         cout << i;
  143.     else
  144.     {
  145.         this->print_Cycle(i, this->_parent[j]);
  146.         cout << ", " << j;
  147.     }
  148. }
  149.  
  150. void DFS::print_TOL()
  151. {
  152.     cout << "\nTopological Ordered List : ";
  153.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  154.     {
  155.         cout << this->_topological_list[i] << " ";
  156.     }
  157.     cout << "\n--------------------------\n";
  158. }
  159.  
  160. int DFS::stronglyConnectedComponents()
  161. {
  162.     cout << "\nStrongly Connected Components:"
  163.          << "\n------------------------------\n";
  164.     int counter = 0;
  165.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  166.     {
  167.         int node = this->_topological_list[i];
  168.         if (this->_color[node] == -1)
  169.         {
  170.             cout << "Component " << ++counter << " : { " << node;
  171.             scc_Visit(node, node);
  172.             cout << " }" << endl;
  173.         }
  174.     }
  175.     return counter;
  176. }
  177.  
  178. void DFS::scc_Visit(int componentHead, int node)
  179. {
  180.     this->_color[node] = 0;
  181.     this->_root[node] = componentHead;
  182.  
  183.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  184.     {
  185.         if (this->_graph->hasEdgeBetween(node, i))
  186.         {
  187.             if (this->_color[i] == -1)
  188.             {
  189.                 cout << ", " << i;
  190.                 this->scc_Visit(componentHead, i);
  191.             }
  192.         }
  193.     }
  194. }
  195.  
  196. void DFS::print_SCC()
  197. {
  198.     DFS d(this->_graph->getTranspose_Matrix());
  199.     d._topological_list = this->_topological_list;
  200.     d.stronglyConnectedComponents();
  201. }
  202.  
  203. void DFS::print_Details()
  204. {
  205.     cout << "\nDetails:\n--------";
  206.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  207.     {
  208.         cout << "\nNode " << i << " ==> Parent-> " << this->_parent[i]
  209.             << ", Starts-> " << this->_startTime[i] << ", Ends-> "
  210.             << this->_endTime[i] << ", Root-> "
  211.             << this->_root[i] << endl;
  212.     }
  213. }
RAW Paste Data