COIN-OR::LEMON - Graph Library

source: lemon/lemon/connectivity.h @ 1337:4add05447ca0

Last change on this file since 1337:4add05447ca0 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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