COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 45.3 KB
RevLine 
[1698]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2553]5 * Copyright (C) 2003-2008
[1956]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1698]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>
[1740]23#include <lemon/bfs.h>
[1698]24#include <lemon/graph_utils.h>
[1750]25#include <lemon/graph_adaptor.h>
26#include <lemon/maps.h>
[1698]27
[2260]28#include <lemon/concepts/graph.h>
29#include <lemon/concepts/ugraph.h>
[1698]30#include <lemon/concept_check.h>
31
[1750]32#include <lemon/bin_heap.h>
[2038]33#include <lemon/bucket_heap.h>
[1750]34
35#include <stack>
36#include <functional>
37
[2429]38/// \ingroup graph_prop
[1698]39/// \file
40/// \brief Topology related algorithms
41///
42/// Topology related algorithms
43
44namespace lemon {
45
[2429]46  /// \ingroup graph_prop
[1750]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.
[1807]53  /// \note By definition, the empty graph is connected.
[1909]54  template <typename UGraph>
55  bool connected(const UGraph& graph) {
[2260]56    checkConcept<concepts::UGraph, UGraph>();
[1909]57    typedef typename UGraph::NodeIt NodeIt;
[1807]58    if (NodeIt(graph) == INVALID) return true;
[1909]59    Dfs<UGraph> dfs(graph);
[1750]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
[2429]69  /// \ingroup graph_prop
[1750]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  ///
[1793]75  /// \param graph The graph. It should be undirected.
[1750]76  /// \return The number of components
[1807]77  /// \note By definition, the empty graph consists
78  /// of zero connected components.
[1909]79  template <typename UGraph>
80  int countConnectedComponents(const UGraph &graph) {
[2260]81    checkConcept<concepts::UGraph, UGraph>();
[1909]82    typedef typename UGraph::Node Node;
83    typedef typename UGraph::Edge Edge;
[1750]84
85    typedef NullMap<Node, Edge> PredMap;
86    typedef NullMap<Node, int> DistMap;
87
88    int compNum = 0;
[1909]89    typename Bfs<UGraph>::
[1750]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();
[1909]101    for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
[1750]102      if (!bfs.reached(n)) {
103        bfs.addSource(n);
104        bfs.start();
105        ++compNum;
106      }
107    }
108    return compNum;
109  }
110
[2429]111  /// \ingroup graph_prop
[1750]112  ///
113  /// \brief Find the connected components of an undirected graph
114  ///
115  /// Find the connected components of an undirected graph.
116  ///
[1763]117  /// \image html connected_components.png
118  /// \image latex connected_components.eps "Connected components" width=\textwidth
119  ///
[1793]120  /// \param graph The graph. It should be undirected.
121  /// \retval compMap A writable node map. The values will be set from 0 to
[1750]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
[1763]126  ///
[1909]127  template <class UGraph, class NodeMap>
128  int connectedComponents(const UGraph &graph, NodeMap &compMap) {
[2260]129    checkConcept<concepts::UGraph, UGraph>();
[1909]130    typedef typename UGraph::Node Node;
131    typedef typename UGraph::Edge Edge;
[2260]132    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
[1750]133
134    typedef NullMap<Node, Edge> PredMap;
135    typedef NullMap<Node, int> DistMap;
136
137    int compNum = 0;
[1909]138    typename Bfs<UGraph>::
[1750]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();
[1909]150    for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
[1750]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
[2429]234  /// \ingroup graph_prop
[1750]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
[1817]240  /// connected with directed paths in both direction.
[1750]241  /// \return %False when the graph is not strongly connected.
242  /// \see connected
243  ///
[1807]244  /// \note By definition, the empty graph is strongly connected.
[1750]245  template <typename Graph>
246  bool stronglyConnected(const Graph& graph) {
[2260]247    checkConcept<concepts::Graph, Graph>();
[1750]248
249    typedef typename Graph::Node Node;
250    typedef typename Graph::NodeIt NodeIt;
251
[2082]252    if (NodeIt(graph) == INVALID) return true;
253
[1750]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
[2429]290  /// \ingroup graph_prop
[1750]291  ///
292  /// \brief Count the strongly connected components of a directed graph
293  ///
294  /// Count the strongly connected components of a directed graph.
[2421]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.
[1750]299  ///
[1793]300  /// \param graph The graph.
[1750]301  /// \return The number of components
[1807]302  /// \note By definition, the empty graph has zero
303  /// strongly connected components.
[1750]304  template <typename Graph>
305  int countStronglyConnectedComponents(const Graph& graph) {
[2260]306    checkConcept<concepts::Graph, Graph>();
[1750]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
[2429]354  /// \ingroup graph_prop
[1750]355  ///
356  /// \brief Find the strongly connected components of a directed graph
357  ///
[2421]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.
[1750]365  ///
[1763]366  /// \image html strongly_connected_components.png
367  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
368  ///
[1793]369  /// \param graph The graph.
370  /// \retval compMap A writable node map. The values will be set from 0 to
[2421]371  /// the number of the strongly connected components minus one. Each value
[1750]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
[1763]375  ///
[1750]376  template <typename Graph, typename NodeMap>
377  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
[2260]378    checkConcept<concepts::Graph, Graph>();
[1750]379    typedef typename Graph::Node Node;
380    typedef typename Graph::NodeIt NodeIt;
[2260]381    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
[1750]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
[2429]424  /// \ingroup graph_prop
[1750]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  ///
[1793]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.
[1750]437  ///
438  /// \return The number of cut edges
439  template <typename Graph, typename EdgeMap>
440  int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
[2260]441    checkConcept<concepts::Graph, Graph>();
[1750]442    typedef typename Graph::Node Node;
443    typedef typename Graph::Edge Edge;
444    typedef typename Graph::NodeIt NodeIt;
[2260]445    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
[1750]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
[1698]487  namespace _topology_bits {
488   
[1750]489    template <typename Graph>
[1800]490    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
[1698]491    public:
[1750]492      typedef typename Graph::Node Node;
493      typedef typename Graph::Edge Edge;
[1909]494      typedef typename Graph::UEdge UEdge;
[1698]495
[1800]496      CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
[1750]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)]);
[1698]525        }
526      }
527
[1750]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>
[1800]548    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
[1750]549    public:
550      typedef typename Graph::Node Node;
551      typedef typename Graph::Edge Edge;
[1909]552      typedef typename Graph::UEdge UEdge;
[1750]553
[1800]554      BiNodeConnectedComponentsVisitor(const Graph& graph,
[1750]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;
[1909]622      std::stack<UEdge> _edgeStack;
[1750]623      int _num;
624    };
625
626
627    template <typename Graph, typename NodeMap>
[1800]628    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
[1750]629    public:
630      typedef typename Graph::Node Node;
631      typedef typename Graph::Edge Edge;
[1909]632      typedef typename Graph::UEdge UEdge;
[1750]633
[1800]634      BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
[1750]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;
[1909]698      std::stack<UEdge> _edgeStack;
[1750]699      int _num;
700      bool rootCut;
701    };
702
703  }
704
[1909]705  template <typename UGraph>
706  int countBiNodeConnectedComponents(const UGraph& graph);
[1750]707
[2429]708  /// \ingroup graph_prop
[1750]709  ///
[1767]710  /// \brief Checks the graph is bi-node-connected.
[1750]711  ///
[1767]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
[1750]714  /// on same circle.
715  ///
716  /// \param graph The graph.
[1767]717  /// \return %True when the graph bi-node-connected.
[1909]718  template <typename UGraph>
719  bool biNodeConnected(const UGraph& graph) {
[1800]720    return countBiNodeConnectedComponents(graph) == 1;
[1750]721  }
722
[2429]723  /// \ingroup graph_prop
[1750]724  ///
725  /// \brief Count the biconnected components.
726  ///
[1767]727  /// This function finds the bi-node-connected components in an undirected
[1750]728  /// graph. The biconnected components are the classes of an equivalence
729  /// relation on the undirected edges. Two undirected edge is in relationship
730  /// when they are on same circle.
731  ///
732  /// \param graph The graph.
733  /// \return The number of components.
[1909]734  template <typename UGraph>
735  int countBiNodeConnectedComponents(const UGraph& graph) {
[2260]736    checkConcept<concepts::UGraph, UGraph>();
[1909]737    typedef typename UGraph::NodeIt NodeIt;
[1750]738
739    using namespace _topology_bits;
740
[1909]741    typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
[1750]742
743    int compNum = 0;
744    Visitor visitor(graph, compNum);
745
[1909]746    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
[1750]747    dfs.init();
748   
749    for (NodeIt it(graph); it != INVALID; ++it) {
750      if (!dfs.reached(it)) {
751        dfs.addSource(it);
752        dfs.start();
753      }
754    }
755    return compNum;
756  }
757
[2429]758  /// \ingroup graph_prop
[1750]759  ///
[1767]760  /// \brief Find the bi-node-connected components.
[1750]761  ///
[1767]762  /// This function finds the bi-node-connected components in an undirected
763  /// graph. The bi-node-connected components are the classes of an equivalence
[1750]764  /// relation on the undirected edges. Two undirected edge are in relationship
765  /// when they are on same circle.
766  ///
[1763]767  /// \image html node_biconnected_components.png
[1767]768  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
[1763]769  ///
[1750]770  /// \param graph The graph.
[1909]771  /// \retval compMap A writable uedge map. The values will be set from 0
[1793]772  /// to the number of the biconnected components minus one. Each values
[1750]773  /// of the map will be set exactly once, the values of a certain component
774  /// will be set continuously.
775  /// \return The number of components.
[1763]776  ///
[1909]777  template <typename UGraph, typename UEdgeMap>
778  int biNodeConnectedComponents(const UGraph& graph,
779                                UEdgeMap& compMap) {
[2260]780    checkConcept<concepts::UGraph, UGraph>();
[1909]781    typedef typename UGraph::NodeIt NodeIt;
782    typedef typename UGraph::UEdge UEdge;
[2260]783    checkConcept<concepts::WriteMap<UEdge, int>, UEdgeMap>();
[1750]784
785    using namespace _topology_bits;
786
[1909]787    typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
[1750]788   
789    int compNum = 0;
790    Visitor visitor(graph, compMap, compNum);
791
[1909]792    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
[1750]793    dfs.init();
794   
795    for (NodeIt it(graph); it != INVALID; ++it) {
796      if (!dfs.reached(it)) {
797        dfs.addSource(it);
798        dfs.start();
799      }
800    }
801    return compNum;
802  }
803
[2429]804  /// \ingroup graph_prop
[1750]805  ///
[1767]806  /// \brief Find the bi-node-connected cut nodes.
[1750]807  ///
[1767]808  /// This function finds the bi-node-connected cut nodes in an undirected
809  /// graph. The bi-node-connected components are the classes of an equivalence
[1750]810  /// relation on the undirected edges. Two undirected edges are in
811  /// relationship when they are on same circle. The biconnected components
812  /// are separted by nodes which are the cut nodes of the components.
813  ///
814  /// \param graph The graph.
[1793]815  /// \retval cutMap A writable edge map. The values will be set true when
[1750]816  /// the node separate two or more components.
817  /// \return The number of the cut nodes.
[1909]818  template <typename UGraph, typename NodeMap>
819  int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
[2260]820    checkConcept<concepts::UGraph, UGraph>();
[1909]821    typedef typename UGraph::Node Node;
822    typedef typename UGraph::NodeIt NodeIt;
[2260]823    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
[1750]824
825    using namespace _topology_bits;
826
[1909]827    typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
[1750]828   
829    int cutNum = 0;
830    Visitor visitor(graph, cutMap, cutNum);
831
[1909]832    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
[1750]833    dfs.init();
834   
835    for (NodeIt it(graph); it != INVALID; ++it) {
836      if (!dfs.reached(it)) {
837        dfs.addSource(it);
838        dfs.start();
839      }
840    }
841    return cutNum;
842  }
843
844  namespace _topology_bits {
845   
846    template <typename Graph>
[1800]847    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
[1750]848    public:
849      typedef typename Graph::Node Node;
850      typedef typename Graph::Edge Edge;
[1909]851      typedef typename Graph::UEdge UEdge;
[1750]852
[1800]853      CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
[1750]854        : _graph(graph), _compNum(compNum),
855          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
856
857      void start(const Node& node) {
858        _predMap.set(node, INVALID);
859      }
860     
861      void reach(const Node& node) {
862        _numMap.set(node, _num);
863        _retMap.set(node, _num);
864        ++_num;
865      }
866     
867      void leave(const Node& node) {
868        if (_numMap[node] <= _retMap[node]) {
869          ++_compNum;
870        }       
871      }
872
873      void discover(const Edge& edge) {
874        _predMap.set(_graph.target(edge), edge);
875      }
876
877      void examine(const Edge& edge) {
878        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
879          return;
880        }
881        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
882          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
883        }
884      }
885
886      void backtrack(const Edge& edge) {
887        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
888          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
889        } 
890      }
891     
892    private:
893      const Graph& _graph;
894      int& _compNum;
895
896      typename Graph::template NodeMap<int> _numMap;
897      typename Graph::template NodeMap<int> _retMap;
898      typename Graph::template NodeMap<Edge> _predMap;
899      int _num;
900    };
901
902    template <typename Graph, typename NodeMap>
[1800]903    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
[1750]904    public:
905      typedef typename Graph::Node Node;
906      typedef typename Graph::Edge Edge;
[1909]907      typedef typename Graph::UEdge UEdge;
[1750]908
[1800]909      BiEdgeConnectedComponentsVisitor(const Graph& graph,
[1750]910                                       NodeMap& compMap, int &compNum)
911        : _graph(graph), _compMap(compMap), _compNum(compNum),
912          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
913
914      void start(const Node& node) {
915        _predMap.set(node, INVALID);
916      }
917     
918      void reach(const Node& node) {
919        _numMap.set(node, _num);
920        _retMap.set(node, _num);
921        _nodeStack.push(node);
922        ++_num;
923      }
924     
925      void leave(const Node& node) {
926        if (_numMap[node] <= _retMap[node]) {
927          while (_nodeStack.top() != node) {
928            _compMap.set(_nodeStack.top(), _compNum);
929            _nodeStack.pop();
930          }
931          _compMap.set(node, _compNum);
932          _nodeStack.pop();
933          ++_compNum;
934        }       
935      }
936
937      void discover(const Edge& edge) {
938        _predMap.set(_graph.target(edge), edge);
939      }
940
941      void examine(const Edge& edge) {
942        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
943          return;
944        }
945        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
946          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
947        }
948      }
949
950      void backtrack(const Edge& edge) {
951        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
952          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
953        } 
954      }
955     
956    private:
957      const Graph& _graph;
958      NodeMap& _compMap;
959      int& _compNum;
960
961      typename Graph::template NodeMap<int> _numMap;
962      typename Graph::template NodeMap<int> _retMap;
963      typename Graph::template NodeMap<Edge> _predMap;
964      std::stack<Node> _nodeStack;
965      int _num;
966    };
967
968
969    template <typename Graph, typename EdgeMap>
[1800]970    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
[1750]971    public:
972      typedef typename Graph::Node Node;
973      typedef typename Graph::Edge Edge;
[1909]974      typedef typename Graph::UEdge UEdge;
[1750]975
[1800]976      BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
[1750]977                                     EdgeMap& cutMap, int &cutNum)
978        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
979          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
980
981      void start(const Node& node) {
982        _predMap[node] = INVALID;
983      }
984     
985      void reach(const Node& node) {
986        _numMap.set(node, _num);
987        _retMap.set(node, _num);
988        ++_num;
989      }
990     
991      void leave(const Node& node) {
992        if (_numMap[node] <= _retMap[node]) {
993          if (_predMap[node] != INVALID) {
994            _cutMap.set(_predMap[node], true);
995            ++_cutNum;
996          }
997        }       
998      }
999
1000      void discover(const Edge& edge) {
1001        _predMap.set(_graph.target(edge), edge);
1002      }
1003
1004      void examine(const Edge& edge) {
1005        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
1006          return;
1007        }
1008        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1009          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1010        }
1011      }
1012
1013      void backtrack(const Edge& edge) {
1014        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1015          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1016        } 
1017      }
1018     
1019    private:
1020      const Graph& _graph;
1021      EdgeMap& _cutMap;
1022      int& _cutNum;
1023
1024      typename Graph::template NodeMap<int> _numMap;
1025      typename Graph::template NodeMap<int> _retMap;
1026      typename Graph::template NodeMap<Edge> _predMap;
1027      int _num;
1028    };
1029  }
1030
[1909]1031  template <typename UGraph>
[2421]1032  int countBiEdgeConnectedComponents(const UGraph& graph);
[1750]1033
[2429]1034  /// \ingroup graph_prop
[1750]1035  ///
[1767]1036  /// \brief Checks that the graph is bi-edge-connected.
[1750]1037  ///
[1767]1038  /// This function checks that the graph is bi-edge-connected. The undirected
1039  /// graph is bi-edge-connected when any two nodes are connected with two
[1750]1040  /// edge-disjoint paths.
1041  ///
1042  /// \param graph The undirected graph.
1043  /// \return The number of components.
[1909]1044  template <typename UGraph>
1045  bool biEdgeConnected(const UGraph& graph) {
[1800]1046    return countBiEdgeConnectedComponents(graph) == 1;
[1750]1047  }
1048
[2429]1049  /// \ingroup graph_prop
[1750]1050  ///
[1767]1051  /// \brief Count the bi-edge-connected components.
[1750]1052  ///
[1767]1053  /// This function count the bi-edge-connected components in an undirected
1054  /// graph. The bi-edge-connected components are the classes of an equivalence
[1750]1055  /// relation on the nodes. Two nodes are in relationship when they are 
1056  /// connected with at least two edge-disjoint paths.
1057  ///
1058  /// \param graph The undirected graph.
1059  /// \return The number of components.
[1909]1060  template <typename UGraph>
1061  int countBiEdgeConnectedComponents(const UGraph& graph) {
[2260]1062    checkConcept<concepts::UGraph, UGraph>();
[1909]1063    typedef typename UGraph::NodeIt NodeIt;
[1750]1064
1065    using namespace _topology_bits;
1066
[1909]1067    typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
[1750]1068   
1069    int compNum = 0;
1070    Visitor visitor(graph, compNum);
1071
[1909]1072    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
[1750]1073    dfs.init();
1074   
1075    for (NodeIt it(graph); it != INVALID; ++it) {
1076      if (!dfs.reached(it)) {
1077        dfs.addSource(it);
1078        dfs.start();
1079      }
1080    }
1081    return compNum;
1082  }
1083
[2429]1084  /// \ingroup graph_prop
[1750]1085  ///
[1767]1086  /// \brief Find the bi-edge-connected components.
[1750]1087  ///
[1767]1088  /// This function finds the bi-edge-connected components in an undirected
1089  /// graph. The bi-edge-connected components are the classes of an equivalence
[1750]1090  /// relation on the nodes. Two nodes are in relationship when they are 
1091  /// connected at least two edge-disjoint paths.
1092  ///
[1763]1093  /// \image html edge_biconnected_components.png
[1767]1094  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
[1763]1095  ///
[1750]1096  /// \param graph The graph.
[1793]1097  /// \retval compMap A writable node map. The values will be set from 0 to
[1750]1098  /// the number of the biconnected components minus one. Each values
1099  /// of the map will be set exactly once, the values of a certain component
1100  /// will be set continuously.
1101  /// \return The number of components.
[1763]1102  ///
[1909]1103  template <typename UGraph, typename NodeMap>
1104  int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) {
[2260]1105    checkConcept<concepts::UGraph, UGraph>();
[1909]1106    typedef typename UGraph::NodeIt NodeIt;
1107    typedef typename UGraph::Node Node;
[2260]1108    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
[1750]1109
1110    using namespace _topology_bits;
1111
[1909]1112    typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
[1750]1113   
1114    int compNum = 0;
1115    Visitor visitor(graph, compMap, compNum);
1116
[1909]1117    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
[1750]1118    dfs.init();
1119   
1120    for (NodeIt it(graph); it != INVALID; ++it) {
1121      if (!dfs.reached(it)) {
1122        dfs.addSource(it);
1123        dfs.start();
1124      }
1125    }
1126    return compNum;
1127  }
1128
[2429]1129  /// \ingroup graph_prop
[1750]1130  ///
[1767]1131  /// \brief Find the bi-edge-connected cut edges.
[1750]1132  ///
[1767]1133  /// This function finds the bi-edge-connected components in an undirected
1134  /// graph. The bi-edge-connected components are the classes of an equivalence
[1750]1135  /// relation on the nodes. Two nodes are in relationship when they are
[1767]1136  /// connected with at least two edge-disjoint paths. The bi-edge-connected
[1750]1137  /// components are separted by edges which are the cut edges of the
1138  /// components.
1139  ///
1140  /// \param graph The graph.
[1793]1141  /// \retval cutMap A writable node map. The values will be set true when the
[1750]1142  /// edge is a cut edge.
1143  /// \return The number of cut edges.
[1909]1144  template <typename UGraph, typename UEdgeMap>
1145  int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) {
[2260]1146    checkConcept<concepts::UGraph, UGraph>();
[1909]1147    typedef typename UGraph::NodeIt NodeIt;
1148    typedef typename UGraph::UEdge UEdge;
[2260]1149    checkConcept<concepts::WriteMap<UEdge, bool>, UEdgeMap>();
[1750]1150
1151    using namespace _topology_bits;
1152
[1909]1153    typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
[1750]1154   
1155    int cutNum = 0;
1156    Visitor visitor(graph, cutMap, cutNum);
1157
[1909]1158    DfsVisit<UGraph, Visitor> dfs(graph, visitor);
[1750]1159    dfs.init();
1160   
1161    for (NodeIt it(graph); it != INVALID; ++it) {
1162      if (!dfs.reached(it)) {
1163        dfs.addSource(it);
1164        dfs.start();
1165      }
1166    }
1167    return cutNum;
1168  }
1169
1170
1171  namespace _topology_bits {
1172   
1173    template <typename Graph, typename IntNodeMap>
1174    class TopologicalSortVisitor : public DfsVisitor<Graph> {
1175    public:
1176      typedef typename Graph::Node Node;
1177      typedef typename Graph::Edge edge;
1178
1179      TopologicalSortVisitor(IntNodeMap& order, int num)
1180        : _order(order), _num(num) {}
1181     
1182      void leave(const Node& node) {
1183        _order.set(node, --_num);
[1698]1184      }
1185
1186    private:
[1750]1187      IntNodeMap& _order;
1188      int _num;
[1698]1189    };
[1750]1190   
[1698]1191  }
1192
[2429]1193  /// \ingroup graph_prop
[1750]1194  ///
1195  /// \brief Sort the nodes of a DAG into topolgical order.
1196  ///
1197  /// Sort the nodes of a DAG into topolgical order.
1198  ///
[1793]1199  /// \param graph The graph. It should be directed and acyclic.
1200  /// \retval order A writable node map. The values will be set from 0 to
[1750]1201  /// the number of the nodes in the graph minus one. Each values of the map
1202  /// will be set exactly once, the values  will be set descending order.
1203  ///
1204  /// \see checkedTopologicalSort
1205  /// \see dag
[1698]1206  template <typename Graph, typename NodeMap>
[1750]1207  void topologicalSort(const Graph& graph, NodeMap& order) {
1208    using namespace _topology_bits;
1209
[2260]1210    checkConcept<concepts::Graph, Graph>();
1211    checkConcept<concepts::WriteMap<typename Graph::Node, int>, NodeMap>();
[1750]1212
1213    typedef typename Graph::Node Node;
1214    typedef typename Graph::NodeIt NodeIt;
1215    typedef typename Graph::Edge Edge;
1216
1217    TopologicalSortVisitor<Graph, NodeMap>
1218      visitor(order, countNodes(graph));
1219
1220    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1221      dfs(graph, visitor);
1222
1223    dfs.init();
1224    for (NodeIt it(graph); it != INVALID; ++it) {
1225      if (!dfs.reached(it)) {
1226        dfs.addSource(it);
1227        dfs.start();
1228      }
1229    }   
1230  }
1231
[2429]1232  /// \ingroup graph_prop
[1750]1233  ///
1234  /// \brief Sort the nodes of a DAG into topolgical order.
1235  ///
1236  /// Sort the nodes of a DAG into topolgical order. It also checks
1237  /// that the given graph is DAG.
1238  ///
[1793]1239  /// \param graph The graph. It should be directed and acyclic.
[1750]1240  /// \retval order A readable - writable node map. The values will be set
1241  /// from 0 to the number of the nodes in the graph minus one. Each values
1242  /// of the map will be set exactly once, the values will be set descending
1243  /// order.
1244  /// \return %False when the graph is not DAG.
1245  ///
1246  /// \see topologicalSort
1247  /// \see dag
1248  template <typename Graph, typename NodeMap>
1249  bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
[1698]1250    using namespace _topology_bits;
1251
[2260]1252    checkConcept<concepts::Graph, Graph>();
1253    checkConcept<concepts::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
[1698]1254
1255    typedef typename Graph::Node Node;
1256    typedef typename Graph::NodeIt NodeIt;
1257    typedef typename Graph::Edge Edge;
1258
[1750]1259    order = constMap<Node, int, -1>();
[1698]1260
[1750]1261    TopologicalSortVisitor<Graph, NodeMap>
1262      visitor(order, countNodes(graph));
[1698]1263
[1750]1264    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1265      dfs(graph, visitor);
[1698]1266
1267    dfs.init();
1268    for (NodeIt it(graph); it != INVALID; ++it) {
1269      if (!dfs.reached(it)) {
1270        dfs.addSource(it);
1271        while (!dfs.emptyQueue()) {
[1750]1272          Edge edge = dfs.nextEdge();
1273          Node target = graph.target(edge);
1274          if (dfs.reached(target) && order[target] == -1) {
1275            return false;
1276          }
1277          dfs.processNextEdge();
1278        }
[1698]1279      }
[1750]1280    }
[1698]1281    return true;
1282  }
1283
[2429]1284  /// \ingroup graph_prop
[1698]1285  ///
[1750]1286  /// \brief Check that the given directed graph is a DAG.
1287  ///
1288  /// Check that the given directed graph is a DAG. The DAG is
[1698]1289  /// an Directed Acyclic Graph.
[1750]1290  /// \return %False when the graph is not DAG.
1291  /// \see acyclic
[1698]1292  template <typename Graph>
1293  bool dag(const Graph& graph) {
1294
[2260]1295    checkConcept<concepts::Graph, Graph>();
[1698]1296
1297    typedef typename Graph::Node Node;
1298    typedef typename Graph::NodeIt NodeIt;
1299    typedef typename Graph::Edge Edge;
1300
1301    typedef typename Graph::template NodeMap<bool> ProcessedMap;
1302
1303    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
[1709]1304      Create dfs(graph);
[1698]1305
1306    ProcessedMap processed(graph);
1307    dfs.processedMap(processed);
1308
1309    dfs.init();
1310    for (NodeIt it(graph); it != INVALID; ++it) {
1311      if (!dfs.reached(it)) {
1312        dfs.addSource(it);
1313        while (!dfs.emptyQueue()) {
1314          Edge edge = dfs.nextEdge();
1315          Node target = graph.target(edge);
1316          if (dfs.reached(target) && !processed[target]) {
1317            return false;
1318          }
1319          dfs.processNextEdge();
1320        }
1321      }
1322    }   
1323    return true;
1324  }
1325
[2429]1326  /// \ingroup graph_prop
[1698]1327  ///
1328  /// \brief Check that the given undirected graph is acyclic.
1329  ///
1330  /// Check that the given undirected graph acyclic.
[1750]1331  /// \param graph The undirected graph.
1332  /// \return %True when there is no circle in the graph.
1333  /// \see dag
[1909]1334  template <typename UGraph>
1335  bool acyclic(const UGraph& graph) {
[2260]1336    checkConcept<concepts::UGraph, UGraph>();
[1909]1337    typedef typename UGraph::Node Node;
1338    typedef typename UGraph::NodeIt NodeIt;
1339    typedef typename UGraph::Edge Edge;
1340    Dfs<UGraph> dfs(graph);
[1698]1341    dfs.init();
1342    for (NodeIt it(graph); it != INVALID; ++it) {
1343      if (!dfs.reached(it)) {
1344        dfs.addSource(it);
1345        while (!dfs.emptyQueue()) {
1346          Edge edge = dfs.nextEdge();
1347          Node source = graph.source(edge);
1348          Node target = graph.target(edge);
1349          if (dfs.reached(target) &&
[1763]1350              dfs.predEdge(source) != graph.oppositeEdge(edge)) {
[1698]1351            return false;
1352          }
1353          dfs.processNextEdge();
1354        }
1355      }
1356    }
1357    return true;
1358  }
1359
[2429]1360  /// \ingroup graph_prop
[1750]1361  ///
[1698]1362  /// \brief Check that the given undirected graph is tree.
1363  ///
1364  /// Check that the given undirected graph is tree.
[1750]1365  /// \param graph The undirected graph.
1366  /// \return %True when the graph is acyclic and connected.
[1909]1367  template <typename UGraph>
1368  bool tree(const UGraph& graph) {
[2260]1369    checkConcept<concepts::UGraph, UGraph>();
[1909]1370    typedef typename UGraph::Node Node;
1371    typedef typename UGraph::NodeIt NodeIt;
1372    typedef typename UGraph::Edge Edge;
1373    Dfs<UGraph> dfs(graph);
[1698]1374    dfs.init();
1375    dfs.addSource(NodeIt(graph));
1376    while (!dfs.emptyQueue()) {
1377      Edge edge = dfs.nextEdge();
1378      Node source = graph.source(edge);
1379      Node target = graph.target(edge);
1380      if (dfs.reached(target) &&
[1763]1381          dfs.predEdge(source) != graph.oppositeEdge(edge)) {
[1698]1382        return false;
1383      }
1384      dfs.processNextEdge();
1385    }
1386    for (NodeIt it(graph); it != INVALID; ++it) {
1387      if (!dfs.reached(it)) {
1388        return false;
1389      }
1390    }   
1391    return true;
1392  }
[1739]1393
[2306]1394  namespace _topology_bits {
1395
1396    template <typename Graph>
1397    class BipartiteVisitor : public BfsVisitor<Graph> {
1398    public:
1399      typedef typename Graph::Edge Edge;
1400      typedef typename Graph::Node Node;
1401
1402      BipartiteVisitor(const Graph& graph, bool& bipartite)
1403        : _graph(graph), _part(graph), _bipartite(bipartite) {}
1404     
1405      void start(const Node& node) {
1406        _part[node] = true;
1407      }
1408      void discover(const Edge& edge) {
1409        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1410      }
1411      void examine(const Edge& edge) {
1412        _bipartite = _bipartite &&
1413          _part[_graph.target(edge)] != _part[_graph.source(edge)];
1414      }
1415
1416    private:
1417
1418      const Graph& _graph;
1419      typename Graph::template NodeMap<bool> _part;
1420      bool& _bipartite;
1421    };
1422
1423    template <typename Graph, typename PartMap>
1424    class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
1425    public:
1426      typedef typename Graph::Edge Edge;
1427      typedef typename Graph::Node Node;
1428
1429      BipartitePartitionsVisitor(const Graph& graph,
1430                                 PartMap& part, bool& bipartite)
1431        : _graph(graph), _part(part), _bipartite(bipartite) {}
1432     
1433      void start(const Node& node) {
1434        _part.set(node, true);
1435      }
1436      void discover(const Edge& edge) {
1437        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1438      }
1439      void examine(const Edge& edge) {
1440        _bipartite = _bipartite &&
1441          _part[_graph.target(edge)] != _part[_graph.source(edge)];
1442      }
1443
1444    private:
1445
1446      const Graph& _graph;
1447      PartMap& _part;
1448      bool& _bipartite;
1449    };
1450  }
1451
[2429]1452  /// \ingroup graph_prop
[1739]1453  ///
[1800]1454  /// \brief Check if the given undirected graph is bipartite or not
[1750]1455  ///
[1800]1456  /// The function checks if the given undirected \c graph graph is bipartite
1457  /// or not. The \ref Bfs algorithm is used to calculate the result.
[1750]1458  /// \param graph The undirected graph.
[1800]1459  /// \return %True if \c graph is bipartite, %false otherwise.
1460  /// \sa bipartitePartitions
1461  ///
1462  /// \author Balazs Attila Mihaly 
[1909]1463  template<typename UGraph>
1464  inline bool bipartite(const UGraph &graph){
[2306]1465    using namespace _topology_bits;
1466
[2260]1467    checkConcept<concepts::UGraph, UGraph>();
[1800]1468   
[1909]1469    typedef typename UGraph::NodeIt NodeIt;
1470    typedef typename UGraph::EdgeIt EdgeIt;
[1800]1471   
[2306]1472    bool bipartite = true;
1473
1474    BipartiteVisitor<UGraph>
1475      visitor(graph, bipartite);
1476    BfsVisit<UGraph, BipartiteVisitor<UGraph> >
1477      bfs(graph, visitor);
[1800]1478    bfs.init();
[2306]1479    for(NodeIt it(graph); it != INVALID; ++it) {
1480      if(!bfs.reached(it)){
1481        bfs.addSource(it);
1482        while (!bfs.emptyQueue()) {
1483          bfs.processNextNode();
1484          if (!bipartite) return false;
1485        }
[1800]1486      }
1487    }
1488    return true;
[1979]1489  }
[1800]1490 
[2429]1491  /// \ingroup graph_prop
[1800]1492  ///
1493  /// \brief Check if the given undirected graph is bipartite or not
1494  ///
1495  /// The function checks if the given undirected graph is bipartite
1496  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
1497  /// During the execution, the \c partMap will be set as the two
1498  /// partitions of the graph.
1499  /// \param graph The undirected graph.
[1808]1500  /// \retval partMap A writable bool map of nodes. It will be set as the
[1800]1501  /// two partitions of the graph.
1502  /// \return %True if \c graph is bipartite, %false otherwise.
1503  ///
1504  /// \author Balazs Attila Mihaly 
1505  ///
1506  /// \image html bipartite_partitions.png
1507  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
[1909]1508  template<typename UGraph, typename NodeMap>
1509  inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
[2306]1510    using namespace _topology_bits;
1511
[2260]1512    checkConcept<concepts::UGraph, UGraph>();
[1800]1513   
[1909]1514    typedef typename UGraph::Node Node;
1515    typedef typename UGraph::NodeIt NodeIt;
1516    typedef typename UGraph::EdgeIt EdgeIt;
[2306]1517
1518    bool bipartite = true;
1519
1520    BipartitePartitionsVisitor<UGraph, NodeMap>
1521      visitor(graph, partMap, bipartite);
1522    BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> >
1523      bfs(graph, visitor);
[1800]1524    bfs.init();
[2306]1525    for(NodeIt it(graph); it != INVALID; ++it) {
1526      if(!bfs.reached(it)){
1527        bfs.addSource(it);
1528        while (!bfs.emptyQueue()) {
1529          bfs.processNextNode();
1530          if (!bipartite) return false;
1531        }
[1740]1532      }
1533    }
[2306]1534    return true;
1535  }
1536
1537  /// \brief Returns true when there is not loop edge in the graph.
1538  ///
1539  /// Returns true when there is not loop edge in the graph.
1540  template <typename Graph>
1541  bool loopFree(const Graph& graph) {
1542    for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
1543      if (graph.source(it) == graph.target(it)) return false;
1544    }
1545    return true;
1546  }
1547
1548  /// \brief Returns true when there is not parallel edges in the graph.
1549  ///
1550  /// Returns true when there is not parallel edges in the graph.
1551  template <typename Graph>
1552  bool parallelFree(const Graph& graph) {
1553    typename Graph::template NodeMap<bool> reached(graph, false);
1554    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1555      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1556        if (reached[graph.target(e)]) return false;
1557        reached.set(graph.target(e), true);
1558      }
1559      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1560        reached.set(graph.target(e), false);
1561      }
1562    }
1563    return true;
1564  }
1565
1566  /// \brief Returns true when there is not loop edge and parallel
1567  /// edges in the graph.
1568  ///
1569  /// Returns true when there is not loop edge and parallel edges in
1570  /// the graph.
1571  template <typename Graph>
1572  bool simpleGraph(const Graph& graph) {
1573    typename Graph::template NodeMap<bool> reached(graph, false);
1574    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1575      reached.set(n, true);
1576      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1577        if (reached[graph.target(e)]) return false;
1578        reached.set(graph.target(e), true);
1579      }
1580      for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1581        reached.set(graph.target(e), false);
1582      }
1583      reached.set(n, false);
[1800]1584    }
[1750]1585    return true;
[1979]1586  }
[1750]1587   
[1698]1588} //namespace lemon
1589
1590#endif //LEMON_TOPOLOGY_H
Note: See TracBrowser for help on using the repository browser.