00001 #ifndef BASICGRAPHALGORITHMS_H
00002 #define BASICGRAPHALGORITHMS_H
00003
00004 #include <Structs/Graphs/dynamicGraph.h>
00005 #include <queue>
00006
00007 template<class GraphType>
00008 class SearchVisitor
00009 {
00010 public:
00011
00012 typedef typename GraphType::NodeIterator node;
00013
00014 SearchVisitor()
00015 {
00016 }
00017
00018 virtual void visitOnInit()
00019 {
00020 }
00021
00022 virtual void visitOnFinding( const node& u)
00023 {
00024
00025 }
00026
00027 virtual void visitOnMarking( const node& u)
00028 {
00029
00030 }
00031
00032 virtual void visitOnExit()
00033 {
00034 }
00035 };
00036
00046 template<class GraphType>
00047 void bfsCore( GraphType& G, typename GraphType::NodeIterator& root, SearchVisitor<GraphType>* visitor = 0)
00048 {
00049 typedef typename GraphType::NodeIterator node;
00050 typedef typename GraphType::EdgeIterator edge;
00051 typedef typename GraphType::SizeType SizeType;
00052 typedef typename GraphType::NodeData NodeData;
00053
00054 node u,v;
00055 edge e,end;
00056 std::queue<node> Q;
00057 Q.push(root);
00058
00059 visitor->visitOnInit();
00060
00061 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00062
00063 root->marked = true;
00064
00065 while( !Q.empty())
00066 {
00067 u = Q.front();
00068 Q.pop();
00069
00070 for( e = G.beginEdges(u), end = G.endEdges(u); e != end; ++e)
00071 {
00072 v = G.target( e);
00073 if( ! v->marked)
00074 {
00075 visitor->visitOnMarking(v);
00076 v->marked = true;
00077 Q.push(v);
00078 }
00079 }
00080 }
00081
00082 visitor->visitOnExit();
00083 }
00084
00085
00095 template<class GraphType>
00096 void reverseBfsCore( GraphType& G, typename GraphType::NodeIterator& root, SearchVisitor<GraphType>* visitor = 0)
00097 {
00098 typedef typename GraphType::NodeIterator node;
00099 typedef typename GraphType::EdgeIterator edge;
00100 typedef typename GraphType::SizeType SizeType;
00101 typedef typename GraphType::NodeData NodeData;
00102
00103 node u,v;
00104 edge e,end;
00105 std::queue<node> Q;
00106 Q.push(root);
00107
00108 visitor->visitOnInit();
00109
00110 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00111
00112 root->marked = true;
00113
00114 while( !Q.empty())
00115 {
00116 u = Q.front();
00117 Q.pop();
00118
00119 for( e = G.beginBackEdges(u), end = G.endBackEdges(u); e != end; ++e)
00120 {
00121 v = G.source( e);
00122 if( ! v->marked)
00123 {
00124 visitor->visitOnMarking(v);
00125 v->marked = true;
00126 Q.push(v);
00127 }
00128 }
00129 }
00130
00131 visitor->visitOnExit();
00132 }
00133
00134
00144 template<class GraphType>
00145 void undirectedBfsCore( GraphType& G, typename GraphType::NodeIterator& root, SearchVisitor<GraphType>* visitor = 0)
00146 {
00147 typedef typename GraphType::NodeIterator node;
00148 typedef typename GraphType::EdgeIterator edge;
00149 typedef typename GraphType::BackEdgeIterator backEdge;
00150 typedef typename GraphType::SizeType SizeType;
00151 typedef typename GraphType::NodeData NodeData;
00152
00153 node u,v;
00154 edge e,end;
00155 backEdge k,kEnd;
00156 std::queue<node> Q;
00157 Q.push(root);
00158
00159 bool status = false;
00160
00161 visitor->visitOnInit();
00162
00163 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00164
00165 root->marked = true;
00166
00167 while( !Q.empty())
00168 {
00169 u = Q.front();
00170 Q.pop();
00171
00172 status = false;
00173
00174 for( e = G.beginEdges(u), end = G.endEdges(u); e != end; ++e)
00175 {
00176 status = true;
00177 v = G.target( e);
00178 if( ! v->marked)
00179 {
00180 visitor->visitOnMarking(v);
00181 v->marked = true;
00182 Q.push(v);
00183 }
00184 }
00185
00186 for( k = G.beginBackEdges(u), kEnd = G.endBackEdges(u); k != kEnd; ++k)
00187 {
00188 status = true;
00189 v = G.source( k);
00190 if( ! v->marked)
00191 {
00192 visitor->visitOnMarking(v);
00193 v->marked = true;
00194 Q.push(v);
00195 }
00196 }
00197 }
00198
00199 visitor->visitOnExit();
00200 }
00201
00202
00212 template<class GraphType>
00213 void dfsCore( GraphType& G, typename GraphType::NodeIterator& root, SearchVisitor<GraphType>* visitor = 0)
00214 {
00215 typedef typename GraphType::NodeIterator node;
00216 typedef typename GraphType::EdgeIterator edge;
00217 typedef typename GraphType::SizeType SizeType;
00218 typedef typename GraphType::NodeData NodeData;
00219
00220 node u,v;
00221 edge e,end;
00222 std::stack<node> S;
00223 S.push(root);
00224
00225 visitor->visitOnInit();
00226
00227 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00228
00229 root->marked = true;
00230
00231 while( !S.empty())
00232 {
00233 u = S.top();
00234 S.pop();
00235
00236 for( e = G.beginEdges(u), end = G.endEdges(u); e != end; ++e)
00237 {
00238 v = G.target( e);
00239 if( ! v->marked)
00240 {
00241 visitor->visitOnMarking(v);
00242 v->marked = true;
00243 S.push(v);
00244 }
00245 }
00246 }
00247
00248 visitor->visitOnExit();
00249 }
00250
00251
00261 template<class GraphType>
00262 void reverseDfsCore( GraphType& G, typename GraphType::NodeIterator& root, SearchVisitor<GraphType>* visitor = 0)
00263 {
00264 typedef typename GraphType::NodeIterator node;
00265 typedef typename GraphType::EdgeIterator edge;
00266 typedef typename GraphType::SizeType SizeType;
00267 typedef typename GraphType::NodeData NodeData;
00268
00269 node u,v;
00270 edge e,end;
00271 std::stack<node> S;
00272 S.push(root);
00273
00274 visitor->visitOnInit();
00275
00276 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00277
00278 root->marked = true;
00279
00280 while( !S.empty())
00281 {
00282 u = S.top();
00283 S.pop();
00284
00285 for( e = G.beginBackEdges(u), end = G.endBackEdges(u); e != end; ++e)
00286 {
00287 v = G.source( e);
00288 if( ! v->marked)
00289 {
00290 visitor->visitOnMarking(v);
00291 v->marked = true;
00292 S.push(v);
00293 }
00294 }
00295 }
00296
00297 visitor->visitOnExit();
00298 }
00299
00309 template<class GraphType>
00310 void undirectedDfsCore( GraphType& G, typename GraphType::NodeIterator& root, SearchVisitor<GraphType>* visitor = 0)
00311 {
00312 typedef typename GraphType::NodeIterator node;
00313 typedef typename GraphType::EdgeIterator edge;
00314 typedef typename GraphType::SizeType SizeType;
00315 typedef typename GraphType::NodeData NodeData;
00316
00317 node u,v;
00318 edge e,end;
00319 std::stack<node> S;
00320 S.push(root);
00321
00322 visitor->visitOnInit();
00323
00324 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00325
00326 root->marked = true;
00327
00328 while( !S.empty())
00329 {
00330 u = S.top();
00331 S.pop();
00332
00333 for( e = G.beginEdges(u), end = G.endEdges(u); e != end; ++e)
00334 {
00335 v = G.target( e);
00336 if( ! v->marked)
00337 {
00338 visitor->visitOnMarking(v);
00339 v->marked = true;
00340 S.push(v);
00341 }
00342 }
00343
00344 for( e = G.beginBackEdges(u), end = G.endBackEdges(u); e != end; ++e)
00345 {
00346 v = G.source( e);
00347 if( ! v->marked)
00348 {
00349 visitor->visitOnMarking(v);
00350 v->marked = true;
00351 S.push(v);
00352 }
00353 }
00354 }
00355
00356 visitor->visitOnExit();
00357 }
00358
00359
00360 template<class GraphType>
00361 unsigned int findStronglyConnectedComponents( GraphType& G)
00362 {
00363 typedef typename GraphType::NodeIterator node;
00364 typedef typename GraphType::EdgeIterator edge;
00365 typedef typename GraphType::BackEdgeIterator backEdge;
00366 typedef typename GraphType::SizeType SizeType;
00367 typedef typename GraphType::NodeData NodeData;
00368
00369 node u,v;
00370 edge e,end;
00371 backEdge k,kEnd;
00372 std::stack<node> S;
00373 std::stack<node> discovered;
00374 unsigned int component = 0;
00375
00376 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u)
00377 {
00378 u->marked = false;
00379 }
00380
00381
00382
00383
00384
00385 while( discovered.size() != G.getNumNodes())
00386 {
00387 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u)
00388 if( !u->marked)
00389 break;
00390
00391
00392
00393 u->marked = true;
00394 discovered.push(u);
00395 S.push(u);
00396
00397 while( !S.empty())
00398 {
00399 u = S.top();
00400 S.pop();
00401
00402
00403
00404 for( e = G.beginEdges(u), end = G.endEdges(u); e != end; ++e)
00405 {
00406 v = G.target( e);
00407 if( ! v->marked)
00408 {
00409 v->marked = true;
00410 S.push(v);
00411 discovered.push(v);
00412 }
00413 }
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426 }
00427 }
00428
00429 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u) u->marked = false;
00430
00431 while( !discovered.empty())
00432 {
00433 u = discovered.top();
00434 discovered.pop();
00435
00436 if( u->marked)
00437 {
00438 continue;
00439 }
00440 component++;
00441 S.push(u);
00442 u->marked = true;
00443
00444 while( !S.empty())
00445 {
00446 u = S.top();
00447 S.pop();
00448
00449 for( k = G.beginBackEdges(u), kEnd = G.endBackEdges(u); k != kEnd; ++k)
00450 {
00451 v = G.source(k);
00452 if( ! v->marked)
00453 {
00454 v->marked = true;
00455 S.push(v);
00456 v->component = component;
00457 }
00458 }
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470 }
00471 }
00472
00473 return component;
00474 }
00475
00476
00484 template<class GraphType>
00485 bool isConnected( GraphType& G)
00486 {
00487 typedef typename GraphType::NodeIterator node;
00488 typedef typename GraphType::EdgeIterator edge;
00489 typedef typename GraphType::SizeType SizeType;
00490 typedef typename GraphType::NodeData NodeData;
00491
00492 class Visitor : public SearchVisitor<GraphType>
00493 {
00494 public:
00495 Visitor():m_numNodes(1){}
00496
00497 const SizeType& getNumNodes()
00498 {
00499 return m_numNodes;
00500 }
00501
00502 virtual void visitOnMarking( const node& u)
00503 {
00504
00505 ++m_numNodes;
00506 }
00507
00508 SizeType m_numNodes;
00509 };
00510
00511 Visitor vis;
00512 node s = G.chooseNode();
00513 bfsCore( G, s, &vis);
00514 return vis.getNumNodes() == G.getNumNodes();
00515 }
00516
00517
00525 template<class GraphType>
00526 bool isWeaklyConnected( GraphType& G)
00527 {
00528 typedef typename GraphType::NodeIterator node;
00529 typedef typename GraphType::EdgeIterator edge;
00530 typedef typename GraphType::SizeType SizeType;
00531 typedef typename GraphType::NodeData NodeData;
00532
00533 class Visitor : public SearchVisitor<GraphType>
00534 {
00535 public:
00536 Visitor():m_numNodes(1){}
00537
00538 const SizeType& getNumNodes()
00539 {
00540 return m_numNodes;
00541 }
00542
00543 virtual void visitOnMarking( const node& u)
00544 {
00545
00546 ++m_numNodes;
00547 }
00548
00549 SizeType m_numNodes;
00550 };
00551
00552 Visitor vis;
00553 node s = G.chooseNode();
00554 undirectedBfsCore( G, s, &vis);
00555 return vis.getNumNodes() == G.getNumNodes();
00556 }
00557
00558
00559 template<class GraphType>
00560 bool topologicalSort( GraphType& G)
00561 {
00562 return true;
00563 }
00564
00565
00566 template<class GraphType>
00567 void removeNodesOfDegree2( GraphType& G)
00568 {
00569 typedef typename GraphType::NodeIterator NodeIterator;
00570 typedef typename GraphType::NodeDescriptor NodeDescriptor;
00571 typedef typename GraphType::EdgeIterator EdgeIterator;
00572 typedef typename GraphType::BackEdgeIterator BackEdgeIterator;
00573 typedef typename GraphType::EdgeDescriptor EdgeDescriptor;
00574 typedef typename GraphType::SizeType SizeType;
00575 typedef typename GraphType::NodeData NodeData;
00576
00577 NodeIterator u, v, w, lastnode;
00578 NodeDescriptor uD, vD, wD;
00579 EdgeIterator e, e1, e2, lastedge;
00580 EdgeDescriptor eD, e1D, e2D;
00581 BackEdgeIterator k, lastbackedge;
00582
00583 unsigned int sum = 0;
00584
00585 std::vector<NodeDescriptor> toBeRemoved;
00586
00587
00588 for( u = G.beginNodes(), lastnode = G.endNodes(); u != lastnode; ++u)
00589 {
00590 if( (G.outdeg(u) == 2) && (G.indeg(u) == 2))
00591 {
00592 uD = G.getNodeDescriptor( u);
00593 e = G.beginEdges(u);
00594 v = G.target(e);
00595 vD = G.getNodeDescriptor( v);
00596
00597 ++e;
00598 w = G.target(e);
00599 wD = G.getNodeDescriptor( w);
00600
00601 if( G.hasEdge( v, u) && G.hasEdge(u,w) && G.hasEdge( w, u) && G.hasEdge(u,v))
00602 {
00603 ++sum;
00604 u->toBeRemoved = true;
00605 toBeRemoved.push_back( G.getNodeDescriptor(u));
00606 }
00607 }
00608 }
00609
00610
00611 NodeIterator root;
00612 std::stack<NodeIterator> S;
00613
00614 for( u = G.beginNodes(), v = G.endNodes(); u != v; ++u)
00615 {
00616 if( !u->toBeRemoved) root = u;
00617 u->marked = false;
00618 }
00619
00620 S.push(root);
00621 root->marked = true;
00622 root->pred = G.getNodeDescriptor(root);
00623
00624 while( !S.empty())
00625 {
00626 u = S.top();
00627 S.pop();
00628
00629 for( e = G.beginEdges(u), lastedge = G.endEdges(u); e != lastedge; ++e)
00630 {
00631 v = G.target( e);
00632 if( ! v->marked)
00633 {
00634 v->marked = true;
00635 S.push(v);
00636 u->toBeRemoved ? v->pred = u->pred : v->pred = G.getNodeDescriptor(u);
00637 v->toBeRemoved ? v->dist = u->dist + e->weight : u->dist = 0;
00638 }
00639 }
00640 }
00641
00642 for( u = G.beginNodes(), lastnode = G.endNodes(); u != lastnode; ++u)
00643 {
00644 v = G.getNodeIterator( (NodeDescriptor)u->pred);
00645 if( u == v) continue;
00646 assert( !v->toBeRemoved);
00647 e = G.getEdgeIterator( G.insertEdge( G.getNodeDescriptor(v), G.getNodeDescriptor(u)));
00648 e->weight = u->dist;
00649 e = G.getEdgeIterator( G.insertEdge( G.getNodeDescriptor(u), G.getNodeDescriptor(v)));
00650 e->weight = u->dist;
00651 }
00652
00653 std::cout << "Number of nodes with degree 2 is " << sum << std::endl;
00654
00655 }
00656
00657
00668 template < class FirstGraphType, class SecondGraphType>
00669 int compare( const FirstGraphType& first, const SecondGraphType& second)
00670 {
00671 typename FirstGraphType::NodeIterator f_u,f_end_nodes;
00672 typename FirstGraphType::EdgeIterator f_e,f_end_edges;
00673 typename SecondGraphType::NodeIterator s_u, s_end_nodes;
00674 typename SecondGraphType::EdgeIterator s_e,s_end_edges;
00675
00676 bool foundNode,foundEdge;
00677
00678 std::cout << "\nForward..." << std::flush;
00679 for( f_u = first.beginNodes(), f_end_nodes = first.endNodes(); f_u != f_end_nodes; ++f_u)
00680 {
00681 foundNode = false;
00682 for( s_u = second.beginNodes(), s_end_nodes = second.endNodes(); s_u != s_end_nodes; ++s_u)
00683 {
00684 if( second.getId(s_u) == first.getId(f_u))
00685 {
00686 foundNode = true;
00687 for( f_e = first.beginEdges(f_u), f_end_edges = first.endEdges(f_u); f_e != f_end_edges; ++f_e)
00688 {
00689 foundEdge = false;
00690 for( s_e = second.beginEdges(s_u), s_end_edges = second.endEdges(s_u); s_e != s_end_edges; ++s_e)
00691 {
00692 if( second.getId(s_e) == first.getId(f_e))
00693 {
00694 foundEdge = true;
00695 }
00696 }
00697 if( !foundEdge) return -1;
00698 }
00699 }
00700 }
00701 if( !foundNode) return -1;
00702 }
00703 std::cout << "done!\nBackward..." << std::flush;
00704 for( s_u = second.beginNodes(), s_end_nodes = second.endNodes(); s_u != s_end_nodes; ++s_u)
00705 {
00706 foundNode = false;
00707 for( f_u = first.beginNodes(), f_end_nodes = first.endNodes(); f_u != f_end_nodes; ++f_u)
00708 {
00709 if( second.getId(s_u->getId) == first.getId(f_u))
00710 {
00711 foundNode = true;
00712 for( s_e = second.beginEdges(s_u), s_end_edges = second.endEdges(s_u); s_e != s_end_edges; ++s_e)
00713 {
00714 foundEdge = false;
00715 for( f_e = first.beginEdges(f_u), f_end_edges = first.endEdges(f_u); f_e != f_end_edges; ++f_e)
00716 {
00717 if( second.getId(s_e) == first.getId(f_e))
00718 {
00719 foundEdge = true;
00720 }
00721 }
00722 if( !foundEdge) return -1;
00723 }
00724 }
00725 }
00726 if( !foundNode) return 1;
00727 }
00728 std::cout << "done!\n" << std::flush;
00729 return 0;
00730 }
00731
00732
00733 #endif // BASICGRAPHALGORITHMS_H