COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 2218:50f1a780a5ff

Last change on this file since 2218:50f1a780a5ff was 2111:ea1fa1bc3f6d, checked in by Balazs Dezso, 18 years ago

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

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