Changeset 1750:5c76ebbb4818 in lemon0.x for lemon
 Timestamp:
 11/02/05 16:23:46 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2279
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/topology.h
r1740 r1750 21 21 #include <lemon/bfs.h> 22 22 #include <lemon/graph_utils.h> 23 #include <lemon/graph_adaptor.h> 24 #include <lemon/maps.h> 23 25 24 26 #include <lemon/concept/graph.h> … … 26 28 #include <lemon/concept_check.h> 27 29 28 /// \ingroup flowalgs 30 #include <lemon/bin_heap.h> 31 #include <lemon/linear_heap.h> 32 33 #include <stack> 34 #include <functional> 35 36 /// \ingroup topology 29 37 /// \file 30 38 /// \brief Topology related algorithms 31 39 /// 32 40 /// Topology related algorithms 33 ///\todo Place the file contents is the module tree.34 41 35 42 namespace lemon { 36 43 44 /// \ingroup topology 45 /// 46 /// \brief Check that the given undirected graph is connected. 47 /// 48 /// Check that the given undirected graph connected. 49 /// \param graph The undirected graph. 50 /// \return %True when there is path between any two nodes in the graph. 51 /// \warning The empty graph is not connected. 52 template <typename UndirGraph> 53 bool connected(const UndirGraph& graph) { 54 checkConcept<concept::UndirGraph, UndirGraph>(); 55 typedef typename UndirGraph::NodeIt NodeIt; 56 if (NodeIt(graph) == INVALID) return false; 57 Dfs<UndirGraph> dfs(graph); 58 dfs.run(NodeIt(graph)); 59 for (NodeIt it(graph); it != INVALID; ++it) { 60 if (!dfs.reached(it)) { 61 return false; 62 } 63 } 64 return true; 65 } 66 67 /// \ingroup topology 68 /// 69 /// \brief Count the number of connected components of an undirected graph 70 /// 71 /// Count the number of connected components of an undirected graph 72 /// 73 /// \param g The graph. In must be undirected. 74 /// \return The number of components 75 template <typename UndirGraph> 76 int countConnectedComponents(const UndirGraph &graph) { 77 checkConcept<concept::UndirGraph, UndirGraph>(); 78 typedef typename UndirGraph::Node Node; 79 typedef typename UndirGraph::Edge Edge; 80 81 typedef NullMap<Node, Edge> PredMap; 82 typedef NullMap<Node, int> DistMap; 83 84 int compNum = 0; 85 typename Bfs<UndirGraph>:: 86 template DefPredMap<PredMap>:: 87 template DefDistMap<DistMap>:: 88 Create bfs(graph); 89 90 PredMap predMap; 91 bfs.predMap(predMap); 92 93 DistMap distMap; 94 bfs.distMap(distMap); 95 96 bfs.init(); 97 for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) { 98 if (!bfs.reached(n)) { 99 bfs.addSource(n); 100 bfs.start(); 101 ++compNum; 102 } 103 } 104 return compNum; 105 } 106 107 /// \ingroup topology 108 /// 109 /// \brief Find the connected components of an undirected graph 110 /// 111 /// Find the connected components of an undirected graph. 112 /// 113 /// \param g The graph. In must be undirected. 114 /// \retval comp A writable node map. The values will be set from 0 to 115 /// the number of the connected components minus one. Each values of the map 116 /// will be set exactly once, the values of a certain component will be 117 /// set continuously. 118 /// \return The number of components 119 template <class UndirGraph, class NodeMap> 120 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { 121 checkConcept<concept::UndirGraph, UndirGraph>(); 122 typedef typename UndirGraph::Node Node; 123 typedef typename UndirGraph::Edge Edge; 124 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); 125 126 typedef NullMap<Node, Edge> PredMap; 127 typedef NullMap<Node, int> DistMap; 128 129 int compNum = 0; 130 typename Bfs<UndirGraph>:: 131 template DefPredMap<PredMap>:: 132 template DefDistMap<DistMap>:: 133 Create bfs(graph); 134 135 PredMap predMap; 136 bfs.predMap(predMap); 137 138 DistMap distMap; 139 bfs.distMap(distMap); 140 141 bfs.init(); 142 for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) { 143 if(!bfs.reached(n)) { 144 bfs.addSource(n); 145 while (!bfs.emptyQueue()) { 146 compMap.set(bfs.nextNode(), compNum); 147 bfs.processNextNode(); 148 } 149 ++compNum; 150 } 151 } 152 return compNum; 153 } 154 37 155 namespace _topology_bits { 38 39 template <typename NodeMap>40 class BackCounterMap{156 157 template <typename Graph, typename Iterator > 158 struct LeaveOrderVisitor : public DfsVisitor<Graph> { 41 159 public: 42 BackCounterMap(NodeMap& _nodeMap, int _counter) 43 : nodeMap(_nodeMap), counter(_counter) {} 44 45 void set(typename NodeMap::Key key, bool val) { 46 if (val) { 47 nodeMap.set(key, counter); 48 } else { 49 nodeMap.set(key, 1); 50 } 51 } 52 53 bool operator[](typename NodeMap::Key key) const { 54 return nodeMap[key] != 1; 160 typedef typename Graph::Node Node; 161 LeaveOrderVisitor(Iterator it) : _it(it) {} 162 163 void leave(const Node& node) { 164 *(_it++) = node; 55 165 } 56 166 57 167 private: 58 NodeMap& nodeMap; 59 int counter; 168 Iterator _it; 60 169 }; 61 } 62 63 // \todo Its to special output // ReadWriteMap 170 171 template <typename Graph, typename Map> 172 struct FillMapVisitor : public DfsVisitor<Graph> { 173 public: 174 typedef typename Graph::Node Node; 175 typedef typename Map::Value Value; 176 177 FillMapVisitor(Map& map, Value& value) 178 : _map(map), _value(value) {} 179 180 void reach(const Node& node) { 181 _map.set(node, _value); 182 } 183 private: 184 Map& _map; 185 Value& _value; 186 }; 187 188 template <typename Graph, typename EdgeMap> 189 struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> { 190 public: 191 typedef typename Graph::Node Node; 192 typedef typename Graph::Edge Edge; 193 194 StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap, 195 int& cutNum) 196 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 197 _compMap(graph), _num(0) { 198 } 199 200 void stop(const Node&) { 201 ++_num; 202 } 203 204 void reach(const Node& node) { 205 _compMap.set(node, _num); 206 } 207 208 void examine(const Edge& edge) { 209 if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) { 210 _cutMap.set(edge, true); 211 ++_cutNum; 212 } 213 } 214 private: 215 const Graph& _graph; 216 EdgeMap& _cutMap; 217 int& _cutNum; 218 219 typename Graph::template NodeMap<int> _compMap; 220 int _num; 221 }; 222 223 } 224 225 226 /// \ingroup topology 227 /// 228 /// \brief Check that the given directed graph is strongly connected. 229 /// 230 /// Check that the given directed graph is strongly connected. The 231 /// graph is strongly connected when any two nodes of the graph are 232 /// connected with directed pathes in both direction. 233 /// \return %False when the graph is not strongly connected. 234 /// \see connected 235 /// 236 /// \waning Empty graph is not strongly connected. 237 template <typename Graph> 238 bool stronglyConnected(const Graph& graph) { 239 checkConcept<concept::StaticGraph, Graph>(); 240 if (NodeIt(graph) == INVALID) return false; 241 242 typedef typename Graph::Node Node; 243 typedef typename Graph::NodeIt NodeIt; 244 245 using namespace _topology_bits; 246 247 typedef DfsVisitor<Graph> Visitor; 248 Visitor visitor; 249 250 DfsVisit<Graph, Visitor> dfs(graph, visitor); 251 dfs.init(); 252 dfs.addSource(NodeIt(graph)); 253 dfs.start(); 254 255 for (NodeIt it(graph); it != INVALID; ++it) { 256 if (!dfs.reached(it)) { 257 return false; 258 } 259 } 260 261 typedef RevGraphAdaptor<const Graph> RGraph; 262 RGraph rgraph(graph); 263 264 typedef DfsVisitor<Graph> RVisitor; 265 RVisitor rvisitor; 266 267 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor); 268 rdfs.init(); 269 rdfs.addSource(NodeIt(graph)); 270 rdfs.start(); 271 272 for (NodeIt it(graph); it != INVALID; ++it) { 273 if (!rdfs.reached(it)) { 274 return false; 275 } 276 } 277 278 return true; 279 } 280 281 /// \ingroup topology 282 /// 283 /// \brief Count the strongly connected components of a directed graph 284 /// 285 /// Count the strongly connected components of a directed graph. 286 /// The strongly connected components are the classes of an equivalence 287 /// relation on the nodes of the graph. Two nodes are connected with 288 /// directed paths in both direction. 289 /// 290 /// \param g The graph. 291 /// \return The number of components 292 template <typename Graph> 293 int countStronglyConnectedComponents(const Graph& graph) { 294 checkConcept<concept::StaticGraph, Graph>(); 295 296 using namespace _topology_bits; 297 298 typedef typename Graph::Node Node; 299 typedef typename Graph::Edge Edge; 300 typedef typename Graph::NodeIt NodeIt; 301 typedef typename Graph::EdgeIt EdgeIt; 302 303 typedef std::vector<Node> Container; 304 typedef typename Container::iterator Iterator; 305 306 Container nodes(countNodes(graph)); 307 typedef LeaveOrderVisitor<Graph, Iterator> Visitor; 308 Visitor visitor(nodes.begin()); 309 310 DfsVisit<Graph, Visitor> dfs(graph, visitor); 311 dfs.init(); 312 for (NodeIt it(graph); it != INVALID; ++it) { 313 if (!dfs.reached(it)) { 314 dfs.addSource(it); 315 dfs.start(); 316 } 317 } 318 319 typedef typename Container::reverse_iterator RIterator; 320 typedef RevGraphAdaptor<const Graph> RGraph; 321 322 RGraph rgraph(graph); 323 324 typedef DfsVisitor<Graph> RVisitor; 325 RVisitor rvisitor; 326 327 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor); 328 329 int compNum = 0; 330 331 rdfs.init(); 332 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { 333 if (!rdfs.reached(*it)) { 334 rdfs.addSource(*it); 335 rdfs.start(); 336 ++compNum; 337 } 338 } 339 return compNum; 340 } 341 342 /// \ingroup topology 343 /// 344 /// \brief Find the strongly connected components of a directed graph 345 /// 346 /// Find the strongly connected components of a directed graph. 347 /// The strongly connected components are the classes of an equivalence 348 /// relation on the nodes of the graph. Two nodes are in relationship 349 /// when there are directed paths between them in both direction. 350 /// 351 /// \param g The graph. 352 /// \retval comp A writable node map. The values will be set from 0 to 353 /// the number of the strongly connected components minus one. Each values 354 /// of the map will be set exactly once, the values of a certain component 355 /// will be set continuously. 356 /// \return The number of components 64 357 template <typename Graph, typename NodeMap> 65 bool topological_sort(const Graph& graph, NodeMap& nodeMap) { 358 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) { 359 checkConcept<concept::StaticGraph, Graph>(); 360 typedef typename Graph::Node Node; 361 typedef typename Graph::NodeIt NodeIt; 362 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); 363 66 364 using namespace _topology_bits; 67 365 366 typedef std::vector<Node> Container; 367 typedef typename Container::iterator Iterator; 368 369 Container nodes(countNodes(graph)); 370 typedef LeaveOrderVisitor<Graph, Iterator> Visitor; 371 Visitor visitor(nodes.begin()); 372 373 DfsVisit<Graph, Visitor> dfs(graph, visitor); 374 dfs.init(); 375 for (NodeIt it(graph); it != INVALID; ++it) { 376 if (!dfs.reached(it)) { 377 dfs.addSource(it); 378 dfs.start(); 379 } 380 } 381 382 typedef typename Container::reverse_iterator RIterator; 383 typedef RevGraphAdaptor<const Graph> RGraph; 384 385 RGraph rgraph(graph); 386 387 int compNum = 0; 388 389 typedef FillMapVisitor<RGraph, NodeMap> RVisitor; 390 RVisitor rvisitor(compMap, compNum); 391 392 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor); 393 394 rdfs.init(); 395 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { 396 if (!rdfs.reached(*it)) { 397 rdfs.addSource(*it); 398 rdfs.start(); 399 ++compNum; 400 } 401 } 402 return compNum; 403 } 404 405 /// \ingroup topology 406 /// 407 /// \brief Find the cut edges of the strongly connected components. 408 /// 409 /// Find the cut edges of the strongly connected components. 410 /// The strongly connected components are the classes of an equivalence 411 /// relation on the nodes of the graph. Two nodes are in relationship 412 /// when there are directed paths between them in both direction. 413 /// The strongly connected components are separated by the cut edges. 414 /// 415 /// \param g The graph. 416 /// \retval comp A writable edge map. The values will be set true when 417 /// the edge is cut edge otherwise false. 418 /// 419 /// \return The number of cut edges 420 template <typename Graph, typename EdgeMap> 421 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { 68 422 checkConcept<concept::StaticGraph, Graph>(); 69 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>(); 423 typedef typename Graph::Node Node; 424 typedef typename Graph::Edge Edge; 425 typedef typename Graph::NodeIt NodeIt; 426 checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>(); 427 428 using namespace _topology_bits; 429 430 typedef std::vector<Node> Container; 431 typedef typename Container::iterator Iterator; 432 433 Container nodes(countNodes(graph)); 434 typedef LeaveOrderVisitor<Graph, Iterator> Visitor; 435 Visitor visitor(nodes.begin()); 436 437 DfsVisit<Graph, Visitor> dfs(graph, visitor); 438 dfs.init(); 439 for (NodeIt it(graph); it != INVALID; ++it) { 440 if (!dfs.reached(it)) { 441 dfs.addSource(it); 442 dfs.start(); 443 } 444 } 445 446 typedef typename Container::reverse_iterator RIterator; 447 typedef RevGraphAdaptor<const Graph> RGraph; 448 449 RGraph rgraph(graph); 450 451 int cutNum = 0; 452 453 typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor; 454 RVisitor rvisitor(rgraph, cutMap, cutNum); 455 456 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor); 457 458 rdfs.init(); 459 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { 460 if (!rdfs.reached(*it)) { 461 rdfs.addSource(*it); 462 rdfs.start(); 463 } 464 } 465 return cutNum; 466 } 467 468 namespace _topology_bits { 469 470 template <typename Graph> 471 class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { 472 public: 473 typedef typename Graph::Node Node; 474 typedef typename Graph::Edge Edge; 475 typedef typename Graph::UndirEdge UndirEdge; 476 477 CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 478 : _graph(graph), _compNum(compNum), 479 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 480 481 void start(const Node& node) { 482 _predMap.set(node, INVALID); 483 } 484 485 void reach(const Node& node) { 486 _numMap.set(node, _num); 487 _retMap.set(node, _num); 488 ++_num; 489 } 490 491 void discover(const Edge& edge) { 492 _predMap.set(_graph.target(edge), _graph.source(edge)); 493 } 494 495 void examine(const Edge& edge) { 496 if (_graph.source(edge) == _graph.target(edge) && 497 _graph.direction(edge)) { 498 ++_compNum; 499 return; 500 } 501 if (_predMap[_graph.source(edge)] == _graph.target(edge)) { 502 return; 503 } 504 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { 505 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); 506 } 507 } 508 509 void backtrack(const Edge& edge) { 510 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 511 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 512 } 513 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { 514 ++_compNum; 515 } 516 } 517 518 private: 519 const Graph& _graph; 520 int& _compNum; 521 522 typename Graph::template NodeMap<int> _numMap; 523 typename Graph::template NodeMap<int> _retMap; 524 typename Graph::template NodeMap<Node> _predMap; 525 int _num; 526 }; 527 528 template <typename Graph, typename EdgeMap> 529 class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { 530 public: 531 typedef typename Graph::Node Node; 532 typedef typename Graph::Edge Edge; 533 typedef typename Graph::UndirEdge UndirEdge; 534 535 NodeBiconnectedComponentsVisitor(const Graph& graph, 536 EdgeMap& compMap, int &compNum) 537 : _graph(graph), _compMap(compMap), _compNum(compNum), 538 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 539 540 void start(const Node& node) { 541 _predMap.set(node, INVALID); 542 } 543 544 void reach(const Node& node) { 545 _numMap.set(node, _num); 546 _retMap.set(node, _num); 547 ++_num; 548 } 549 550 void discover(const Edge& edge) { 551 Node target = _graph.target(edge); 552 _predMap.set(target, edge); 553 _edgeStack.push(edge); 554 } 555 556 void examine(const Edge& edge) { 557 Node source = _graph.source(edge); 558 Node target = _graph.target(edge); 559 if (source == target && _graph.direction(edge)) { 560 _compMap.set(edge, _compNum); 561 ++_compNum; 562 return; 563 } 564 if (_numMap[target] < _numMap[source]) { 565 if (_predMap[source] != _graph.oppositeEdge(edge)) { 566 _edgeStack.push(edge); 567 } 568 } 569 if (_predMap[source] != INVALID && 570 target == _graph.source(_predMap[source])) { 571 return; 572 } 573 if (_retMap[source] > _numMap[target]) { 574 _retMap.set(source, _numMap[target]); 575 } 576 } 577 578 void backtrack(const Edge& edge) { 579 Node source = _graph.source(edge); 580 Node target = _graph.target(edge); 581 if (_retMap[source] > _retMap[target]) { 582 _retMap.set(source, _retMap[target]); 583 } 584 if (_numMap[source] <= _retMap[target]) { 585 while (_edgeStack.top() != edge) { 586 _compMap.set(_edgeStack.top(), _compNum); 587 _edgeStack.pop(); 588 } 589 _compMap.set(edge, _compNum); 590 _edgeStack.pop(); 591 ++_compNum; 592 } 593 } 594 595 private: 596 const Graph& _graph; 597 EdgeMap& _compMap; 598 int& _compNum; 599 600 typename Graph::template NodeMap<int> _numMap; 601 typename Graph::template NodeMap<int> _retMap; 602 typename Graph::template NodeMap<Edge> _predMap; 603 std::stack<UndirEdge> _edgeStack; 604 int _num; 605 }; 606 607 608 template <typename Graph, typename NodeMap> 609 class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> { 610 public: 611 typedef typename Graph::Node Node; 612 typedef typename Graph::Edge Edge; 613 typedef typename Graph::UndirEdge UndirEdge; 614 615 NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, 616 int& cutNum) 617 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 618 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 619 620 void start(const Node& node) { 621 _predMap.set(node, INVALID); 622 rootCut = false; 623 } 624 625 void reach(const Node& node) { 626 _numMap.set(node, _num); 627 _retMap.set(node, _num); 628 ++_num; 629 } 630 631 void discover(const Edge& edge) { 632 _predMap.set(_graph.target(edge), _graph.source(edge)); 633 } 634 635 void examine(const Edge& edge) { 636 if (_graph.source(edge) == _graph.target(edge) && 637 _graph.direction(edge)) { 638 if (!_cutMap[_graph.source(edge)]) { 639 _cutMap.set(_graph.source(edge), true); 640 ++_cutNum; 641 } 642 return; 643 } 644 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return; 645 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { 646 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); 647 } 648 } 649 650 void backtrack(const Edge& edge) { 651 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 652 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 653 } 654 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { 655 if (_predMap[_graph.source(edge)] != INVALID) { 656 if (!_cutMap[_graph.source(edge)]) { 657 _cutMap.set(_graph.source(edge), true); 658 ++_cutNum; 659 } 660 } else if (rootCut) { 661 if (!_cutMap[_graph.source(edge)]) { 662 _cutMap.set(_graph.source(edge), true); 663 ++_cutNum; 664 } 665 } else { 666 rootCut = true; 667 } 668 } 669 } 670 671 private: 672 const Graph& _graph; 673 NodeMap& _cutMap; 674 int& _cutNum; 675 676 typename Graph::template NodeMap<int> _numMap; 677 typename Graph::template NodeMap<int> _retMap; 678 typename Graph::template NodeMap<Node> _predMap; 679 std::stack<UndirEdge> _edgeStack; 680 int _num; 681 bool rootCut; 682 }; 683 684 } 685 686 template <typename UndirGraph> 687 int countNodeBiconnectedComponents(const UndirGraph& graph); 688 689 /// \ingroup topology 690 /// 691 /// \brief Checks the graph is node biconnected. 692 /// 693 /// This function checks that the undirected graph is node biconnected 694 /// graph. The graph is node biconnected if any two undirected edge is 695 /// on same circle. 696 /// 697 /// \param graph The graph. 698 /// \return %True when the graph node biconnected. 699 /// \todo Make it faster. 700 template <typename UndirGraph> 701 bool nodeBiconnected(const UndirGraph& graph) { 702 return countNodeBiconnectedComponents(graph) == 1; 703 } 704 705 /// \ingroup topology 706 /// 707 /// \brief Count the biconnected components. 708 /// 709 /// This function finds the node biconnected components in an undirected 710 /// graph. The biconnected components are the classes of an equivalence 711 /// relation on the undirected edges. Two undirected edge is in relationship 712 /// when they are on same circle. 713 /// 714 /// \param graph The graph. 715 /// \return The number of components. 716 template <typename UndirGraph> 717 int countNodeBiconnectedComponents(const UndirGraph& graph) { 718 checkConcept<concept::UndirGraph, UndirGraph>(); 719 typedef typename UndirGraph::NodeIt NodeIt; 720 721 using namespace _topology_bits; 722 723 typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor; 724 725 int compNum = 0; 726 Visitor visitor(graph, compNum); 727 728 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); 729 dfs.init(); 730 731 for (NodeIt it(graph); it != INVALID; ++it) { 732 if (!dfs.reached(it)) { 733 dfs.addSource(it); 734 dfs.start(); 735 } 736 } 737 return compNum; 738 } 739 740 /// \ingroup topology 741 /// 742 /// \brief Find the node biconnected components. 743 /// 744 /// This function finds the node biconnected components in an undirected 745 /// graph. The node biconnected components are the classes of an equivalence 746 /// relation on the undirected edges. Two undirected edge are in relationship 747 /// when they are on same circle. 748 /// 749 /// \param graph The graph. 750 /// \retval comp A writable undir edge map. The values will be set from 0 to 751 /// the number of the biconnected components minus one. Each values 752 /// of the map will be set exactly once, the values of a certain component 753 /// will be set continuously. 754 /// \return The number of components. 755 template <typename UndirGraph, typename UndirEdgeMap> 756 int nodeBiconnectedComponents(const UndirGraph& graph, 757 UndirEdgeMap& compMap) { 758 checkConcept<concept::UndirGraph, UndirGraph>(); 759 typedef typename UndirGraph::NodeIt NodeIt; 760 typedef typename UndirGraph::UndirEdge UndirEdge; 761 checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>(); 762 763 using namespace _topology_bits; 764 765 typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor; 766 767 int compNum = 0; 768 Visitor visitor(graph, compMap, compNum); 769 770 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); 771 dfs.init(); 772 773 for (NodeIt it(graph); it != INVALID; ++it) { 774 if (!dfs.reached(it)) { 775 dfs.addSource(it); 776 dfs.start(); 777 } 778 } 779 return compNum; 780 } 781 782 /// \ingroup topology 783 /// 784 /// \brief Find the node biconnected cut nodes. 785 /// 786 /// This function finds the node biconnected cut nodes in an undirected 787 /// graph. The node biconnected components are the classes of an equivalence 788 /// relation on the undirected edges. Two undirected edges are in 789 /// relationship when they are on same circle. The biconnected components 790 /// are separted by nodes which are the cut nodes of the components. 791 /// 792 /// \param graph The graph. 793 /// \retval comp A writable edge map. The values will be set true when 794 /// the node separate two or more components. 795 /// \return The number of the cut nodes. 796 template <typename UndirGraph, typename NodeMap> 797 int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { 798 checkConcept<concept::UndirGraph, UndirGraph>(); 799 typedef typename UndirGraph::Node Node; 800 typedef typename UndirGraph::NodeIt NodeIt; 801 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); 802 803 using namespace _topology_bits; 804 805 typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor; 806 807 int cutNum = 0; 808 Visitor visitor(graph, cutMap, cutNum); 809 810 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); 811 dfs.init(); 812 813 for (NodeIt it(graph); it != INVALID; ++it) { 814 if (!dfs.reached(it)) { 815 dfs.addSource(it); 816 dfs.start(); 817 } 818 } 819 return cutNum; 820 } 821 822 namespace _topology_bits { 823 824 template <typename Graph> 825 class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { 826 public: 827 typedef typename Graph::Node Node; 828 typedef typename Graph::Edge Edge; 829 typedef typename Graph::UndirEdge UndirEdge; 830 831 CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum) 832 : _graph(graph), _compNum(compNum), 833 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 834 835 void start(const Node& node) { 836 _predMap.set(node, INVALID); 837 } 838 839 void reach(const Node& node) { 840 _numMap.set(node, _num); 841 _retMap.set(node, _num); 842 ++_num; 843 } 844 845 void leave(const Node& node) { 846 if (_numMap[node] <= _retMap[node]) { 847 ++_compNum; 848 } 849 } 850 851 void discover(const Edge& edge) { 852 _predMap.set(_graph.target(edge), edge); 853 } 854 855 void examine(const Edge& edge) { 856 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { 857 return; 858 } 859 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 860 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 861 } 862 } 863 864 void backtrack(const Edge& edge) { 865 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 866 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 867 } 868 } 869 870 private: 871 const Graph& _graph; 872 int& _compNum; 873 874 typename Graph::template NodeMap<int> _numMap; 875 typename Graph::template NodeMap<int> _retMap; 876 typename Graph::template NodeMap<Edge> _predMap; 877 int _num; 878 }; 879 880 template <typename Graph, typename NodeMap> 881 class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> { 882 public: 883 typedef typename Graph::Node Node; 884 typedef typename Graph::Edge Edge; 885 typedef typename Graph::UndirEdge UndirEdge; 886 887 EdgeBiconnectedComponentsVisitor(const Graph& graph, 888 NodeMap& compMap, int &compNum) 889 : _graph(graph), _compMap(compMap), _compNum(compNum), 890 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 891 892 void start(const Node& node) { 893 _predMap.set(node, INVALID); 894 } 895 896 void reach(const Node& node) { 897 _numMap.set(node, _num); 898 _retMap.set(node, _num); 899 _nodeStack.push(node); 900 ++_num; 901 } 902 903 void leave(const Node& node) { 904 if (_numMap[node] <= _retMap[node]) { 905 while (_nodeStack.top() != node) { 906 _compMap.set(_nodeStack.top(), _compNum); 907 _nodeStack.pop(); 908 } 909 _compMap.set(node, _compNum); 910 _nodeStack.pop(); 911 ++_compNum; 912 } 913 } 914 915 void discover(const Edge& edge) { 916 _predMap.set(_graph.target(edge), edge); 917 } 918 919 void examine(const Edge& edge) { 920 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { 921 return; 922 } 923 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 924 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 925 } 926 } 927 928 void backtrack(const Edge& edge) { 929 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 930 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 931 } 932 } 933 934 private: 935 const Graph& _graph; 936 NodeMap& _compMap; 937 int& _compNum; 938 939 typename Graph::template NodeMap<int> _numMap; 940 typename Graph::template NodeMap<int> _retMap; 941 typename Graph::template NodeMap<Edge> _predMap; 942 std::stack<Node> _nodeStack; 943 int _num; 944 }; 945 946 947 template <typename Graph, typename EdgeMap> 948 class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> { 949 public: 950 typedef typename Graph::Node Node; 951 typedef typename Graph::Edge Edge; 952 typedef typename Graph::UndirEdge UndirEdge; 953 954 EdgeBiconnectedCutEdgesVisitor(const Graph& graph, 955 EdgeMap& cutMap, int &cutNum) 956 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 957 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 958 959 void start(const Node& node) { 960 _predMap[node] = INVALID; 961 } 962 963 void reach(const Node& node) { 964 _numMap.set(node, _num); 965 _retMap.set(node, _num); 966 ++_num; 967 } 968 969 void leave(const Node& node) { 970 if (_numMap[node] <= _retMap[node]) { 971 if (_predMap[node] != INVALID) { 972 _cutMap.set(_predMap[node], true); 973 ++_cutNum; 974 } 975 } 976 } 977 978 void discover(const Edge& edge) { 979 _predMap.set(_graph.target(edge), edge); 980 } 981 982 void examine(const Edge& edge) { 983 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) { 984 return; 985 } 986 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 987 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 988 } 989 } 990 991 void backtrack(const Edge& edge) { 992 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 993 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 994 } 995 } 996 997 private: 998 const Graph& _graph; 999 EdgeMap& _cutMap; 1000 int& _cutNum; 1001 1002 typename Graph::template NodeMap<int> _numMap; 1003 typename Graph::template NodeMap<int> _retMap; 1004 typename Graph::template NodeMap<Edge> _predMap; 1005 int _num; 1006 }; 1007 } 1008 1009 template <typename UndirGraph> 1010 int countEdgeBiconnectedComponents(const UndirGraph& graph); 1011 1012 /// \ingroup topology 1013 /// 1014 /// \brief Checks that the graph is edge biconnected. 1015 /// 1016 /// This function checks that the graph is edge biconnected. The undirected 1017 /// graph is edge biconnected when any two nodes are connected with two 1018 /// edgedisjoint paths. 1019 /// 1020 /// \param graph The undirected graph. 1021 /// \return The number of components. 1022 /// \todo Make it faster. 1023 template <typename UndirGraph> 1024 bool edgeBiconnected(const UndirGraph& graph) { 1025 return countEdgeBiconnectedComponents(graph) == 1; 1026 } 1027 1028 /// \ingroup topology 1029 /// 1030 /// \brief Count the edge biconnected components. 1031 /// 1032 /// This function count the edge biconnected components in an undirected 1033 /// graph. The edge biconnected components are the classes of an equivalence 1034 /// relation on the nodes. Two nodes are in relationship when they are 1035 /// connected with at least two edgedisjoint paths. 1036 /// 1037 /// \param graph The undirected graph. 1038 /// \return The number of components. 1039 template <typename UndirGraph> 1040 int countEdgeBiconnectedComponents(const UndirGraph& graph) { 1041 checkConcept<concept::UndirGraph, UndirGraph>(); 1042 typedef typename UndirGraph::NodeIt NodeIt; 1043 1044 using namespace _topology_bits; 1045 1046 typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor; 1047 1048 int compNum = 0; 1049 Visitor visitor(graph, compNum); 1050 1051 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); 1052 dfs.init(); 1053 1054 for (NodeIt it(graph); it != INVALID; ++it) { 1055 if (!dfs.reached(it)) { 1056 dfs.addSource(it); 1057 dfs.start(); 1058 } 1059 } 1060 return compNum; 1061 } 1062 1063 /// \ingroup topology 1064 /// 1065 /// \brief Find the edge biconnected components. 1066 /// 1067 /// This function finds the edge biconnected components in an undirected 1068 /// graph. The edge biconnected components are the classes of an equivalence 1069 /// relation on the nodes. Two nodes are in relationship when they are 1070 /// connected at least two edgedisjoint paths. 1071 /// 1072 /// \param graph The graph. 1073 /// \retval comp A writable node map. The values will be set from 0 to 1074 /// the number of the biconnected components minus one. Each values 1075 /// of the map will be set exactly once, the values of a certain component 1076 /// will be set continuously. 1077 /// \return The number of components. 1078 template <typename UndirGraph, typename NodeMap> 1079 int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { 1080 checkConcept<concept::UndirGraph, UndirGraph>(); 1081 typedef typename UndirGraph::NodeIt NodeIt; 1082 typedef typename UndirGraph::Node Node; 1083 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); 1084 1085 using namespace _topology_bits; 1086 1087 typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor; 1088 1089 int compNum = 0; 1090 Visitor visitor(graph, compMap, compNum); 1091 1092 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); 1093 dfs.init(); 1094 1095 for (NodeIt it(graph); it != INVALID; ++it) { 1096 if (!dfs.reached(it)) { 1097 dfs.addSource(it); 1098 dfs.start(); 1099 } 1100 } 1101 return compNum; 1102 } 1103 1104 /// \ingroup topology 1105 /// 1106 /// \brief Find the edge biconnected cut edges. 1107 /// 1108 /// This function finds the edge biconnected components in an undirected 1109 /// graph. The edge biconnected components are the classes of an equivalence 1110 /// relation on the nodes. Two nodes are in relationship when they are 1111 /// connected with at least two edgedisjoint paths. The edge biconnected 1112 /// components are separted by edges which are the cut edges of the 1113 /// components. 1114 /// 1115 /// \param graph The graph. 1116 /// \retval comp A writable node map. The values will be set true when the 1117 /// edge is a cut edge. 1118 /// \return The number of cut edges. 1119 template <typename UndirGraph, typename UndirEdgeMap> 1120 int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { 1121 checkConcept<concept::UndirGraph, UndirGraph>(); 1122 typedef typename UndirGraph::NodeIt NodeIt; 1123 typedef typename UndirGraph::UndirEdge UndirEdge; 1124 checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>(); 1125 1126 using namespace _topology_bits; 1127 1128 typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor; 1129 1130 int cutNum = 0; 1131 Visitor visitor(graph, cutMap, cutNum); 1132 1133 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); 1134 dfs.init(); 1135 1136 for (NodeIt it(graph); it != INVALID; ++it) { 1137 if (!dfs.reached(it)) { 1138 dfs.addSource(it); 1139 dfs.start(); 1140 } 1141 } 1142 return cutNum; 1143 } 1144 1145 1146 namespace _topology_bits { 1147 1148 template <typename Graph, typename IntNodeMap> 1149 class TopologicalSortVisitor : public DfsVisitor<Graph> { 1150 public: 1151 typedef typename Graph::Node Node; 1152 typedef typename Graph::Edge edge; 1153 1154 TopologicalSortVisitor(IntNodeMap& order, int num) 1155 : _order(order), _num(num) {} 1156 1157 void leave(const Node& node) { 1158 _order.set(node, _num); 1159 } 1160 1161 private: 1162 IntNodeMap& _order; 1163 int _num; 1164 }; 1165 1166 } 1167 1168 /// \ingroup topology 1169 /// 1170 /// \brief Sort the nodes of a DAG into topolgical order. 1171 /// 1172 /// Sort the nodes of a DAG into topolgical order. 1173 /// 1174 /// \param g The graph. In must be directed and acyclic. 1175 /// \retval comp A writable node map. The values will be set from 0 to 1176 /// the number of the nodes in the graph minus one. Each values of the map 1177 /// will be set exactly once, the values will be set descending order. 1178 /// 1179 /// \see checkedTopologicalSort 1180 /// \see dag 1181 template <typename Graph, typename NodeMap> 1182 void topologicalSort(const Graph& graph, NodeMap& order) { 1183 using namespace _topology_bits; 1184 1185 checkConcept<concept::StaticGraph, Graph>(); 1186 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>(); 70 1187 71 1188 typedef typename Graph::Node Node; … … 73 1190 typedef typename Graph::Edge Edge; 74 1191 75 typedef BackCounterMap<NodeMap> ProcessedMap; 1192 TopologicalSortVisitor<Graph, NodeMap> 1193 visitor(order, countNodes(graph)); 1194 1195 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> > 1196 dfs(graph, visitor); 1197 1198 dfs.init(); 1199 for (NodeIt it(graph); it != INVALID; ++it) { 1200 if (!dfs.reached(it)) { 1201 dfs.addSource(it); 1202 dfs.start(); 1203 } 1204 } 1205 } 1206 1207 /// \ingroup topology 1208 /// 1209 /// \brief Sort the nodes of a DAG into topolgical order. 1210 /// 1211 /// Sort the nodes of a DAG into topolgical order. It also checks 1212 /// that the given graph is DAG. 1213 /// 1214 /// \param g The graph. In must be directed and acyclic. 1215 /// \retval order A readable  writable node map. The values will be set 1216 /// from 0 to the number of the nodes in the graph minus one. Each values 1217 /// of the map will be set exactly once, the values will be set descending 1218 /// order. 1219 /// \return %False when the graph is not DAG. 1220 /// 1221 /// \see topologicalSort 1222 /// \see dag 1223 template <typename Graph, typename NodeMap> 1224 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) { 1225 using namespace _topology_bits; 1226 1227 checkConcept<concept::StaticGraph, Graph>(); 1228 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>(); 1229 1230 typedef typename Graph::Node Node; 1231 typedef typename Graph::NodeIt NodeIt; 1232 typedef typename Graph::Edge Edge; 1233 1234 order = constMap<Node, int, 1>(); 1235 1236 TopologicalSortVisitor<Graph, NodeMap> 1237 visitor(order, countNodes(graph)); 1238 1239 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> > 1240 dfs(graph, visitor); 1241 1242 dfs.init(); 1243 for (NodeIt it(graph); it != INVALID; ++it) { 1244 if (!dfs.reached(it)) { 1245 dfs.addSource(it); 1246 while (!dfs.emptyQueue()) { 1247 Edge edge = dfs.nextEdge(); 1248 Node target = graph.target(edge); 1249 if (dfs.reached(target) && order[target] == 1) { 1250 return false; 1251 } 1252 dfs.processNextEdge(); 1253 } 1254 } 1255 } 1256 return true; 1257 } 1258 1259 /// \ingroup topology 1260 /// 1261 /// \brief Check that the given directed graph is a DAG. 1262 /// 1263 /// Check that the given directed graph is a DAG. The DAG is 1264 /// an Directed Acyclic Graph. 1265 /// \return %False when the graph is not DAG. 1266 /// \see acyclic 1267 template <typename Graph> 1268 bool dag(const Graph& graph) { 1269 1270 checkConcept<concept::StaticGraph, Graph>(); 1271 1272 typedef typename Graph::Node Node; 1273 typedef typename Graph::NodeIt NodeIt; 1274 typedef typename Graph::Edge Edge; 1275 1276 typedef typename Graph::template NodeMap<bool> ProcessedMap; 76 1277 77 1278 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>:: 78 1279 Create dfs(graph); 79 1280 80 ProcessedMap processed(nodeMap, countNodes(graph)); 81 1281 ProcessedMap processed(graph); 82 1282 dfs.processedMap(processed); 1283 83 1284 dfs.init(); 84 1285 for (NodeIt it(graph); it != INVALID; ++it) { … … 98 1299 } 99 1300 100 /// \brief Check that the given graph is a DAG. 101 /// 102 /// Check that the given graph is a DAG. The DAG is 103 /// an Directed Acyclic Graph. 104 template <typename Graph> 105 bool dag(const Graph& graph) { 106 107 checkConcept<concept::StaticGraph, Graph>(); 108 109 typedef typename Graph::Node Node; 110 typedef typename Graph::NodeIt NodeIt; 111 typedef typename Graph::Edge Edge; 112 113 typedef typename Graph::template NodeMap<bool> ProcessedMap; 114 115 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>:: 116 Create dfs(graph); 117 118 ProcessedMap processed(graph); 119 dfs.processedMap(processed); 120 121 dfs.init(); 122 for (NodeIt it(graph); it != INVALID; ++it) { 123 if (!dfs.reached(it)) { 124 dfs.addSource(it); 125 while (!dfs.emptyQueue()) { 126 Edge edge = dfs.nextEdge(); 127 Node target = graph.target(edge); 128 if (dfs.reached(target) && !processed[target]) { 129 return false; 130 } 131 dfs.processNextEdge(); 132 } 133 } 134 } 135 return true; 136 } 137 138 // UndirGraph algorithms 139 140 /// \brief Check that the given undirected graph is connected. 141 /// 142 /// Check that the given undirected graph connected. 143 template <typename UndirGraph> 144 bool connected(const UndirGraph& graph) { 145 checkConcept<concept::UndirGraph, UndirGraph>(); 146 typedef typename UndirGraph::NodeIt NodeIt; 147 if (NodeIt(graph) == INVALID) return false; 148 Dfs<UndirGraph> dfs(graph); 149 dfs.run(NodeIt(graph)); 150 for (NodeIt it(graph); it != INVALID; ++it) { 151 if (!dfs.reached(it)) { 152 return false; 153 } 154 } 155 return true; 156 } 157 1301 /// \ingroup topology 1302 /// 158 1303 /// \brief Check that the given undirected graph is acyclic. 159 1304 /// 160 1305 /// Check that the given undirected graph acyclic. 1306 /// \param graph The undirected graph. 1307 /// \return %True when there is no circle in the graph. 1308 /// \see dag 161 1309 template <typename UndirGraph> 162 1310 bool acyclic(const UndirGraph& graph) { … … 185 1333 } 186 1334 1335 /// \ingroup topology 1336 /// 187 1337 /// \brief Check that the given undirected graph is tree. 188 1338 /// 189 1339 /// Check that the given undirected graph is tree. 1340 /// \param graph The undirected graph. 1341 /// \return %True when the graph is acyclic and connected. 190 1342 template <typename UndirGraph> 191 1343 bool tree(const UndirGraph& graph) { … … 194 1346 typedef typename UndirGraph::NodeIt NodeIt; 195 1347 typedef typename UndirGraph::Edge Edge; 196 if (NodeIt(graph) == INVALID) return false;197 1348 Dfs<UndirGraph> dfs(graph); 198 1349 dfs.init(); … … 215 1366 return true; 216 1367 } 217 218 ///Count the number of connected components of an undirected graph 219 220 ///Count the number of connected components of an undirected graph 221 /// 222 ///\param g The graph. In must be undirected. 223 ///\return The number of components 224 template <class UndirGraph> 225 int countConnectedComponents(const UndirGraph &g) { 1368 1369 /// \ingroup topology 1370 /// 1371 /// \brief Check that the given undirected graph is bipartite. 1372 /// 1373 /// Check that the given undirected graph is bipartite. 1374 /// \param graph The undirected graph. 1375 /// \return %True when the nodes can be separated into two sets that 1376 /// there are not connected nodes in neither sets. 1377 template <typename UndirGraph> 1378 bool bipartite(const UndirGraph& graph) { 226 1379 checkConcept<concept::UndirGraph, UndirGraph>(); 227 int c = 0; 228 Bfs<UndirGraph> bfs(g); 229 bfs.init(); 230 for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { 231 if(!bfs.reached(n)) { 232 bfs.addSource(n); 233 bfs.start(); 234 ++c; 235 } 236 } 237 return c; 238 } 239 240 241 ///Find the connected components of an undirected graph 242 243 ///Find the connected components of an undirected graph 244 /// 245 ///\param g The graph. In must be undirected. 246 ///\retval comp A writable node map. The values will be set from 0 to 247 ///the number of the connected components minus one. Each values of the map 248 ///will be set exactly once, the values of a certain component will be 249 ///set continuously. 250 ///\return The number of components 251 ///\todo Test required 252 template <class UndirGraph, class IntNodeMap> 253 int connectedComponents(const UndirGraph &g, IntNodeMap &comp) { 254 checkConcept<concept::UndirGraph, UndirGraph>(); 255 checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, 256 IntNodeMap>(); 257 int c = 0; 258 Bfs<UndirGraph> bfs(g); 259 bfs.init(); 260 for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { 261 if(!bfs.reached(n)) { 262 bfs.addSource(n); 263 while (!bfs.emptyQueue()) { 264 comp[bfs.nextNode()] = c; 265 bfs.processNextNode(); 266 } 267 ++c; 268 } 269 } 270 return c; 271 } 272 273 namespace _components_bits { 274 275 template <typename Key, typename IntMap> 276 struct FillWriteMap : public MapBase<Key, bool> { 277 public: 278 FillWriteMap(IntMap& _map, int& _comp) 279 : map(_map), comp(_comp) {} 280 void set(Key key, bool value) { 281 if (value) { map.set(key, comp); } 282 } 283 private: 284 IntMap& map; 285 int& comp; 286 }; 287 288 template <typename Key, typename Container = std::vector<Key> > 289 struct BackInserterWriteMap : public MapBase<Key, bool> { 290 public: 291 BackInserterWriteMap(Container& _container) 292 : container(_container) {} 293 void set(Key key, bool value) { 294 if (value) { container.push_back(key); } 295 } 296 private: 297 Container& container; 298 }; 299 300 } 301 302 /// \brief Count the strongly connected components of a directed graph 303 /// 304 /// Count the strongly connected components of a directed graph 305 /// 306 /// \param g The graph. 307 /// \return The number of components 308 template <typename Graph> 309 int countStronglyConnectedComponents(const Graph& graph) { 310 checkConcept<concept::StaticGraph, Graph>(); 311 312 using namespace _components_bits; 313 314 typedef typename Graph::Node Node; 315 typedef typename Graph::Edge Edge; 316 typedef typename Graph::NodeIt NodeIt; 317 typedef typename Graph::EdgeIt EdgeIt; 318 319 320 typename Dfs<Graph>:: 321 template DefProcessedMap<BackInserterWriteMap<Node> >:: 322 Create dfs(graph); 323 324 std::vector<Node> nodes; 325 BackInserterWriteMap<Node> processed(nodes); 326 dfs.processedMap(processed); 327 328 dfs.init(); 1380 typedef typename UndirGraph::Node Node; 1381 typedef typename UndirGraph::NodeIt NodeIt; 1382 typedef typename UndirGraph::Edge Edge; 1383 if (NodeIt(graph) == INVALID) return false; 1384 Dfs<UndirGraph> dfs(graph); 1385 dfs.init(); 1386 typename UndirGraph::template NodeMap<bool> red(graph); 329 1387 for (NodeIt it(graph); it != INVALID; ++it) { 330 1388 if (!dfs.reached(it)) { 331 1389 dfs.addSource(it); 332 dfs.start(); 333 } 334 } 335 336 typedef RevGraphAdaptor<const Graph> RGraph; 337 338 RGraph rgraph(graph); 339 340 Dfs<RGraph> rdfs(rgraph); 341 342 int num = 0; 343 344 rdfs.init(); 345 for (typename std::vector<Node>::reverse_iterator 346 it = nodes.rbegin(); it != nodes.rend(); ++it) { 347 if (!rdfs.reached(*it)) { 348 rdfs.addSource(*it); 349 rdfs.start(); 350 ++num; 351 } 352 } 353 return num; 354 } 355 356 /// \brief Find the strongly connected components of a directed graph 357 /// 358 /// Find the strongly connected components of a directed graph 359 /// 360 /// \param g The graph. 361 /// \retval comp A writable node map. The values will be set from 0 to 362 /// the number of the strongly connected components minus one. Each values 363 /// of the map will be set exactly once, the values of a certain component 364 /// will be set continuously. 365 /// \return The number of components 366 template <typename Graph, typename IntNodeMap> 367 int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) { 368 checkConcept<concept::StaticGraph, Graph>(); 369 checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>(); 370 371 using namespace _components_bits; 372 373 typedef typename Graph::Node Node; 374 typedef typename Graph::Edge Edge; 375 typedef typename Graph::NodeIt NodeIt; 376 typedef typename Graph::EdgeIt EdgeIt; 377 378 379 typename Dfs<Graph>:: 380 template DefProcessedMap<BackInserterWriteMap<Node> >:: 381 Create dfs(graph); 382 383 std::vector<Node> nodes; 384 BackInserterWriteMap<Node> processed(nodes); 385 dfs.processedMap(processed); 386 387 dfs.init(); 388 for (NodeIt it(graph); it != INVALID; ++it) { 389 if (!dfs.reached(it)) { 390 dfs.addSource(it); 391 dfs.start(); 392 } 393 } 394 395 typedef RevGraphAdaptor<const Graph> RGraph; 396 397 RGraph rgraph(graph); 398 399 typename Dfs<RGraph>:: 400 template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >:: 401 Create rdfs(rgraph); 402 403 int num = 0; 404 FillWriteMap<Node, IntNodeMap> rprocessed(comp, num); 405 rdfs.processedMap(rprocessed); 406 407 rdfs.init(); 408 for (typename std::vector<Node>::reverse_iterator 409 it = nodes.rbegin(); it != nodes.rend(); ++it) { 410 if (!rdfs.reached(*it)) { 411 rdfs.addSource(*it); 412 rdfs.start(); 413 ++num; 414 } 415 } 416 return num; 417 } 418 1390 red[it] = true; 1391 while (!dfs.emptyQueue()) { 1392 Edge edge = dfs.nextEdge(); 1393 Node source = graph.source(edge); 1394 Node target = graph.target(edge); 1395 if (dfs.reached(target) && red[source] == red[target]) { 1396 return false; 1397 } else { 1398 red[target] = !red[source]; 1399 } 1400 dfs.processNextEdge(); 1401 } 1402 } 1403 } 1404 return true; 1405 } 1406 419 1407 } //namespace lemon 420 1408
Note: See TracChangeset
for help on using the changeset viewer.