COIN-OR::LEMON - Graph Library

source: lemon/lemon/connectivity.h @ 451:09e416d35896

Last change on this file since 451:09e416d35896 was 433:6ff53afe98b5, checked in by Balazs Dezso <deba@…>, 15 years ago

Port topology.h as connectivity.h from SVN -r3509 (#61)

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