COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 2429:fd51b552bcf2

Last change on this file since 2429:fd51b552bcf2 was 2429:fd51b552bcf2, checked in by Balazs Dezso, 13 years ago

Renaming topology doxygen group

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