COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1979:c2992fd74dad, checked in by Balazs Dezso, 14 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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