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