COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 2564:3250756f5add

Last change on this file since 2564:3250756f5add was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

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

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