1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 2003-2013 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 19 #ifndef LEMON_CONNECTIVITY_H 20 #define LEMON_CONNECTIVITY_H 21 22 #include <lemon/dfs.h> 23 #include <lemon/bfs.h> 24 #include <lemon/core.h> 25 #include <lemon/maps.h> 26 #include <lemon/adaptors.h> 27 28 #include <lemon/concepts/digraph.h> 29 #include <lemon/concepts/graph.h> 30 #include <lemon/concept_check.h> 31 32 #include <stack> 33 #include <functional> 34 35 /// \ingroup graph_properties 36 /// \file 37 /// \brief Connectivity algorithms 38 /// 39 /// Connectivity algorithms 40 41 namespace lemon { 42 43 /// \ingroup graph_properties 44 /// 45 /// \brief Check whether an undirected graph is connected. 46 /// 47 /// This function checks whether the given undirected graph is connected, 48 /// i.e. there is a path between any two nodes in the graph. 49 /// 50 /// \return \c true if the graph is connected. 51 /// \note By definition, the empty graph is connected. 52 /// 53 /// \see countConnectedComponents(), connectedComponents() 54 /// \see stronglyConnected() 55 template <typename Graph> connected(const Graph & graph)56 bool connected(const Graph& graph) { 57 checkConcept<concepts::Graph, Graph>(); 58 typedef typename Graph::NodeIt NodeIt; 59 if (NodeIt(graph) == INVALID) return true; 60 Dfs<Graph> dfs(graph); 61 dfs.run(NodeIt(graph)); 62 for (NodeIt it(graph); it != INVALID; ++it) { 63 if (!dfs.reached(it)) { 64 return false; 65 } 66 } 67 return true; 68 } 69 70 /// \ingroup graph_properties 71 /// 72 /// \brief Count the number of connected components of an undirected graph 73 /// 74 /// This function counts the number of connected components of the given 75 /// undirected graph. 76 /// 77 /// The connected components are the classes of an equivalence relation 78 /// on the nodes of an undirected graph. Two nodes are in the same class 79 /// if they are connected with a path. 80 /// 81 /// \return The number of connected components. 82 /// \note By definition, the empty graph consists 83 /// of zero connected components. 84 /// 85 /// \see connected(), connectedComponents() 86 template <typename Graph> countConnectedComponents(const Graph & graph)87 int countConnectedComponents(const Graph &graph) { 88 checkConcept<concepts::Graph, Graph>(); 89 typedef typename Graph::Node Node; 90 typedef typename Graph::Arc Arc; 91 92 typedef NullMap<Node, Arc> PredMap; 93 typedef NullMap<Node, int> DistMap; 94 95 int compNum = 0; 96 typename Bfs<Graph>:: 97 template SetPredMap<PredMap>:: 98 template SetDistMap<DistMap>:: 99 Create bfs(graph); 100 101 PredMap predMap; 102 bfs.predMap(predMap); 103 104 DistMap distMap; 105 bfs.distMap(distMap); 106 107 bfs.init(); 108 for(typename Graph::NodeIt n(graph); n != INVALID; ++n) { 109 if (!bfs.reached(n)) { 110 bfs.addSource(n); 111 bfs.start(); 112 ++compNum; 113 } 114 } 115 return compNum; 116 } 117 118 /// \ingroup graph_properties 119 /// 120 /// \brief Find the connected components of an undirected graph 121 /// 122 /// This function finds the connected components of the given undirected 123 /// graph. 124 /// 125 /// The connected components are the classes of an equivalence relation 126 /// on the nodes of an undirected graph. Two nodes are in the same class 127 /// if they are connected with a path. 128 /// 129 /// \image html connected_components.png 130 /// \image latex connected_components.eps "Connected components" width=\textwidth 131 /// 132 /// \param graph The undirected graph. 133 /// \retval compMap A writable node map. The values will be set from 0 to 134 /// the number of the connected components minus one. Each value of the map 135 /// will be set exactly once, and the values of a certain component will be 136 /// set continuously. 137 /// \return The number of connected components. 138 /// \note By definition, the empty graph consists 139 /// of zero connected components. 140 /// 141 /// \see connected(), countConnectedComponents() 142 template <class Graph, class NodeMap> connectedComponents(const Graph & graph,NodeMap & compMap)143 int connectedComponents(const Graph &graph, NodeMap &compMap) { 144 checkConcept<concepts::Graph, Graph>(); 145 typedef typename Graph::Node Node; 146 typedef typename Graph::Arc Arc; 147 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); 148 149 typedef NullMap<Node, Arc> PredMap; 150 typedef NullMap<Node, int> DistMap; 151 152 int compNum = 0; 153 typename Bfs<Graph>:: 154 template SetPredMap<PredMap>:: 155 template SetDistMap<DistMap>:: 156 Create bfs(graph); 157 158 PredMap predMap; 159 bfs.predMap(predMap); 160 161 DistMap distMap; 162 bfs.distMap(distMap); 163 164 bfs.init(); 165 for(typename Graph::NodeIt n(graph); n != INVALID; ++n) { 166 if(!bfs.reached(n)) { 167 bfs.addSource(n); 168 while (!bfs.emptyQueue()) { 169 compMap.set(bfs.nextNode(), compNum); 170 bfs.processNextNode(); 171 } 172 ++compNum; 173 } 174 } 175 return compNum; 176 } 177 178 namespace _connectivity_bits { 179 180 template <typename Digraph, typename Iterator > 181 struct LeaveOrderVisitor : public DfsVisitor<Digraph> { 182 public: 183 typedef typename Digraph::Node Node; LeaveOrderVisitorLeaveOrderVisitor184 LeaveOrderVisitor(Iterator it) : _it(it) {} 185 leaveLeaveOrderVisitor186 void leave(const Node& node) { 187 *(_it++) = node; 188 } 189 190 private: 191 Iterator _it; 192 }; 193 194 template <typename Digraph, typename Map> 195 struct FillMapVisitor : public DfsVisitor<Digraph> { 196 public: 197 typedef typename Digraph::Node Node; 198 typedef typename Map::Value Value; 199 FillMapVisitorFillMapVisitor200 FillMapVisitor(Map& map, Value& value) 201 : _map(map), _value(value) {} 202 reachFillMapVisitor203 void reach(const Node& node) { 204 _map.set(node, _value); 205 } 206 private: 207 Map& _map; 208 Value& _value; 209 }; 210 211 template <typename Digraph, typename ArcMap> 212 struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> { 213 public: 214 typedef typename Digraph::Node Node; 215 typedef typename Digraph::Arc Arc; 216 StronglyConnectedCutArcsVisitorStronglyConnectedCutArcsVisitor217 StronglyConnectedCutArcsVisitor(const Digraph& digraph, 218 ArcMap& cutMap, 219 int& cutNum) 220 : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum), 221 _compMap(digraph, -1), _num(-1) { 222 } 223 startStronglyConnectedCutArcsVisitor224 void start(const Node&) { 225 ++_num; 226 } 227 reachStronglyConnectedCutArcsVisitor228 void reach(const Node& node) { 229 _compMap.set(node, _num); 230 } 231 examineStronglyConnectedCutArcsVisitor232 void examine(const Arc& arc) { 233 if (_compMap[_digraph.source(arc)] != 234 _compMap[_digraph.target(arc)]) { 235 _cutMap.set(arc, true); 236 ++_cutNum; 237 } 238 } 239 private: 240 const Digraph& _digraph; 241 ArcMap& _cutMap; 242 int& _cutNum; 243 244 typename Digraph::template NodeMap<int> _compMap; 245 int _num; 246 }; 247 248 } 249 250 251 /// \ingroup graph_properties 252 /// 253 /// \brief Check whether a directed graph is strongly connected. 254 /// 255 /// This function checks whether the given directed graph is strongly 256 /// connected, i.e. any two nodes of the digraph are 257 /// connected with directed paths in both direction. 258 /// 259 /// \return \c true if the digraph is strongly connected. 260 /// \note By definition, the empty digraph is strongly connected. 261 /// 262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() 263 /// \see connected() 264 template <typename Digraph> stronglyConnected(const Digraph & digraph)265 bool stronglyConnected(const Digraph& digraph) { 266 checkConcept<concepts::Digraph, Digraph>(); 267 268 typedef typename Digraph::Node Node; 269 typedef typename Digraph::NodeIt NodeIt; 270 271 typename Digraph::Node source = NodeIt(digraph); 272 if (source == INVALID) return true; 273 274 using namespace _connectivity_bits; 275 276 typedef DfsVisitor<Digraph> Visitor; 277 Visitor visitor; 278 279 DfsVisit<Digraph, Visitor> dfs(digraph, visitor); 280 dfs.init(); 281 dfs.addSource(source); 282 dfs.start(); 283 284 for (NodeIt it(digraph); it != INVALID; ++it) { 285 if (!dfs.reached(it)) { 286 return false; 287 } 288 } 289 290 typedef ReverseDigraph<const Digraph> RDigraph; 291 typedef typename RDigraph::NodeIt RNodeIt; 292 RDigraph rdigraph(digraph); 293 294 typedef DfsVisitor<RDigraph> RVisitor; 295 RVisitor rvisitor; 296 297 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor); 298 rdfs.init(); 299 rdfs.addSource(source); 300 rdfs.start(); 301 302 for (RNodeIt it(rdigraph); it != INVALID; ++it) { 303 if (!rdfs.reached(it)) { 304 return false; 305 } 306 } 307 308 return true; 309 } 310 311 /// \ingroup graph_properties 312 /// 313 /// \brief Count the number of strongly connected components of a 314 /// directed graph 315 /// 316 /// This function counts the number of strongly connected components of 317 /// the given directed graph. 318 /// 319 /// The strongly connected components are the classes of an 320 /// equivalence relation on the nodes of a digraph. Two nodes are in 321 /// the same class if they are connected with directed paths in both 322 /// direction. 323 /// 324 /// \return The number of strongly connected components. 325 /// \note By definition, the empty digraph has zero 326 /// strongly connected components. 327 /// 328 /// \see stronglyConnected(), stronglyConnectedComponents() 329 template <typename Digraph> countStronglyConnectedComponents(const Digraph & digraph)330 int countStronglyConnectedComponents(const Digraph& digraph) { 331 checkConcept<concepts::Digraph, Digraph>(); 332 333 using namespace _connectivity_bits; 334 335 typedef typename Digraph::Node Node; 336 typedef typename Digraph::Arc Arc; 337 typedef typename Digraph::NodeIt NodeIt; 338 typedef typename Digraph::ArcIt ArcIt; 339 340 typedef std::vector<Node> Container; 341 typedef typename Container::iterator Iterator; 342 343 Container nodes(countNodes(digraph)); 344 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 345 Visitor visitor(nodes.begin()); 346 347 DfsVisit<Digraph, Visitor> dfs(digraph, visitor); 348 dfs.init(); 349 for (NodeIt it(digraph); it != INVALID; ++it) { 350 if (!dfs.reached(it)) { 351 dfs.addSource(it); 352 dfs.start(); 353 } 354 } 355 356 typedef typename Container::reverse_iterator RIterator; 357 typedef ReverseDigraph<const Digraph> RDigraph; 358 359 RDigraph rdigraph(digraph); 360 361 typedef DfsVisitor<Digraph> RVisitor; 362 RVisitor rvisitor; 363 364 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor); 365 366 int compNum = 0; 367 368 rdfs.init(); 369 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { 370 if (!rdfs.reached(*it)) { 371 rdfs.addSource(*it); 372 rdfs.start(); 373 ++compNum; 374 } 375 } 376 return compNum; 377 } 378 379 /// \ingroup graph_properties 380 /// 381 /// \brief Find the strongly connected components of a directed graph 382 /// 383 /// This function finds the strongly connected components of the given 384 /// directed graph. In addition, the numbering of the components will 385 /// satisfy that there is no arc going from a higher numbered component 386 /// to a lower one (i.e. it provides a topological order of the components). 387 /// 388 /// The strongly connected components are the classes of an 389 /// equivalence relation on the nodes of a digraph. Two nodes are in 390 /// the same class if they are connected with directed paths in both 391 /// direction. 392 /// 393 /// \image html strongly_connected_components.png 394 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth 395 /// 396 /// \param digraph The digraph. 397 /// \retval compMap A writable node map. The values will be set from 0 to 398 /// the number of the strongly connected components minus one. Each value 399 /// of the map will be set exactly once, and the values of a certain 400 /// component will be set continuously. 401 /// \return The number of strongly connected components. 402 /// \note By definition, the empty digraph has zero 403 /// strongly connected components. 404 /// 405 /// \see stronglyConnected(), countStronglyConnectedComponents() 406 template <typename Digraph, typename NodeMap> stronglyConnectedComponents(const Digraph & digraph,NodeMap & compMap)407 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { 408 checkConcept<concepts::Digraph, Digraph>(); 409 typedef typename Digraph::Node Node; 410 typedef typename Digraph::NodeIt NodeIt; 411 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); 412 413 using namespace _connectivity_bits; 414 415 typedef std::vector<Node> Container; 416 typedef typename Container::iterator Iterator; 417 418 Container nodes(countNodes(digraph)); 419 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 420 Visitor visitor(nodes.begin()); 421 422 DfsVisit<Digraph, Visitor> dfs(digraph, visitor); 423 dfs.init(); 424 for (NodeIt it(digraph); it != INVALID; ++it) { 425 if (!dfs.reached(it)) { 426 dfs.addSource(it); 427 dfs.start(); 428 } 429 } 430 431 typedef typename Container::reverse_iterator RIterator; 432 typedef ReverseDigraph<const Digraph> RDigraph; 433 434 RDigraph rdigraph(digraph); 435 436 int compNum = 0; 437 438 typedef FillMapVisitor<RDigraph, NodeMap> RVisitor; 439 RVisitor rvisitor(compMap, compNum); 440 441 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor); 442 443 rdfs.init(); 444 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { 445 if (!rdfs.reached(*it)) { 446 rdfs.addSource(*it); 447 rdfs.start(); 448 ++compNum; 449 } 450 } 451 return compNum; 452 } 453 454 /// \ingroup graph_properties 455 /// 456 /// \brief Find the cut arcs of the strongly connected components. 457 /// 458 /// This function finds the cut arcs of the strongly connected components 459 /// of the given digraph. 460 /// 461 /// The strongly connected components are the classes of an 462 /// equivalence relation on the nodes of a digraph. Two nodes are in 463 /// the same class if they are connected with directed paths in both 464 /// direction. 465 /// The strongly connected components are separated by the cut arcs. 466 /// 467 /// \param digraph The digraph. 468 /// \retval cutMap A writable arc map. The values will be set to \c true 469 /// for the cut arcs (exactly once for each cut arc), and will not be 470 /// changed for other arcs. 471 /// \return The number of cut arcs. 472 /// 473 /// \see stronglyConnected(), stronglyConnectedComponents() 474 template <typename Digraph, typename ArcMap> stronglyConnectedCutArcs(const Digraph & digraph,ArcMap & cutMap)475 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) { 476 checkConcept<concepts::Digraph, Digraph>(); 477 typedef typename Digraph::Node Node; 478 typedef typename Digraph::Arc Arc; 479 typedef typename Digraph::NodeIt NodeIt; 480 checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>(); 481 482 using namespace _connectivity_bits; 483 484 typedef std::vector<Node> Container; 485 typedef typename Container::iterator Iterator; 486 487 Container nodes(countNodes(digraph)); 488 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 489 Visitor visitor(nodes.begin()); 490 491 DfsVisit<Digraph, Visitor> dfs(digraph, visitor); 492 dfs.init(); 493 for (NodeIt it(digraph); it != INVALID; ++it) { 494 if (!dfs.reached(it)) { 495 dfs.addSource(it); 496 dfs.start(); 497 } 498 } 499 500 typedef typename Container::reverse_iterator RIterator; 501 typedef ReverseDigraph<const Digraph> RDigraph; 502 503 RDigraph rdigraph(digraph); 504 505 int cutNum = 0; 506 507 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor; 508 RVisitor rvisitor(rdigraph, cutMap, cutNum); 509 510 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor); 511 512 rdfs.init(); 513 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) { 514 if (!rdfs.reached(*it)) { 515 rdfs.addSource(*it); 516 rdfs.start(); 517 } 518 } 519 return cutNum; 520 } 521 522 namespace _connectivity_bits { 523 524 template <typename Digraph> 525 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> { 526 public: 527 typedef typename Digraph::Node Node; 528 typedef typename Digraph::Arc Arc; 529 typedef typename Digraph::Edge Edge; 530 CountBiNodeConnectedComponentsVisitor(const Digraph & graph,int & compNum)531 CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum) 532 : _graph(graph), _compNum(compNum), 533 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 534 start(const Node & node)535 void start(const Node& node) { 536 _predMap.set(node, INVALID); 537 } 538 reach(const Node & node)539 void reach(const Node& node) { 540 _numMap.set(node, _num); 541 _retMap.set(node, _num); 542 ++_num; 543 } 544 discover(const Arc & edge)545 void discover(const Arc& edge) { 546 _predMap.set(_graph.target(edge), _graph.source(edge)); 547 } 548 examine(const Arc & edge)549 void examine(const Arc& edge) { 550 if (_graph.source(edge) == _graph.target(edge) && 551 _graph.direction(edge)) { 552 ++_compNum; 553 return; 554 } 555 if (_predMap[_graph.source(edge)] == _graph.target(edge)) { 556 return; 557 } 558 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { 559 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); 560 } 561 } 562 backtrack(const Arc & edge)563 void backtrack(const Arc& edge) { 564 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 565 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 566 } 567 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { 568 ++_compNum; 569 } 570 } 571 572 private: 573 const Digraph& _graph; 574 int& _compNum; 575 576 typename Digraph::template NodeMap<int> _numMap; 577 typename Digraph::template NodeMap<int> _retMap; 578 typename Digraph::template NodeMap<Node> _predMap; 579 int _num; 580 }; 581 582 template <typename Digraph, typename ArcMap> 583 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> { 584 public: 585 typedef typename Digraph::Node Node; 586 typedef typename Digraph::Arc Arc; 587 typedef typename Digraph::Edge Edge; 588 BiNodeConnectedComponentsVisitor(const Digraph & graph,ArcMap & compMap,int & compNum)589 BiNodeConnectedComponentsVisitor(const Digraph& graph, 590 ArcMap& compMap, int &compNum) 591 : _graph(graph), _compMap(compMap), _compNum(compNum), 592 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 593 start(const Node & node)594 void start(const Node& node) { 595 _predMap.set(node, INVALID); 596 } 597 reach(const Node & node)598 void reach(const Node& node) { 599 _numMap.set(node, _num); 600 _retMap.set(node, _num); 601 ++_num; 602 } 603 discover(const Arc & edge)604 void discover(const Arc& edge) { 605 Node target = _graph.target(edge); 606 _predMap.set(target, edge); 607 _edgeStack.push(edge); 608 } 609 examine(const Arc & edge)610 void examine(const Arc& edge) { 611 Node source = _graph.source(edge); 612 Node target = _graph.target(edge); 613 if (source == target && _graph.direction(edge)) { 614 _compMap.set(edge, _compNum); 615 ++_compNum; 616 return; 617 } 618 if (_numMap[target] < _numMap[source]) { 619 if (_predMap[source] != _graph.oppositeArc(edge)) { 620 _edgeStack.push(edge); 621 } 622 } 623 if (_predMap[source] != INVALID && 624 target == _graph.source(_predMap[source])) { 625 return; 626 } 627 if (_retMap[source] > _numMap[target]) { 628 _retMap.set(source, _numMap[target]); 629 } 630 } 631 backtrack(const Arc & edge)632 void backtrack(const Arc& edge) { 633 Node source = _graph.source(edge); 634 Node target = _graph.target(edge); 635 if (_retMap[source] > _retMap[target]) { 636 _retMap.set(source, _retMap[target]); 637 } 638 if (_numMap[source] <= _retMap[target]) { 639 while (_edgeStack.top() != edge) { 640 _compMap.set(_edgeStack.top(), _compNum); 641 _edgeStack.pop(); 642 } 643 _compMap.set(edge, _compNum); 644 _edgeStack.pop(); 645 ++_compNum; 646 } 647 } 648 649 private: 650 const Digraph& _graph; 651 ArcMap& _compMap; 652 int& _compNum; 653 654 typename Digraph::template NodeMap<int> _numMap; 655 typename Digraph::template NodeMap<int> _retMap; 656 typename Digraph::template NodeMap<Arc> _predMap; 657 std::stack<Edge> _edgeStack; 658 int _num; 659 }; 660 661 662 template <typename Digraph, typename NodeMap> 663 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> { 664 public: 665 typedef typename Digraph::Node Node; 666 typedef typename Digraph::Arc Arc; 667 typedef typename Digraph::Edge Edge; 668 BiNodeConnectedCutNodesVisitor(const Digraph & graph,NodeMap & cutMap,int & cutNum)669 BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap, 670 int& cutNum) 671 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 672 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 673 start(const Node & node)674 void start(const Node& node) { 675 _predMap.set(node, INVALID); 676 rootCut = false; 677 } 678 reach(const Node & node)679 void reach(const Node& node) { 680 _numMap.set(node, _num); 681 _retMap.set(node, _num); 682 ++_num; 683 } 684 discover(const Arc & edge)685 void discover(const Arc& edge) { 686 _predMap.set(_graph.target(edge), _graph.source(edge)); 687 } 688 examine(const Arc & edge)689 void examine(const Arc& edge) { 690 if (_graph.source(edge) == _graph.target(edge) && 691 _graph.direction(edge)) { 692 if (!_cutMap[_graph.source(edge)]) { 693 _cutMap.set(_graph.source(edge), true); 694 ++_cutNum; 695 } 696 return; 697 } 698 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return; 699 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) { 700 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]); 701 } 702 } 703 backtrack(const Arc & edge)704 void backtrack(const Arc& edge) { 705 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 706 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 707 } 708 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) { 709 if (_predMap[_graph.source(edge)] != INVALID) { 710 if (!_cutMap[_graph.source(edge)]) { 711 _cutMap.set(_graph.source(edge), true); 712 ++_cutNum; 713 } 714 } else if (rootCut) { 715 if (!_cutMap[_graph.source(edge)]) { 716 _cutMap.set(_graph.source(edge), true); 717 ++_cutNum; 718 } 719 } else { 720 rootCut = true; 721 } 722 } 723 } 724 725 private: 726 const Digraph& _graph; 727 NodeMap& _cutMap; 728 int& _cutNum; 729 730 typename Digraph::template NodeMap<int> _numMap; 731 typename Digraph::template NodeMap<int> _retMap; 732 typename Digraph::template NodeMap<Node> _predMap; 733 std::stack<Edge> _edgeStack; 734 int _num; 735 bool rootCut; 736 }; 737 738 } 739 740 template <typename Graph> 741 int countBiNodeConnectedComponents(const Graph& graph); 742 743 /// \ingroup graph_properties 744 /// 745 /// \brief Check whether an undirected graph is bi-node-connected. 746 /// 747 /// This function checks whether the given undirected graph is 748 /// bi-node-connected, i.e. a connected graph without articulation 749 /// node. 750 /// 751 /// \return \c true if the graph bi-node-connected. 752 /// 753 /// \note By definition, 754 /// \li a graph consisting of zero or one node is bi-node-connected, 755 /// \li a graph consisting of two isolated nodes 756 /// is \e not bi-node-connected and 757 /// \li a graph consisting of two nodes connected by an edge 758 /// is bi-node-connected. 759 /// 760 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() 761 template <typename Graph> biNodeConnected(const Graph & graph)762 bool biNodeConnected(const Graph& graph) { 763 bool hasNonIsolated = false, hasIsolated = false; 764 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 765 if (typename Graph::OutArcIt(graph, n) == INVALID) { 766 if (hasIsolated || hasNonIsolated) { 767 return false; 768 } else { 769 hasIsolated = true; 770 } 771 } else { 772 if (hasIsolated) { 773 return false; 774 } else { 775 hasNonIsolated = true; 776 } 777 } 778 } 779 return countBiNodeConnectedComponents(graph) <= 1; 780 } 781 782 /// \ingroup graph_properties 783 /// 784 /// \brief Count the number of bi-node-connected components of an 785 /// undirected graph. 786 /// 787 /// This function counts the number of bi-node-connected components of 788 /// the given undirected graph. 789 /// 790 /// The bi-node-connected components are the classes of an equivalence 791 /// relation on the edges of a undirected graph. Two edges are in the 792 /// same class if they are on same circle. 793 /// 794 /// \return The number of bi-node-connected components. 795 /// 796 /// \see biNodeConnected(), biNodeConnectedComponents() 797 template <typename Graph> countBiNodeConnectedComponents(const Graph & graph)798 int countBiNodeConnectedComponents(const Graph& graph) { 799 checkConcept<concepts::Graph, Graph>(); 800 typedef typename Graph::NodeIt NodeIt; 801 802 using namespace _connectivity_bits; 803 804 typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor; 805 806 int compNum = 0; 807 Visitor visitor(graph, compNum); 808 809 DfsVisit<Graph, Visitor> dfs(graph, visitor); 810 dfs.init(); 811 812 for (NodeIt it(graph); it != INVALID; ++it) { 813 if (!dfs.reached(it)) { 814 dfs.addSource(it); 815 dfs.start(); 816 } 817 } 818 return compNum; 819 } 820 821 /// \ingroup graph_properties 822 /// 823 /// \brief Find the bi-node-connected components of an undirected graph. 824 /// 825 /// This function finds the bi-node-connected components of the given 826 /// undirected graph. 827 /// 828 /// The bi-node-connected components are the classes of an equivalence 829 /// relation on the edges of a undirected graph. Two edges are in the 830 /// same class if they are on same circle. 831 /// 832 /// \image html node_biconnected_components.png 833 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 834 /// 835 /// \param graph The undirected graph. 836 /// \retval compMap A writable edge map. The values will be set from 0 837 /// to the number of the bi-node-connected components minus one. Each 838 /// value of the map will be set exactly once, and the values of a 839 /// certain component will be set continuously. 840 /// \return The number of bi-node-connected components. 841 /// 842 /// \see biNodeConnected(), countBiNodeConnectedComponents() 843 template <typename Graph, typename EdgeMap> biNodeConnectedComponents(const Graph & graph,EdgeMap & compMap)844 int biNodeConnectedComponents(const Graph& graph, 845 EdgeMap& compMap) { 846 checkConcept<concepts::Graph, Graph>(); 847 typedef typename Graph::NodeIt NodeIt; 848 typedef typename Graph::Edge Edge; 849 checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>(); 850 851 using namespace _connectivity_bits; 852 853 typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor; 854 855 int compNum = 0; 856 Visitor visitor(graph, compMap, compNum); 857 858 DfsVisit<Graph, Visitor> dfs(graph, visitor); 859 dfs.init(); 860 861 for (NodeIt it(graph); it != INVALID; ++it) { 862 if (!dfs.reached(it)) { 863 dfs.addSource(it); 864 dfs.start(); 865 } 866 } 867 return compNum; 868 } 869 870 /// \ingroup graph_properties 871 /// 872 /// \brief Find the bi-node-connected cut nodes in an undirected graph. 873 /// 874 /// This function finds the bi-node-connected cut nodes in the given 875 /// undirected graph. 876 /// 877 /// The bi-node-connected components are the classes of an equivalence 878 /// relation on the edges of a undirected graph. Two edges are in the 879 /// same class if they are on same circle. 880 /// The bi-node-connected components are separted by the cut nodes of 881 /// the components. 882 /// 883 /// \param graph The undirected graph. 884 /// \retval cutMap A writable node map. The values will be set to 885 /// \c true for the nodes that separate two or more components 886 /// (exactly once for each cut node), and will not be changed for 887 /// other nodes. 888 /// \return The number of the cut nodes. 889 /// 890 /// \see biNodeConnected(), biNodeConnectedComponents() 891 template <typename Graph, typename NodeMap> biNodeConnectedCutNodes(const Graph & graph,NodeMap & cutMap)892 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { 893 checkConcept<concepts::Graph, Graph>(); 894 typedef typename Graph::Node Node; 895 typedef typename Graph::NodeIt NodeIt; 896 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>(); 897 898 using namespace _connectivity_bits; 899 900 typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor; 901 902 int cutNum = 0; 903 Visitor visitor(graph, cutMap, cutNum); 904 905 DfsVisit<Graph, Visitor> dfs(graph, visitor); 906 dfs.init(); 907 908 for (NodeIt it(graph); it != INVALID; ++it) { 909 if (!dfs.reached(it)) { 910 dfs.addSource(it); 911 dfs.start(); 912 } 913 } 914 return cutNum; 915 } 916 917 namespace _connectivity_bits { 918 919 template <typename Digraph> 920 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> { 921 public: 922 typedef typename Digraph::Node Node; 923 typedef typename Digraph::Arc Arc; 924 typedef typename Digraph::Edge Edge; 925 CountBiEdgeConnectedComponentsVisitor(const Digraph & graph,int & compNum)926 CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum) 927 : _graph(graph), _compNum(compNum), 928 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 929 start(const Node & node)930 void start(const Node& node) { 931 _predMap.set(node, INVALID); 932 } 933 reach(const Node & node)934 void reach(const Node& node) { 935 _numMap.set(node, _num); 936 _retMap.set(node, _num); 937 ++_num; 938 } 939 leave(const Node & node)940 void leave(const Node& node) { 941 if (_numMap[node] <= _retMap[node]) { 942 ++_compNum; 943 } 944 } 945 discover(const Arc & edge)946 void discover(const Arc& edge) { 947 _predMap.set(_graph.target(edge), edge); 948 } 949 examine(const Arc & edge)950 void examine(const Arc& edge) { 951 if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) { 952 return; 953 } 954 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 955 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 956 } 957 } 958 backtrack(const Arc & edge)959 void backtrack(const Arc& edge) { 960 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 961 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 962 } 963 } 964 965 private: 966 const Digraph& _graph; 967 int& _compNum; 968 969 typename Digraph::template NodeMap<int> _numMap; 970 typename Digraph::template NodeMap<int> _retMap; 971 typename Digraph::template NodeMap<Arc> _predMap; 972 int _num; 973 }; 974 975 template <typename Digraph, typename NodeMap> 976 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> { 977 public: 978 typedef typename Digraph::Node Node; 979 typedef typename Digraph::Arc Arc; 980 typedef typename Digraph::Edge Edge; 981 BiEdgeConnectedComponentsVisitor(const Digraph & graph,NodeMap & compMap,int & compNum)982 BiEdgeConnectedComponentsVisitor(const Digraph& graph, 983 NodeMap& compMap, int &compNum) 984 : _graph(graph), _compMap(compMap), _compNum(compNum), 985 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 986 start(const Node & node)987 void start(const Node& node) { 988 _predMap.set(node, INVALID); 989 } 990 reach(const Node & node)991 void reach(const Node& node) { 992 _numMap.set(node, _num); 993 _retMap.set(node, _num); 994 _nodeStack.push(node); 995 ++_num; 996 } 997 leave(const Node & node)998 void leave(const Node& node) { 999 if (_numMap[node] <= _retMap[node]) { 1000 while (_nodeStack.top() != node) { 1001 _compMap.set(_nodeStack.top(), _compNum); 1002 _nodeStack.pop(); 1003 } 1004 _compMap.set(node, _compNum); 1005 _nodeStack.pop(); 1006 ++_compNum; 1007 } 1008 } 1009 discover(const Arc & edge)1010 void discover(const Arc& edge) { 1011 _predMap.set(_graph.target(edge), edge); 1012 } 1013 examine(const Arc & edge)1014 void examine(const Arc& edge) { 1015 if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) { 1016 return; 1017 } 1018 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 1019 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 1020 } 1021 } 1022 backtrack(const Arc & edge)1023 void backtrack(const Arc& edge) { 1024 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 1025 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 1026 } 1027 } 1028 1029 private: 1030 const Digraph& _graph; 1031 NodeMap& _compMap; 1032 int& _compNum; 1033 1034 typename Digraph::template NodeMap<int> _numMap; 1035 typename Digraph::template NodeMap<int> _retMap; 1036 typename Digraph::template NodeMap<Arc> _predMap; 1037 std::stack<Node> _nodeStack; 1038 int _num; 1039 }; 1040 1041 1042 template <typename Digraph, typename ArcMap> 1043 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> { 1044 public: 1045 typedef typename Digraph::Node Node; 1046 typedef typename Digraph::Arc Arc; 1047 typedef typename Digraph::Edge Edge; 1048 BiEdgeConnectedCutEdgesVisitor(const Digraph & graph,ArcMap & cutMap,int & cutNum)1049 BiEdgeConnectedCutEdgesVisitor(const Digraph& graph, 1050 ArcMap& cutMap, int &cutNum) 1051 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), 1052 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} 1053 start(const Node & node)1054 void start(const Node& node) { 1055 _predMap[node] = INVALID; 1056 } 1057 reach(const Node & node)1058 void reach(const Node& node) { 1059 _numMap.set(node, _num); 1060 _retMap.set(node, _num); 1061 ++_num; 1062 } 1063 leave(const Node & node)1064 void leave(const Node& node) { 1065 if (_numMap[node] <= _retMap[node]) { 1066 if (_predMap[node] != INVALID) { 1067 _cutMap.set(_predMap[node], true); 1068 ++_cutNum; 1069 } 1070 } 1071 } 1072 discover(const Arc & edge)1073 void discover(const Arc& edge) { 1074 _predMap.set(_graph.target(edge), edge); 1075 } 1076 examine(const Arc & edge)1077 void examine(const Arc& edge) { 1078 if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) { 1079 return; 1080 } 1081 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 1082 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 1083 } 1084 } 1085 backtrack(const Arc & edge)1086 void backtrack(const Arc& edge) { 1087 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) { 1088 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]); 1089 } 1090 } 1091 1092 private: 1093 const Digraph& _graph; 1094 ArcMap& _cutMap; 1095 int& _cutNum; 1096 1097 typename Digraph::template NodeMap<int> _numMap; 1098 typename Digraph::template NodeMap<int> _retMap; 1099 typename Digraph::template NodeMap<Arc> _predMap; 1100 int _num; 1101 }; 1102 } 1103 1104 template <typename Graph> 1105 int countBiEdgeConnectedComponents(const Graph& graph); 1106 1107 /// \ingroup graph_properties 1108 /// 1109 /// \brief Check whether an undirected graph is bi-edge-connected. 1110 /// 1111 /// This function checks whether the given undirected graph is 1112 /// bi-edge-connected, i.e. any two nodes are connected with at least 1113 /// two edge-disjoint paths. 1114 /// 1115 /// \return \c true if the graph is bi-edge-connected. 1116 /// \note By definition, the empty graph is bi-edge-connected. 1117 /// 1118 /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() 1119 template <typename Graph> biEdgeConnected(const Graph & graph)1120 bool biEdgeConnected(const Graph& graph) { 1121 return countBiEdgeConnectedComponents(graph) <= 1; 1122 } 1123 1124 /// \ingroup graph_properties 1125 /// 1126 /// \brief Count the number of bi-edge-connected components of an 1127 /// undirected graph. 1128 /// 1129 /// This function counts the number of bi-edge-connected components of 1130 /// the given undirected graph. 1131 /// 1132 /// The bi-edge-connected components are the classes of an equivalence 1133 /// relation on the nodes of an undirected graph. Two nodes are in the 1134 /// same class if they are connected with at least two edge-disjoint 1135 /// paths. 1136 /// 1137 /// \return The number of bi-edge-connected components. 1138 /// 1139 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1140 template <typename Graph> countBiEdgeConnectedComponents(const Graph & graph)1141 int countBiEdgeConnectedComponents(const Graph& graph) { 1142 checkConcept<concepts::Graph, Graph>(); 1143 typedef typename Graph::NodeIt NodeIt; 1144 1145 using namespace _connectivity_bits; 1146 1147 typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor; 1148 1149 int compNum = 0; 1150 Visitor visitor(graph, compNum); 1151 1152 DfsVisit<Graph, Visitor> dfs(graph, visitor); 1153 dfs.init(); 1154 1155 for (NodeIt it(graph); it != INVALID; ++it) { 1156 if (!dfs.reached(it)) { 1157 dfs.addSource(it); 1158 dfs.start(); 1159 } 1160 } 1161 return compNum; 1162 } 1163 1164 /// \ingroup graph_properties 1165 /// 1166 /// \brief Find the bi-edge-connected components of an undirected graph. 1167 /// 1168 /// This function finds the bi-edge-connected components of the given 1169 /// undirected graph. 1170 /// 1171 /// The bi-edge-connected components are the classes of an equivalence 1172 /// relation on the nodes of an undirected graph. Two nodes are in the 1173 /// same class if they are connected with at least two edge-disjoint 1174 /// paths. 1175 /// 1176 /// \image html edge_biconnected_components.png 1177 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1178 /// 1179 /// \param graph The undirected graph. 1180 /// \retval compMap A writable node map. The values will be set from 0 to 1181 /// the number of the bi-edge-connected components minus one. Each value 1182 /// of the map will be set exactly once, and the values of a certain 1183 /// component will be set continuously. 1184 /// \return The number of bi-edge-connected components. 1185 /// 1186 /// \see biEdgeConnected(), countBiEdgeConnectedComponents() 1187 template <typename Graph, typename NodeMap> biEdgeConnectedComponents(const Graph & graph,NodeMap & compMap)1188 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { 1189 checkConcept<concepts::Graph, Graph>(); 1190 typedef typename Graph::NodeIt NodeIt; 1191 typedef typename Graph::Node Node; 1192 checkConcept<concepts::WriteMap<Node, int>, NodeMap>(); 1193 1194 using namespace _connectivity_bits; 1195 1196 typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor; 1197 1198 int compNum = 0; 1199 Visitor visitor(graph, compMap, compNum); 1200 1201 DfsVisit<Graph, Visitor> dfs(graph, visitor); 1202 dfs.init(); 1203 1204 for (NodeIt it(graph); it != INVALID; ++it) { 1205 if (!dfs.reached(it)) { 1206 dfs.addSource(it); 1207 dfs.start(); 1208 } 1209 } 1210 return compNum; 1211 } 1212 1213 /// \ingroup graph_properties 1214 /// 1215 /// \brief Find the bi-edge-connected cut edges in an undirected graph. 1216 /// 1217 /// This function finds the bi-edge-connected cut edges in the given 1218 /// undirected graph. 1219 /// 1220 /// The bi-edge-connected components are the classes of an equivalence 1221 /// relation on the nodes of an undirected graph. Two nodes are in the 1222 /// same class if they are connected with at least two edge-disjoint 1223 /// paths. 1224 /// The bi-edge-connected components are separted by the cut edges of 1225 /// the components. 1226 /// 1227 /// \param graph The undirected graph. 1228 /// \retval cutMap A writable edge map. The values will be set to \c true 1229 /// for the cut edges (exactly once for each cut edge), and will not be 1230 /// changed for other edges. 1231 /// \return The number of cut edges. 1232 /// 1233 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1234 template <typename Graph, typename EdgeMap> biEdgeConnectedCutEdges(const Graph & graph,EdgeMap & cutMap)1235 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { 1236 checkConcept<concepts::Graph, Graph>(); 1237 typedef typename Graph::NodeIt NodeIt; 1238 typedef typename Graph::Edge Edge; 1239 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>(); 1240 1241 using namespace _connectivity_bits; 1242 1243 typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor; 1244 1245 int cutNum = 0; 1246 Visitor visitor(graph, cutMap, cutNum); 1247 1248 DfsVisit<Graph, Visitor> dfs(graph, visitor); 1249 dfs.init(); 1250 1251 for (NodeIt it(graph); it != INVALID; ++it) { 1252 if (!dfs.reached(it)) { 1253 dfs.addSource(it); 1254 dfs.start(); 1255 } 1256 } 1257 return cutNum; 1258 } 1259 1260 1261 namespace _connectivity_bits { 1262 1263 template <typename Digraph, typename IntNodeMap> 1264 class TopologicalSortVisitor : public DfsVisitor<Digraph> { 1265 public: 1266 typedef typename Digraph::Node Node; 1267 typedef typename Digraph::Arc edge; 1268 TopologicalSortVisitor(IntNodeMap & order,int num)1269 TopologicalSortVisitor(IntNodeMap& order, int num) 1270 : _order(order), _num(num) {} 1271 leave(const Node & node)1272 void leave(const Node& node) { 1273 _order.set(node, --_num); 1274 } 1275 1276 private: 1277 IntNodeMap& _order; 1278 int _num; 1279 }; 1280 1281 } 1282 1283 /// \ingroup graph_properties 1284 /// 1285 /// \brief Check whether a digraph is DAG. 1286 /// 1287 /// This function checks whether the given digraph is DAG, i.e. 1288 /// \e Directed \e Acyclic \e Graph. 1289 /// \return \c true if there is no directed cycle in the digraph. 1290 /// \see acyclic() 1291 template <typename Digraph> dag(const Digraph & digraph)1292 bool dag(const Digraph& digraph) { 1293 1294 checkConcept<concepts::Digraph, Digraph>(); 1295 1296 typedef typename Digraph::Node Node; 1297 typedef typename Digraph::NodeIt NodeIt; 1298 typedef typename Digraph::Arc Arc; 1299 1300 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1301 1302 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1303 Create dfs(digraph); 1304 1305 ProcessedMap processed(digraph); 1306 dfs.processedMap(processed); 1307 1308 dfs.init(); 1309 for (NodeIt it(digraph); it != INVALID; ++it) { 1310 if (!dfs.reached(it)) { 1311 dfs.addSource(it); 1312 while (!dfs.emptyQueue()) { 1313 Arc arc = dfs.nextArc(); 1314 Node target = digraph.target(arc); 1315 if (dfs.reached(target) && !processed[target]) { 1316 return false; 1317 } 1318 dfs.processNextArc(); 1319 } 1320 } 1321 } 1322 return true; 1323 } 1324 1325 /// \ingroup graph_properties 1326 /// 1327 /// \brief Sort the nodes of a DAG into topolgical order. 1328 /// 1329 /// This function sorts the nodes of the given acyclic digraph (DAG) 1330 /// into topolgical order. 1331 /// 1332 /// \param digraph The digraph, which must be DAG. 1333 /// \retval order A writable node map. The values will be set from 0 to 1334 /// the number of the nodes in the digraph minus one. Each value of the 1335 /// map will be set exactly once, and the values will be set descending 1336 /// order. 1337 /// 1338 /// \see dag(), checkedTopologicalSort() 1339 template <typename Digraph, typename NodeMap> topologicalSort(const Digraph & digraph,NodeMap & order)1340 void topologicalSort(const Digraph& digraph, NodeMap& order) { 1341 using namespace _connectivity_bits; 1342 1343 checkConcept<concepts::Digraph, Digraph>(); 1344 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>(); 1345 1346 typedef typename Digraph::Node Node; 1347 typedef typename Digraph::NodeIt NodeIt; 1348 typedef typename Digraph::Arc Arc; 1349 1350 TopologicalSortVisitor<Digraph, NodeMap> 1351 visitor(order, countNodes(digraph)); 1352 1353 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1354 dfs(digraph, visitor); 1355 1356 dfs.init(); 1357 for (NodeIt it(digraph); it != INVALID; ++it) { 1358 if (!dfs.reached(it)) { 1359 dfs.addSource(it); 1360 dfs.start(); 1361 } 1362 } 1363 } 1364 1365 /// \ingroup graph_properties 1366 /// 1367 /// \brief Sort the nodes of a DAG into topolgical order. 1368 /// 1369 /// This function sorts the nodes of the given acyclic digraph (DAG) 1370 /// into topolgical order and also checks whether the given digraph 1371 /// is DAG. 1372 /// 1373 /// \param digraph The digraph. 1374 /// \retval order A readable and writable node map. The values will be 1375 /// set from 0 to the number of the nodes in the digraph minus one. 1376 /// Each value of the map will be set exactly once, and the values will 1377 /// be set descending order. 1378 /// \return \c false if the digraph is not DAG. 1379 /// 1380 /// \see dag(), topologicalSort() 1381 template <typename Digraph, typename NodeMap> checkedTopologicalSort(const Digraph & digraph,NodeMap & order)1382 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { 1383 using namespace _connectivity_bits; 1384 1385 checkConcept<concepts::Digraph, Digraph>(); 1386 checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>, 1387 NodeMap>(); 1388 1389 typedef typename Digraph::Node Node; 1390 typedef typename Digraph::NodeIt NodeIt; 1391 typedef typename Digraph::Arc Arc; 1392 1393 for (NodeIt it(digraph); it != INVALID; ++it) { 1394 order.set(it, -1); 1395 } 1396 1397 TopologicalSortVisitor<Digraph, NodeMap> 1398 visitor(order, countNodes(digraph)); 1399 1400 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1401 dfs(digraph, visitor); 1402 1403 dfs.init(); 1404 for (NodeIt it(digraph); it != INVALID; ++it) { 1405 if (!dfs.reached(it)) { 1406 dfs.addSource(it); 1407 while (!dfs.emptyQueue()) { 1408 Arc arc = dfs.nextArc(); 1409 Node target = digraph.target(arc); 1410 if (dfs.reached(target) && order[target] == -1) { 1411 return false; 1412 } 1413 dfs.processNextArc(); 1414 } 1415 } 1416 } 1417 return true; 1418 } 1419 1420 /// \ingroup graph_properties 1421 /// 1422 /// \brief Check whether an undirected graph is acyclic. 1423 /// 1424 /// This function checks whether the given undirected graph is acyclic. 1425 /// \return \c true if there is no cycle in the graph. 1426 /// \see dag() 1427 template <typename Graph> acyclic(const Graph & graph)1428 bool acyclic(const Graph& graph) { 1429 checkConcept<concepts::Graph, Graph>(); 1430 typedef typename Graph::Node Node; 1431 typedef typename Graph::NodeIt NodeIt; 1432 typedef typename Graph::Arc Arc; 1433 Dfs<Graph> dfs(graph); 1434 dfs.init(); 1435 for (NodeIt it(graph); it != INVALID; ++it) { 1436 if (!dfs.reached(it)) { 1437 dfs.addSource(it); 1438 while (!dfs.emptyQueue()) { 1439 Arc arc = dfs.nextArc(); 1440 Node source = graph.source(arc); 1441 Node target = graph.target(arc); 1442 if (dfs.reached(target) && 1443 dfs.predArc(source) != graph.oppositeArc(arc)) { 1444 return false; 1445 } 1446 dfs.processNextArc(); 1447 } 1448 } 1449 } 1450 return true; 1451 } 1452 1453 /// \ingroup graph_properties 1454 /// 1455 /// \brief Check whether an undirected graph is tree. 1456 /// 1457 /// This function checks whether the given undirected graph is tree. 1458 /// \return \c true if the graph is acyclic and connected. 1459 /// \see acyclic(), connected() 1460 template <typename Graph> tree(const Graph & graph)1461 bool tree(const Graph& graph) { 1462 checkConcept<concepts::Graph, Graph>(); 1463 typedef typename Graph::Node Node; 1464 typedef typename Graph::NodeIt NodeIt; 1465 typedef typename Graph::Arc Arc; 1466 if (NodeIt(graph) == INVALID) return true; 1467 Dfs<Graph> dfs(graph); 1468 dfs.init(); 1469 dfs.addSource(NodeIt(graph)); 1470 while (!dfs.emptyQueue()) { 1471 Arc arc = dfs.nextArc(); 1472 Node source = graph.source(arc); 1473 Node target = graph.target(arc); 1474 if (dfs.reached(target) && 1475 dfs.predArc(source) != graph.oppositeArc(arc)) { 1476 return false; 1477 } 1478 dfs.processNextArc(); 1479 } 1480 for (NodeIt it(graph); it != INVALID; ++it) { 1481 if (!dfs.reached(it)) { 1482 return false; 1483 } 1484 } 1485 return true; 1486 } 1487 1488 namespace _connectivity_bits { 1489 1490 template <typename Digraph> 1491 class BipartiteVisitor : public BfsVisitor<Digraph> { 1492 public: 1493 typedef typename Digraph::Arc Arc; 1494 typedef typename Digraph::Node Node; 1495 BipartiteVisitor(const Digraph & graph,bool & bipartite)1496 BipartiteVisitor(const Digraph& graph, bool& bipartite) 1497 : _graph(graph), _part(graph), _bipartite(bipartite) {} 1498 start(const Node & node)1499 void start(const Node& node) { 1500 _part[node] = true; 1501 } discover(const Arc & edge)1502 void discover(const Arc& edge) { 1503 _part.set(_graph.target(edge), !_part[_graph.source(edge)]); 1504 } examine(const Arc & edge)1505 void examine(const Arc& edge) { 1506 _bipartite = _bipartite && 1507 _part[_graph.target(edge)] != _part[_graph.source(edge)]; 1508 } 1509 1510 private: 1511 1512 const Digraph& _graph; 1513 typename Digraph::template NodeMap<bool> _part; 1514 bool& _bipartite; 1515 }; 1516 1517 template <typename Digraph, typename PartMap> 1518 class BipartitePartitionsVisitor : public BfsVisitor<Digraph> { 1519 public: 1520 typedef typename Digraph::Arc Arc; 1521 typedef typename Digraph::Node Node; 1522 BipartitePartitionsVisitor(const Digraph & graph,PartMap & part,bool & bipartite)1523 BipartitePartitionsVisitor(const Digraph& graph, 1524 PartMap& part, bool& bipartite) 1525 : _graph(graph), _part(part), _bipartite(bipartite) {} 1526 start(const Node & node)1527 void start(const Node& node) { 1528 _part.set(node, true); 1529 } discover(const Arc & edge)1530 void discover(const Arc& edge) { 1531 _part.set(_graph.target(edge), !_part[_graph.source(edge)]); 1532 } examine(const Arc & edge)1533 void examine(const Arc& edge) { 1534 _bipartite = _bipartite && 1535 _part[_graph.target(edge)] != _part[_graph.source(edge)]; 1536 } 1537 1538 private: 1539 1540 const Digraph& _graph; 1541 PartMap& _part; 1542 bool& _bipartite; 1543 }; 1544 } 1545 1546 /// \ingroup graph_properties 1547 /// 1548 /// \brief Check whether an undirected graph is bipartite. 1549 /// 1550 /// The function checks whether the given undirected graph is bipartite. 1551 /// \return \c true if the graph is bipartite. 1552 /// 1553 /// \see bipartitePartitions() 1554 template<typename Graph> bipartite(const Graph & graph)1555 bool bipartite(const Graph &graph){ 1556 using namespace _connectivity_bits; 1557 1558 checkConcept<concepts::Graph, Graph>(); 1559 1560 typedef typename Graph::NodeIt NodeIt; 1561 typedef typename Graph::ArcIt ArcIt; 1562 1563 bool bipartite = true; 1564 1565 BipartiteVisitor<Graph> 1566 visitor(graph, bipartite); 1567 BfsVisit<Graph, BipartiteVisitor<Graph> > 1568 bfs(graph, visitor); 1569 bfs.init(); 1570 for(NodeIt it(graph); it != INVALID; ++it) { 1571 if(!bfs.reached(it)){ 1572 bfs.addSource(it); 1573 while (!bfs.emptyQueue()) { 1574 bfs.processNextNode(); 1575 if (!bipartite) return false; 1576 } 1577 } 1578 } 1579 return true; 1580 } 1581 1582 /// \ingroup graph_properties 1583 /// 1584 /// \brief Find the bipartite partitions of an undirected graph. 1585 /// 1586 /// This function checks whether the given undirected graph is bipartite 1587 /// and gives back the bipartite partitions. 1588 /// 1589 /// \image html bipartite_partitions.png 1590 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth 1591 /// 1592 /// \param graph The undirected graph. 1593 /// \retval partMap A writable node map of \c bool (or convertible) value 1594 /// type. The values will be set to \c true for one component and 1595 /// \c false for the other one. 1596 /// \return \c true if the graph is bipartite, \c false otherwise. 1597 /// 1598 /// \see bipartite() 1599 template<typename Graph, typename NodeMap> bipartitePartitions(const Graph & graph,NodeMap & partMap)1600 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ 1601 using namespace _connectivity_bits; 1602 1603 checkConcept<concepts::Graph, Graph>(); 1604 checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>(); 1605 1606 typedef typename Graph::Node Node; 1607 typedef typename Graph::NodeIt NodeIt; 1608 typedef typename Graph::ArcIt ArcIt; 1609 1610 bool bipartite = true; 1611 1612 BipartitePartitionsVisitor<Graph, NodeMap> 1613 visitor(graph, partMap, bipartite); 1614 BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> > 1615 bfs(graph, visitor); 1616 bfs.init(); 1617 for(NodeIt it(graph); it != INVALID; ++it) { 1618 if(!bfs.reached(it)){ 1619 bfs.addSource(it); 1620 while (!bfs.emptyQueue()) { 1621 bfs.processNextNode(); 1622 if (!bipartite) return false; 1623 } 1624 } 1625 } 1626 return true; 1627 } 1628 1629 /// \ingroup graph_properties 1630 /// 1631 /// \brief Check whether the given graph contains no loop arcs/edges. 1632 /// 1633 /// This function returns \c true if there are no loop arcs/edges in 1634 /// the given graph. It works for both directed and undirected graphs. 1635 template <typename Graph> loopFree(const Graph & graph)1636 bool loopFree(const Graph& graph) { 1637 for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { 1638 if (graph.source(it) == graph.target(it)) return false; 1639 } 1640 return true; 1641 } 1642 1643 /// \ingroup graph_properties 1644 /// 1645 /// \brief Check whether the given graph contains no parallel arcs/edges. 1646 /// 1647 /// This function returns \c true if there are no parallel arcs/edges in 1648 /// the given graph. It works for both directed and undirected graphs. 1649 template <typename Graph> parallelFree(const Graph & graph)1650 bool parallelFree(const Graph& graph) { 1651 typename Graph::template NodeMap<int> reached(graph, 0); 1652 int cnt = 1; 1653 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1654 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1655 if (reached[graph.target(a)] == cnt) return false; 1656 reached[graph.target(a)] = cnt; 1657 } 1658 ++cnt; 1659 } 1660 return true; 1661 } 1662 1663 /// \ingroup graph_properties 1664 /// 1665 /// \brief Check whether the given graph is simple. 1666 /// 1667 /// This function returns \c true if the given graph is simple, i.e. 1668 /// it contains no loop arcs/edges and no parallel arcs/edges. 1669 /// The function works for both directed and undirected graphs. 1670 /// \see loopFree(), parallelFree() 1671 template <typename Graph> simpleGraph(const Graph & graph)1672 bool simpleGraph(const Graph& graph) { 1673 typename Graph::template NodeMap<int> reached(graph, 0); 1674 int cnt = 1; 1675 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1676 reached[n] = cnt; 1677 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1678 if (reached[graph.target(a)] == cnt) return false; 1679 reached[graph.target(a)] = cnt; 1680 } 1681 ++cnt; 1682 } 1683 return true; 1684 } 1685 1686 } //namespace lemon 1687 1688 #endif //LEMON_CONNECTIVITY_H 1689