COIN-OR::LEMON - Graph Library

source: lemon/lemon/connectivity.h @ 694:dcba640438c7

Last change on this file since 694:dcba640438c7 was 694:dcba640438c7, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Bug fixes in connectivity.h (#285)

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