COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1800:d391ea416aa0

Last change on this file since 1800:d391ea416aa0 was 1800:d391ea416aa0, checked in by Balazs Dezso, 18 years ago

bipartite by szakall

File size: 42.0 KB
Line 
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>
21#include <lemon/bfs.h>
22#include <lemon/graph_utils.h>
23#include <lemon/graph_adaptor.h>
24#include <lemon/maps.h>
25
26#include <lemon/concept/graph.h>
27#include <lemon/concept/undir_graph.h>
28#include <lemon/concept_check.h>
29
30#include <lemon/bin_heap.h>
31#include <lemon/linear_heap.h>
32
33#include <stack>
34#include <functional>
35
36/// \ingroup topology
37/// \file
38/// \brief Topology related algorithms
39///
40/// Topology related algorithms
41
42namespace lemon {
43
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 graph The graph. It should 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  ///
113  /// \image html connected_components.png
114  /// \image latex connected_components.eps "Connected components" width=\textwidth
115  ///
116  /// \param graph The graph. It should be undirected.
117  /// \retval compMap 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
122  ///
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  /// \warning 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 graph 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  ///
355  /// \image html strongly_connected_components.png
356  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
357  ///
358  /// \param graph The graph.
359  /// \param compMap A writable node map. The values will be set from 0 to
360  /// the number of the connected components minus one. Each values of the map
361  /// will be set exactly once, the values of a certain component will be
362  /// set continuously.
363  /// \retval compMap A writable node map. The values will be set from 0 to
364  /// the number of the strongly connected components minus one. Each values
365  /// of the map will be set exactly once, the values of a certain component
366  /// will be set continuously.
367  /// \return The number of components
368  ///
369  template <typename Graph, typename NodeMap>
370  int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
371    checkConcept<concept::StaticGraph, Graph>();
372    typedef typename Graph::Node Node;
373    typedef typename Graph::NodeIt NodeIt;
374    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
375
376    using namespace _topology_bits;
377   
378    typedef std::vector<Node> Container;
379    typedef typename Container::iterator Iterator;
380
381    Container nodes(countNodes(graph));
382    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
383    Visitor visitor(nodes.begin());
384     
385    DfsVisit<Graph, Visitor> dfs(graph, visitor);
386    dfs.init();
387    for (NodeIt it(graph); it != INVALID; ++it) {
388      if (!dfs.reached(it)) {
389        dfs.addSource(it);
390        dfs.start();
391      }
392    }
393
394    typedef typename Container::reverse_iterator RIterator;
395    typedef RevGraphAdaptor<const Graph> RGraph;
396
397    RGraph rgraph(graph);
398
399    int compNum = 0;
400
401    typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
402    RVisitor rvisitor(compMap, compNum);
403
404    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
405
406    rdfs.init();
407    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
408      if (!rdfs.reached(*it)) {
409        rdfs.addSource(*it);
410        rdfs.start();
411        ++compNum;
412      }
413    }
414    return compNum;
415  }
416
417  /// \ingroup topology
418  ///
419  /// \brief Find the cut edges of the strongly connected components.
420  ///
421  /// Find the cut edges of the strongly connected components.
422  /// The strongly connected components are the classes of an equivalence
423  /// relation on the nodes of the graph. Two nodes are in relationship
424  /// when there are directed paths between them in both direction.
425  /// The strongly connected components are separated by the cut edges.
426  ///
427  /// \param graph The graph.
428  /// \retval cutMap A writable node map. The values will be set true when the
429  /// edge is a cut edge.
430  ///
431  /// \return The number of cut edges
432  template <typename Graph, typename EdgeMap>
433  int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
434    checkConcept<concept::StaticGraph, Graph>();
435    typedef typename Graph::Node Node;
436    typedef typename Graph::Edge Edge;
437    typedef typename Graph::NodeIt NodeIt;
438    checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
439
440    using namespace _topology_bits;
441   
442    typedef std::vector<Node> Container;
443    typedef typename Container::iterator Iterator;
444
445    Container nodes(countNodes(graph));
446    typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
447    Visitor visitor(nodes.begin());
448     
449    DfsVisit<Graph, Visitor> dfs(graph, visitor);
450    dfs.init();
451    for (NodeIt it(graph); it != INVALID; ++it) {
452      if (!dfs.reached(it)) {
453        dfs.addSource(it);
454        dfs.start();
455      }
456    }
457
458    typedef typename Container::reverse_iterator RIterator;
459    typedef RevGraphAdaptor<const Graph> RGraph;
460
461    RGraph rgraph(graph);
462
463    int cutNum = 0;
464
465    typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
466    RVisitor rvisitor(rgraph, cutMap, cutNum);
467
468    DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
469
470    rdfs.init();
471    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
472      if (!rdfs.reached(*it)) {
473        rdfs.addSource(*it);
474        rdfs.start();
475      }
476    }
477    return cutNum;
478  }
479
480  namespace _topology_bits {
481   
482    template <typename Graph>
483    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
484    public:
485      typedef typename Graph::Node Node;
486      typedef typename Graph::Edge Edge;
487      typedef typename Graph::UndirEdge UndirEdge;
488
489      CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
490        : _graph(graph), _compNum(compNum),
491          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
492
493      void start(const Node& node) {
494        _predMap.set(node, INVALID);
495      }
496     
497      void reach(const Node& node) {
498        _numMap.set(node, _num);
499        _retMap.set(node, _num);
500        ++_num;
501      }
502
503      void discover(const Edge& edge) {
504        _predMap.set(_graph.target(edge), _graph.source(edge));
505      }
506
507      void examine(const Edge& edge) {
508        if (_graph.source(edge) == _graph.target(edge) &&
509            _graph.direction(edge)) {
510          ++_compNum;
511          return;
512        }
513        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
514          return;
515        }
516        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
517          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
518        }
519      }
520
521      void backtrack(const Edge& edge) {
522        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
523          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
524        } 
525        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
526          ++_compNum;
527        }
528      }
529     
530    private:
531      const Graph& _graph;
532      int& _compNum;
533
534      typename Graph::template NodeMap<int> _numMap;
535      typename Graph::template NodeMap<int> _retMap;
536      typename Graph::template NodeMap<Node> _predMap;
537      int _num;
538    };
539
540    template <typename Graph, typename EdgeMap>
541    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
542    public:
543      typedef typename Graph::Node Node;
544      typedef typename Graph::Edge Edge;
545      typedef typename Graph::UndirEdge UndirEdge;
546
547      BiNodeConnectedComponentsVisitor(const Graph& graph,
548                                       EdgeMap& compMap, int &compNum)
549        : _graph(graph), _compMap(compMap), _compNum(compNum),
550          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
551
552      void start(const Node& node) {
553        _predMap.set(node, INVALID);
554      }
555     
556      void reach(const Node& node) {
557        _numMap.set(node, _num);
558        _retMap.set(node, _num);
559        ++_num;
560      }
561
562      void discover(const Edge& edge) {
563        Node target = _graph.target(edge);
564        _predMap.set(target, edge);
565        _edgeStack.push(edge);
566      }
567
568      void examine(const Edge& edge) {
569        Node source = _graph.source(edge);
570        Node target = _graph.target(edge);
571        if (source == target && _graph.direction(edge)) {
572          _compMap.set(edge, _compNum);
573          ++_compNum;
574          return;
575        }
576        if (_numMap[target] < _numMap[source]) {
577          if (_predMap[source] != _graph.oppositeEdge(edge)) {
578            _edgeStack.push(edge);
579          }
580        }
581        if (_predMap[source] != INVALID &&
582            target == _graph.source(_predMap[source])) {
583          return;
584        }
585        if (_retMap[source] > _numMap[target]) {
586          _retMap.set(source, _numMap[target]);
587        }
588      }
589
590      void backtrack(const Edge& edge) {
591        Node source = _graph.source(edge);
592        Node target = _graph.target(edge);
593        if (_retMap[source] > _retMap[target]) {
594          _retMap.set(source, _retMap[target]);
595        } 
596        if (_numMap[source] <= _retMap[target]) {
597          while (_edgeStack.top() != edge) {
598            _compMap.set(_edgeStack.top(), _compNum);
599            _edgeStack.pop();
600          }
601          _compMap.set(edge, _compNum);
602          _edgeStack.pop();
603          ++_compNum;
604        }
605      }
606     
607    private:
608      const Graph& _graph;
609      EdgeMap& _compMap;
610      int& _compNum;
611
612      typename Graph::template NodeMap<int> _numMap;
613      typename Graph::template NodeMap<int> _retMap;
614      typename Graph::template NodeMap<Edge> _predMap;
615      std::stack<UndirEdge> _edgeStack;
616      int _num;
617    };
618
619
620    template <typename Graph, typename NodeMap>
621    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
622    public:
623      typedef typename Graph::Node Node;
624      typedef typename Graph::Edge Edge;
625      typedef typename Graph::UndirEdge UndirEdge;
626
627      BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
628                                     int& cutNum)
629        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
630          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
631
632      void start(const Node& node) {
633        _predMap.set(node, INVALID);
634        rootCut = false;
635      }
636     
637      void reach(const Node& node) {
638        _numMap.set(node, _num);
639        _retMap.set(node, _num);
640        ++_num;
641      }
642
643      void discover(const Edge& edge) {
644        _predMap.set(_graph.target(edge), _graph.source(edge));
645      }
646
647      void examine(const Edge& edge) {
648        if (_graph.source(edge) == _graph.target(edge) &&
649            _graph.direction(edge)) {
650          if (!_cutMap[_graph.source(edge)]) {
651            _cutMap.set(_graph.source(edge), true);
652            ++_cutNum;
653          }
654          return;
655        }
656        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
657        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
658          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
659        }
660      }
661
662      void backtrack(const Edge& edge) {
663        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
664          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
665        } 
666        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
667          if (_predMap[_graph.source(edge)] != INVALID) {
668            if (!_cutMap[_graph.source(edge)]) {
669              _cutMap.set(_graph.source(edge), true);
670              ++_cutNum;
671            }
672          } else if (rootCut) {
673            if (!_cutMap[_graph.source(edge)]) {
674              _cutMap.set(_graph.source(edge), true);
675              ++_cutNum;
676            }
677          } else {
678            rootCut = true;
679          }
680        }
681      }
682     
683    private:
684      const Graph& _graph;
685      NodeMap& _cutMap;
686      int& _cutNum;
687
688      typename Graph::template NodeMap<int> _numMap;
689      typename Graph::template NodeMap<int> _retMap;
690      typename Graph::template NodeMap<Node> _predMap;
691      std::stack<UndirEdge> _edgeStack;
692      int _num;
693      bool rootCut;
694    };
695
696  }
697
698  template <typename UndirGraph>
699  int countBiNodeConnectedComponents(const UndirGraph& graph);
700
701  /// \ingroup topology
702  ///
703  /// \brief Checks the graph is bi-node-connected.
704  ///
705  /// This function checks that the undirected graph is bi-node-connected 
706  /// graph. The graph is bi-node-connected if any two undirected edge is
707  /// on same circle.
708  ///
709  /// \param graph The graph.
710  /// \return %True when the graph bi-node-connected.
711  /// \todo Make it faster.
712  template <typename UndirGraph>
713  bool biNodeConnected(const UndirGraph& graph) {
714    return countBiNodeConnectedComponents(graph) == 1;
715  }
716
717  /// \ingroup topology
718  ///
719  /// \brief Count the biconnected components.
720  ///
721  /// This function finds the bi-node-connected components in an undirected
722  /// graph. The biconnected components are the classes of an equivalence
723  /// relation on the undirected edges. Two undirected edge is in relationship
724  /// when they are on same circle.
725  ///
726  /// \param graph The graph.
727  /// \return The number of components.
728  template <typename UndirGraph>
729  int countBiNodeConnectedComponents(const UndirGraph& graph) {
730    checkConcept<concept::UndirGraph, UndirGraph>();
731    typedef typename UndirGraph::NodeIt NodeIt;
732
733    using namespace _topology_bits;
734
735    typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
736
737    int compNum = 0;
738    Visitor visitor(graph, compNum);
739
740    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
741    dfs.init();
742   
743    for (NodeIt it(graph); it != INVALID; ++it) {
744      if (!dfs.reached(it)) {
745        dfs.addSource(it);
746        dfs.start();
747      }
748    }
749    return compNum;
750  }
751
752  /// \ingroup topology
753  ///
754  /// \brief Find the bi-node-connected components.
755  ///
756  /// This function finds the bi-node-connected components in an undirected
757  /// graph. The bi-node-connected components are the classes of an equivalence
758  /// relation on the undirected edges. Two undirected edge are in relationship
759  /// when they are on same circle.
760  ///
761  /// \image html node_biconnected_components.png
762  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
763  ///
764  /// \param graph The graph.
765  /// \retval compMap A writable undir edge map. The values will be set from 0
766  /// to the number of the biconnected components minus one. Each values
767  /// of the map will be set exactly once, the values of a certain component
768  /// will be set continuously.
769  /// \return The number of components.
770  ///
771  template <typename UndirGraph, typename UndirEdgeMap>
772  int biNodeConnectedComponents(const UndirGraph& graph,
773                                UndirEdgeMap& compMap) {
774    checkConcept<concept::UndirGraph, UndirGraph>();
775    typedef typename UndirGraph::NodeIt NodeIt;
776    typedef typename UndirGraph::UndirEdge UndirEdge;
777    checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
778
779    using namespace _topology_bits;
780
781    typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
782   
783    int compNum = 0;
784    Visitor visitor(graph, compMap, compNum);
785
786    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
787    dfs.init();
788   
789    for (NodeIt it(graph); it != INVALID; ++it) {
790      if (!dfs.reached(it)) {
791        dfs.addSource(it);
792        dfs.start();
793      }
794    }
795    return compNum;
796  }
797
798  /// \ingroup topology
799  ///
800  /// \brief Find the bi-node-connected cut nodes.
801  ///
802  /// This function finds the bi-node-connected cut nodes in an undirected
803  /// graph. The bi-node-connected components are the classes of an equivalence
804  /// relation on the undirected edges. Two undirected edges are in
805  /// relationship when they are on same circle. The biconnected components
806  /// are separted by nodes which are the cut nodes of the components.
807  ///
808  /// \param graph The graph.
809  /// \retval cutMap A writable edge map. The values will be set true when
810  /// the node separate two or more components.
811  /// \return The number of the cut nodes.
812  template <typename UndirGraph, typename NodeMap>
813  int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
814    checkConcept<concept::UndirGraph, UndirGraph>();
815    typedef typename UndirGraph::Node Node;
816    typedef typename UndirGraph::NodeIt NodeIt;
817    checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
818
819    using namespace _topology_bits;
820
821    typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
822   
823    int cutNum = 0;
824    Visitor visitor(graph, cutMap, cutNum);
825
826    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
827    dfs.init();
828   
829    for (NodeIt it(graph); it != INVALID; ++it) {
830      if (!dfs.reached(it)) {
831        dfs.addSource(it);
832        dfs.start();
833      }
834    }
835    return cutNum;
836  }
837
838  namespace _topology_bits {
839   
840    template <typename Graph>
841    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
842    public:
843      typedef typename Graph::Node Node;
844      typedef typename Graph::Edge Edge;
845      typedef typename Graph::UndirEdge UndirEdge;
846
847      CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
848        : _graph(graph), _compNum(compNum),
849          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
850
851      void start(const Node& node) {
852        _predMap.set(node, INVALID);
853      }
854     
855      void reach(const Node& node) {
856        _numMap.set(node, _num);
857        _retMap.set(node, _num);
858        ++_num;
859      }
860     
861      void leave(const Node& node) {
862        if (_numMap[node] <= _retMap[node]) {
863          ++_compNum;
864        }       
865      }
866
867      void discover(const Edge& edge) {
868        _predMap.set(_graph.target(edge), edge);
869      }
870
871      void examine(const Edge& edge) {
872        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
873          return;
874        }
875        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
876          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
877        }
878      }
879
880      void backtrack(const Edge& edge) {
881        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
882          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
883        } 
884      }
885     
886    private:
887      const Graph& _graph;
888      int& _compNum;
889
890      typename Graph::template NodeMap<int> _numMap;
891      typename Graph::template NodeMap<int> _retMap;
892      typename Graph::template NodeMap<Edge> _predMap;
893      int _num;
894    };
895
896    template <typename Graph, typename NodeMap>
897    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
898    public:
899      typedef typename Graph::Node Node;
900      typedef typename Graph::Edge Edge;
901      typedef typename Graph::UndirEdge UndirEdge;
902
903      BiEdgeConnectedComponentsVisitor(const Graph& graph,
904                                       NodeMap& compMap, int &compNum)
905        : _graph(graph), _compMap(compMap), _compNum(compNum),
906          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
907
908      void start(const Node& node) {
909        _predMap.set(node, INVALID);
910      }
911     
912      void reach(const Node& node) {
913        _numMap.set(node, _num);
914        _retMap.set(node, _num);
915        _nodeStack.push(node);
916        ++_num;
917      }
918     
919      void leave(const Node& node) {
920        if (_numMap[node] <= _retMap[node]) {
921          while (_nodeStack.top() != node) {
922            _compMap.set(_nodeStack.top(), _compNum);
923            _nodeStack.pop();
924          }
925          _compMap.set(node, _compNum);
926          _nodeStack.pop();
927          ++_compNum;
928        }       
929      }
930
931      void discover(const Edge& edge) {
932        _predMap.set(_graph.target(edge), edge);
933      }
934
935      void examine(const Edge& edge) {
936        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
937          return;
938        }
939        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
940          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
941        }
942      }
943
944      void backtrack(const Edge& edge) {
945        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
946          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
947        } 
948      }
949     
950    private:
951      const Graph& _graph;
952      NodeMap& _compMap;
953      int& _compNum;
954
955      typename Graph::template NodeMap<int> _numMap;
956      typename Graph::template NodeMap<int> _retMap;
957      typename Graph::template NodeMap<Edge> _predMap;
958      std::stack<Node> _nodeStack;
959      int _num;
960    };
961
962
963    template <typename Graph, typename EdgeMap>
964    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
965    public:
966      typedef typename Graph::Node Node;
967      typedef typename Graph::Edge Edge;
968      typedef typename Graph::UndirEdge UndirEdge;
969
970      BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
971                                     EdgeMap& cutMap, int &cutNum)
972        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
973          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
974
975      void start(const Node& node) {
976        _predMap[node] = INVALID;
977      }
978     
979      void reach(const Node& node) {
980        _numMap.set(node, _num);
981        _retMap.set(node, _num);
982        ++_num;
983      }
984     
985      void leave(const Node& node) {
986        if (_numMap[node] <= _retMap[node]) {
987          if (_predMap[node] != INVALID) {
988            _cutMap.set(_predMap[node], true);
989            ++_cutNum;
990          }
991        }       
992      }
993
994      void discover(const Edge& edge) {
995        _predMap.set(_graph.target(edge), edge);
996      }
997
998      void examine(const Edge& edge) {
999        if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
1000          return;
1001        }
1002        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1003          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1004        }
1005      }
1006
1007      void backtrack(const Edge& edge) {
1008        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1009          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1010        } 
1011      }
1012     
1013    private:
1014      const Graph& _graph;
1015      EdgeMap& _cutMap;
1016      int& _cutNum;
1017
1018      typename Graph::template NodeMap<int> _numMap;
1019      typename Graph::template NodeMap<int> _retMap;
1020      typename Graph::template NodeMap<Edge> _predMap;
1021      int _num;
1022    };
1023  }
1024
1025  template <typename UndirGraph>
1026  int countbiEdgeConnectedComponents(const UndirGraph& graph);
1027
1028  /// \ingroup topology
1029  ///
1030  /// \brief Checks that the graph is bi-edge-connected.
1031  ///
1032  /// This function checks that the graph is bi-edge-connected. The undirected
1033  /// graph is bi-edge-connected when any two nodes are connected with two
1034  /// edge-disjoint paths.
1035  ///
1036  /// \param graph The undirected graph.
1037  /// \return The number of components.
1038  /// \todo Make it faster.
1039  template <typename UndirGraph>
1040  bool biEdgeConnected(const UndirGraph& graph) {
1041    return countBiEdgeConnectedComponents(graph) == 1;
1042  }
1043
1044  /// \ingroup topology
1045  ///
1046  /// \brief Count the bi-edge-connected components.
1047  ///
1048  /// This function count the bi-edge-connected components in an undirected
1049  /// graph. The bi-edge-connected components are the classes of an equivalence
1050  /// relation on the nodes. Two nodes are in relationship when they are 
1051  /// connected with at least two edge-disjoint paths.
1052  ///
1053  /// \param graph The undirected graph.
1054  /// \return The number of components.
1055  template <typename UndirGraph>
1056  int countBiEdgeConnectedComponents(const UndirGraph& graph) {
1057    checkConcept<concept::UndirGraph, UndirGraph>();
1058    typedef typename UndirGraph::NodeIt NodeIt;
1059
1060    using namespace _topology_bits;
1061
1062    typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
1063   
1064    int compNum = 0;
1065    Visitor visitor(graph, compNum);
1066
1067    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1068    dfs.init();
1069   
1070    for (NodeIt it(graph); it != INVALID; ++it) {
1071      if (!dfs.reached(it)) {
1072        dfs.addSource(it);
1073        dfs.start();
1074      }
1075    }
1076    return compNum;
1077  }
1078
1079  /// \ingroup topology
1080  ///
1081  /// \brief Find the bi-edge-connected components.
1082  ///
1083  /// This function finds the bi-edge-connected components in an undirected
1084  /// graph. The bi-edge-connected components are the classes of an equivalence
1085  /// relation on the nodes. Two nodes are in relationship when they are 
1086  /// connected at least two edge-disjoint paths.
1087  ///
1088  /// \image html edge_biconnected_components.png
1089  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1090  ///
1091  /// \param graph The graph.
1092  /// \retval compMap A writable node map. The values will be set from 0 to
1093  /// the number of the biconnected components minus one. Each values
1094  /// of the map will be set exactly once, the values of a certain component
1095  /// will be set continuously.
1096  /// \return The number of components.
1097  ///
1098  template <typename UndirGraph, typename NodeMap>
1099  int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
1100    checkConcept<concept::UndirGraph, UndirGraph>();
1101    typedef typename UndirGraph::NodeIt NodeIt;
1102    typedef typename UndirGraph::Node Node;
1103    checkConcept<concept::WriteMap<Node, int>, NodeMap>();
1104
1105    using namespace _topology_bits;
1106
1107    typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
1108   
1109    int compNum = 0;
1110    Visitor visitor(graph, compMap, compNum);
1111
1112    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1113    dfs.init();
1114   
1115    for (NodeIt it(graph); it != INVALID; ++it) {
1116      if (!dfs.reached(it)) {
1117        dfs.addSource(it);
1118        dfs.start();
1119      }
1120    }
1121    return compNum;
1122  }
1123
1124  /// \ingroup topology
1125  ///
1126  /// \brief Find the bi-edge-connected cut edges.
1127  ///
1128  /// This function finds the bi-edge-connected components in an undirected
1129  /// graph. The bi-edge-connected components are the classes of an equivalence
1130  /// relation on the nodes. Two nodes are in relationship when they are
1131  /// connected with at least two edge-disjoint paths. The bi-edge-connected
1132  /// components are separted by edges which are the cut edges of the
1133  /// components.
1134  ///
1135  /// \param graph The graph.
1136  /// \retval cutMap A writable node map. The values will be set true when the
1137  /// edge is a cut edge.
1138  /// \return The number of cut edges.
1139  template <typename UndirGraph, typename UndirEdgeMap>
1140  int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {
1141    checkConcept<concept::UndirGraph, UndirGraph>();
1142    typedef typename UndirGraph::NodeIt NodeIt;
1143    typedef typename UndirGraph::UndirEdge UndirEdge;
1144    checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
1145
1146    using namespace _topology_bits;
1147
1148    typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
1149   
1150    int cutNum = 0;
1151    Visitor visitor(graph, cutMap, cutNum);
1152
1153    DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1154    dfs.init();
1155   
1156    for (NodeIt it(graph); it != INVALID; ++it) {
1157      if (!dfs.reached(it)) {
1158        dfs.addSource(it);
1159        dfs.start();
1160      }
1161    }
1162    return cutNum;
1163  }
1164
1165
1166  namespace _topology_bits {
1167   
1168    template <typename Graph, typename IntNodeMap>
1169    class TopologicalSortVisitor : public DfsVisitor<Graph> {
1170    public:
1171      typedef typename Graph::Node Node;
1172      typedef typename Graph::Edge edge;
1173
1174      TopologicalSortVisitor(IntNodeMap& order, int num)
1175        : _order(order), _num(num) {}
1176     
1177      void leave(const Node& node) {
1178        _order.set(node, --_num);
1179      }
1180
1181    private:
1182      IntNodeMap& _order;
1183      int _num;
1184    };
1185   
1186  }
1187
1188  /// \ingroup topology
1189  ///
1190  /// \brief Sort the nodes of a DAG into topolgical order.
1191  ///
1192  /// Sort the nodes of a DAG into topolgical order.
1193  ///
1194  /// \param graph The graph. It should be directed and acyclic.
1195  /// \retval order A writable node map. The values will be set from 0 to
1196  /// the number of the nodes in the graph minus one. Each values of the map
1197  /// will be set exactly once, the values  will be set descending order.
1198  ///
1199  /// \see checkedTopologicalSort
1200  /// \see dag
1201  template <typename Graph, typename NodeMap>
1202  void topologicalSort(const Graph& graph, NodeMap& order) {
1203    using namespace _topology_bits;
1204
1205    checkConcept<concept::StaticGraph, Graph>();
1206    checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
1207
1208    typedef typename Graph::Node Node;
1209    typedef typename Graph::NodeIt NodeIt;
1210    typedef typename Graph::Edge Edge;
1211
1212    TopologicalSortVisitor<Graph, NodeMap>
1213      visitor(order, countNodes(graph));
1214
1215    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1216      dfs(graph, visitor);
1217
1218    dfs.init();
1219    for (NodeIt it(graph); it != INVALID; ++it) {
1220      if (!dfs.reached(it)) {
1221        dfs.addSource(it);
1222        dfs.start();
1223      }
1224    }   
1225  }
1226
1227  /// \ingroup topology
1228  ///
1229  /// \brief Sort the nodes of a DAG into topolgical order.
1230  ///
1231  /// Sort the nodes of a DAG into topolgical order. It also checks
1232  /// that the given graph is DAG.
1233  ///
1234  /// \param graph The graph. It should be directed and acyclic.
1235  /// \retval order A readable - writable node map. The values will be set
1236  /// from 0 to the number of the nodes in the graph minus one. Each values
1237  /// of the map will be set exactly once, the values will be set descending
1238  /// order.
1239  /// \return %False when the graph is not DAG.
1240  ///
1241  /// \see topologicalSort
1242  /// \see dag
1243  template <typename Graph, typename NodeMap>
1244  bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
1245    using namespace _topology_bits;
1246
1247    checkConcept<concept::StaticGraph, Graph>();
1248    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
1249
1250    typedef typename Graph::Node Node;
1251    typedef typename Graph::NodeIt NodeIt;
1252    typedef typename Graph::Edge Edge;
1253
1254    order = constMap<Node, int, -1>();
1255
1256    TopologicalSortVisitor<Graph, NodeMap>
1257      visitor(order, countNodes(graph));
1258
1259    DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1260      dfs(graph, visitor);
1261
1262    dfs.init();
1263    for (NodeIt it(graph); it != INVALID; ++it) {
1264      if (!dfs.reached(it)) {
1265        dfs.addSource(it);
1266        while (!dfs.emptyQueue()) {
1267          Edge edge = dfs.nextEdge();
1268          Node target = graph.target(edge);
1269          if (dfs.reached(target) && order[target] == -1) {
1270            return false;
1271          }
1272          dfs.processNextEdge();
1273        }
1274      }
1275    }
1276    return true;
1277  }
1278
1279  /// \ingroup topology
1280  ///
1281  /// \brief Check that the given directed graph is a DAG.
1282  ///
1283  /// Check that the given directed graph is a DAG. The DAG is
1284  /// an Directed Acyclic Graph.
1285  /// \return %False when the graph is not DAG.
1286  /// \see acyclic
1287  template <typename Graph>
1288  bool dag(const Graph& graph) {
1289
1290    checkConcept<concept::StaticGraph, Graph>();
1291
1292    typedef typename Graph::Node Node;
1293    typedef typename Graph::NodeIt NodeIt;
1294    typedef typename Graph::Edge Edge;
1295
1296    typedef typename Graph::template NodeMap<bool> ProcessedMap;
1297
1298    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
1299      Create dfs(graph);
1300
1301    ProcessedMap processed(graph);
1302    dfs.processedMap(processed);
1303
1304    dfs.init();
1305    for (NodeIt it(graph); it != INVALID; ++it) {
1306      if (!dfs.reached(it)) {
1307        dfs.addSource(it);
1308        while (!dfs.emptyQueue()) {
1309          Edge edge = dfs.nextEdge();
1310          Node target = graph.target(edge);
1311          if (dfs.reached(target) && !processed[target]) {
1312            return false;
1313          }
1314          dfs.processNextEdge();
1315        }
1316      }
1317    }   
1318    return true;
1319  }
1320
1321  /// \ingroup topology
1322  ///
1323  /// \brief Check that the given undirected graph is acyclic.
1324  ///
1325  /// Check that the given undirected graph acyclic.
1326  /// \param graph The undirected graph.
1327  /// \return %True when there is no circle in the graph.
1328  /// \see dag
1329  template <typename UndirGraph>
1330  bool acyclic(const UndirGraph& graph) {
1331    checkConcept<concept::UndirGraph, UndirGraph>();
1332    typedef typename UndirGraph::Node Node;
1333    typedef typename UndirGraph::NodeIt NodeIt;
1334    typedef typename UndirGraph::Edge Edge;
1335    Dfs<UndirGraph> dfs(graph);
1336    dfs.init();
1337    for (NodeIt it(graph); it != INVALID; ++it) {
1338      if (!dfs.reached(it)) {
1339        dfs.addSource(it);
1340        while (!dfs.emptyQueue()) {
1341          Edge edge = dfs.nextEdge();
1342          Node source = graph.source(edge);
1343          Node target = graph.target(edge);
1344          if (dfs.reached(target) &&
1345              dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1346            return false;
1347          }
1348          dfs.processNextEdge();
1349        }
1350      }
1351    }
1352    return true;
1353  }
1354
1355  /// \ingroup topology
1356  ///
1357  /// \brief Check that the given undirected graph is tree.
1358  ///
1359  /// Check that the given undirected graph is tree.
1360  /// \param graph The undirected graph.
1361  /// \return %True when the graph is acyclic and connected.
1362  template <typename UndirGraph>
1363  bool tree(const UndirGraph& graph) {
1364    checkConcept<concept::UndirGraph, UndirGraph>();
1365    typedef typename UndirGraph::Node Node;
1366    typedef typename UndirGraph::NodeIt NodeIt;
1367    typedef typename UndirGraph::Edge Edge;
1368    Dfs<UndirGraph> dfs(graph);
1369    dfs.init();
1370    dfs.addSource(NodeIt(graph));
1371    while (!dfs.emptyQueue()) {
1372      Edge edge = dfs.nextEdge();
1373      Node source = graph.source(edge);
1374      Node target = graph.target(edge);
1375      if (dfs.reached(target) &&
1376          dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1377        return false;
1378      }
1379      dfs.processNextEdge();
1380    }
1381    for (NodeIt it(graph); it != INVALID; ++it) {
1382      if (!dfs.reached(it)) {
1383        return false;
1384      }
1385    }   
1386    return true;
1387  }
1388
1389  /// \ingroup topology
1390  ///
1391  /// \brief Check if the given undirected graph is bipartite or not
1392  ///
1393  /// The function checks if the given undirected \c graph graph is bipartite
1394  /// or not. The \ref Bfs algorithm is used to calculate the result.
1395  /// \param graph The undirected graph.
1396  /// \return %True if \c graph is bipartite, %false otherwise.
1397  /// \sa bipartitePartitions
1398  ///
1399  /// \author Balazs Attila Mihaly 
1400  template<typename UndirGraph>
1401  inline bool bipartite(const UndirGraph &graph){
1402    checkConcept<concept::UndirGraph, UndirGraph>();
1403   
1404    typedef typename UndirGraph::NodeIt NodeIt;
1405    typedef typename UndirGraph::EdgeIt EdgeIt;
1406   
1407    Bfs<UndirGraph> bfs(graph);
1408    bfs.init();
1409    for(NodeIt i(graph);i!=INVALID;++i){
1410      if(!bfs.reached(i)){
1411        bfs.run(i);
1412      }
1413    }
1414    for(EdgeIt i(graph);i!=INVALID;++i){
1415      if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
1416    }
1417    return true;
1418  };
1419 
1420  /// \ingroup topology
1421  ///
1422  /// \brief Check if the given undirected graph is bipartite or not
1423  ///
1424  /// The function checks if the given undirected graph is bipartite
1425  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
1426  /// During the execution, the \c partMap will be set as the two
1427  /// partitions of the graph.
1428  /// \param graph The undirected graph.
1429  /// \retval partMap A writeable bool map of nodes. It will be set as the
1430  /// two partitions of the graph.
1431  /// \return %True if \c graph is bipartite, %false otherwise.
1432  ///
1433  /// \author Balazs Attila Mihaly 
1434  ///
1435  /// \image html bipartite_partitions.png
1436  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1437  template<typename UndirGraph, typename NodeMap>
1438  inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
1439    checkConcept<concept::UndirGraph, UndirGraph>();
1440   
1441    typedef typename UndirGraph::Node Node;
1442    typedef typename UndirGraph::NodeIt NodeIt;
1443    typedef typename UndirGraph::EdgeIt EdgeIt;
1444 
1445    Bfs<UndirGraph> bfs(graph);
1446    bfs.init();
1447    for(NodeIt i(graph);i!=INVALID;++i){
1448      if(!bfs.reached(i)){
1449        bfs.addSource(i);
1450        for(Node j=bfs.processNextNode();!bfs.emptyQueue();
1451            j=bfs.processNextNode()){
1452          partMap.set(j,bfs.dist(j)%2==0);
1453        }
1454      }
1455    }
1456    for(EdgeIt i(graph);i!=INVALID;++i){
1457      if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
1458    }
1459    return true;
1460  };
1461   
1462} //namespace lemon
1463
1464#endif //LEMON_TOPOLOGY_H
Note: See TracBrowser for help on using the repository browser.