COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1763:49045f2d28d4

Last change on this file since 1763:49045f2d28d4 was 1763:49045f2d28d4, checked in by Balazs Dezso, 14 years ago

pred => predEdge rename

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