COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/connectivity.h @ 540:9db62975c32b

Last change on this file since 540:9db62975c32b was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 15 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 46.6 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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_CONNECTIVITY_H
20#define LEMON_CONNECTIVITY_H
21
22#include <lemon/dfs.h>
23#include <lemon/bfs.h>
24#include <lemon/core.h>
25#include <lemon/maps.h>
26#include <lemon/adaptors.h>
27
28#include <lemon/concepts/digraph.h>
29#include <lemon/concepts/graph.h>
30#include <lemon/concept_check.h>
31
32#include <stack>
33#include <functional>
34
35/// \ingroup connectivity
36/// \file
37/// \brief Connectivity algorithms
38///
39/// Connectivity algorithms
40
41namespace lemon {
42
43  /// \ingroup connectivity
44  ///
45  /// \brief Check whether the given undirected graph is connected.
46  ///
47  /// Check whether the given undirected graph is connected.
48  /// \param graph The undirected graph.
49  /// \return %True when there is path between any two nodes in the graph.
50  /// \note By definition, the empty graph is connected.
51  template <typename Graph>
52  bool connected(const Graph& graph) {
53    checkConcept<concepts::Graph, Graph>();
54    typedef typename Graph::NodeIt NodeIt;
55    if (NodeIt(graph) == INVALID) return true;
56    Dfs<Graph> dfs(graph);
57    dfs.run(NodeIt(graph));
58    for (NodeIt it(graph); it != INVALID; ++it) {
59      if (!dfs.reached(it)) {
60        return false;
61      }
62    }
63    return true;
64  }
65
66  /// \ingroup connectivity
67  ///
68  /// \brief Count the number of connected components of an undirected graph
69  ///
70  /// Count the number of connected components of an undirected graph
71  ///
72  /// \param graph The graph. It must be undirected.
73  /// \return The number of components
74  /// \note By definition, the empty graph consists
75  /// of zero connected components.
76  template <typename Graph>
77  int countConnectedComponents(const Graph &graph) {
78    checkConcept<concepts::Graph, Graph>();
79    typedef typename Graph::Node Node;
80    typedef typename Graph::Arc Arc;
81
82    typedef NullMap<Node, Arc> PredMap;
83    typedef NullMap<Node, int> DistMap;
84
85    int compNum = 0;
86    typename Bfs<Graph>::
87      template SetPredMap<PredMap>::
88      template SetDistMap<DistMap>::
89      Create bfs(graph);
90
91    PredMap predMap;
92    bfs.predMap(predMap);
93
94    DistMap distMap;
95    bfs.distMap(distMap);
96
97    bfs.init();
98    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
99      if (!bfs.reached(n)) {
100        bfs.addSource(n);
101        bfs.start();
102        ++compNum;
103      }
104    }
105    return compNum;
106  }
107
108  /// \ingroup connectivity
109  ///
110  /// \brief Find the connected components of an undirected graph
111  ///
112  /// Find the connected components of an undirected graph.
113  ///
114  /// \param graph The graph. It must be undirected.
115  /// \retval compMap A writable node map. The values will be set from 0 to
116  /// the number of the connected components minus one. Each values of the map
117  /// will be set exactly once, the values of a certain component will be
118  /// set continuously.
119  /// \return The number of components
120  ///
121  template <class Graph, class NodeMap>
122  int connectedComponents(const Graph &graph, NodeMap &compMap) {
123    checkConcept<concepts::Graph, Graph>();
124    typedef typename Graph::Node Node;
125    typedef typename Graph::Arc Arc;
126    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
127
128    typedef NullMap<Node, Arc> PredMap;
129    typedef NullMap<Node, int> DistMap;
130
131    int compNum = 0;
132    typename Bfs<Graph>::
133      template SetPredMap<PredMap>::
134      template SetDistMap<DistMap>::
135      Create bfs(graph);
136
137    PredMap predMap;
138    bfs.predMap(predMap);
139
140    DistMap distMap;
141    bfs.distMap(distMap);
142
143    bfs.init();
144    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
145      if(!bfs.reached(n)) {
146        bfs.addSource(n);
147        while (!bfs.emptyQueue()) {
148          compMap.set(bfs.nextNode(), compNum);
149          bfs.processNextNode();
150        }
151        ++compNum;
152      }
153    }
154    return compNum;
155  }
156
157  namespace _connectivity_bits {
158
159    template <typename Digraph, typename Iterator >
160    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
161    public:
162      typedef typename Digraph::Node Node;
163      LeaveOrderVisitor(Iterator it) : _it(it) {}
164
165      void leave(const Node& node) {
166        *(_it++) = node;
167      }
168
169    private:
170      Iterator _it;
171    };
172
173    template <typename Digraph, typename Map>
174    struct FillMapVisitor : public DfsVisitor<Digraph> {
175    public:
176      typedef typename Digraph::Node Node;
177      typedef typename Map::Value Value;
178
179      FillMapVisitor(Map& map, Value& value)
180        : _map(map), _value(value) {}
181
182      void reach(const Node& node) {
183        _map.set(node, _value);
184      }
185    private:
186      Map& _map;
187      Value& _value;
188    };
189
190    template <typename Digraph, typename ArcMap>
191    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
192    public:
193      typedef typename Digraph::Node Node;
194      typedef typename Digraph::Arc Arc;
195
196      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
197                                      ArcMap& cutMap,
198                                      int& cutNum)
199        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
200          _compMap(digraph, -1), _num(-1) {
201      }
202
203      void start(const Node&) {
204        ++_num;
205      }
206
207      void reach(const Node& node) {
208        _compMap.set(node, _num);
209      }
210
211      void examine(const Arc& arc) {
212         if (_compMap[_digraph.source(arc)] !=
213             _compMap[_digraph.target(arc)]) {
214           _cutMap.set(arc, true);
215           ++_cutNum;
216         }
217      }
218    private:
219      const Digraph& _digraph;
220      ArcMap& _cutMap;
221      int& _cutNum;
222
223      typename Digraph::template NodeMap<int> _compMap;
224      int _num;
225    };
226
227  }
228
229
230  /// \ingroup connectivity
231  ///
232  /// \brief Check whether the given directed graph is strongly connected.
233  ///
234  /// Check whether the given directed graph is strongly connected. The
235  /// graph is strongly connected when any two nodes of the graph are
236  /// connected with directed paths in both direction.
237  /// \return %False when the graph is not strongly connected.
238  /// \see connected
239  ///
240  /// \note By definition, the empty graph is strongly connected.
241  template <typename Digraph>
242  bool stronglyConnected(const Digraph& digraph) {
243    checkConcept<concepts::Digraph, Digraph>();
244
245    typedef typename Digraph::Node Node;
246    typedef typename Digraph::NodeIt NodeIt;
247
248    typename Digraph::Node source = NodeIt(digraph);
249    if (source == INVALID) return true;
250
251    using namespace _connectivity_bits;
252
253    typedef DfsVisitor<Digraph> Visitor;
254    Visitor visitor;
255
256    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
257    dfs.init();
258    dfs.addSource(source);
259    dfs.start();
260
261    for (NodeIt it(digraph); it != INVALID; ++it) {
262      if (!dfs.reached(it)) {
263        return false;
264      }
265    }
266
267    typedef ReverseDigraph<const Digraph> RDigraph;
268    typedef typename RDigraph::NodeIt RNodeIt;
269    RDigraph rdigraph(digraph);
270
271    typedef DfsVisitor<Digraph> RVisitor;
272    RVisitor rvisitor;
273
274    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
275    rdfs.init();
276    rdfs.addSource(source);
277    rdfs.start();
278
279    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
280      if (!rdfs.reached(it)) {
281        return false;
282      }
283    }
284
285    return true;
286  }
287
288  /// \ingroup connectivity
289  ///
290  /// \brief Count the strongly connected components of a directed graph
291  ///
292  /// Count the strongly connected components of a directed graph.
293  /// The strongly connected components are the classes of an
294  /// equivalence relation on the nodes of the graph. Two nodes are in
295  /// the same class if they are connected with directed paths in both
296  /// direction.
297  ///
298  /// \param digraph The graph.
299  /// \return The number of components
300  /// \note By definition, the empty graph has zero
301  /// strongly connected components.
302  template <typename Digraph>
303  int countStronglyConnectedComponents(const Digraph& digraph) {
304    checkConcept<concepts::Digraph, Digraph>();
305
306    using namespace _connectivity_bits;
307
308    typedef typename Digraph::Node Node;
309    typedef typename Digraph::Arc Arc;
310    typedef typename Digraph::NodeIt NodeIt;
311    typedef typename Digraph::ArcIt ArcIt;
312
313    typedef std::vector<Node> Container;
314    typedef typename Container::iterator Iterator;
315
316    Container nodes(countNodes(digraph));
317    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
318    Visitor visitor(nodes.begin());
319
320    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
321    dfs.init();
322    for (NodeIt it(digraph); 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 ReverseDigraph<const Digraph> RDigraph;
331
332    RDigraph rdigraph(digraph);
333
334    typedef DfsVisitor<Digraph> RVisitor;
335    RVisitor rvisitor;
336
337    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, 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 connectivity
353  ///
354  /// \brief Find the strongly connected components of a directed graph
355  ///
356  /// Find the strongly connected components of a directed graph.  The
357  /// strongly connected components are the classes of an equivalence
358  /// relation on the nodes of the graph. Two nodes are in
359  /// relationship when there are directed paths between them in both
360  /// direction. In addition, the numbering of components will satisfy
361  /// that there is no arc going from a higher numbered component to
362  /// a lower.
363  ///
364  /// \param digraph The digraph.
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 value
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 Digraph, typename NodeMap>
372  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
373    checkConcept<concepts::Digraph, Digraph>();
374    typedef typename Digraph::Node Node;
375    typedef typename Digraph::NodeIt NodeIt;
376    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
377
378    using namespace _connectivity_bits;
379
380    typedef std::vector<Node> Container;
381    typedef typename Container::iterator Iterator;
382
383    Container nodes(countNodes(digraph));
384    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
385    Visitor visitor(nodes.begin());
386
387    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
388    dfs.init();
389    for (NodeIt it(digraph); 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 ReverseDigraph<const Digraph> RDigraph;
398
399    RDigraph rdigraph(digraph);
400
401    int compNum = 0;
402
403    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
404    RVisitor rvisitor(compMap, compNum);
405
406    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, 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 connectivity
420  ///
421  /// \brief Find the cut arcs of the strongly connected components.
422  ///
423  /// Find the cut arcs 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 arcs.
428  ///
429  /// \param graph The graph.
430  /// \retval cutMap A writable node map. The values will be set true when the
431  /// arc is a cut arc.
432  ///
433  /// \return The number of cut arcs
434  template <typename Digraph, typename ArcMap>
435  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
436    checkConcept<concepts::Digraph, Digraph>();
437    typedef typename Digraph::Node Node;
438    typedef typename Digraph::Arc Arc;
439    typedef typename Digraph::NodeIt NodeIt;
440    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
441
442    using namespace _connectivity_bits;
443
444    typedef std::vector<Node> Container;
445    typedef typename Container::iterator Iterator;
446
447    Container nodes(countNodes(graph));
448    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
449    Visitor visitor(nodes.begin());
450
451    DfsVisit<Digraph, 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 ReverseDigraph<const Digraph> RDigraph;
462
463    RDigraph rgraph(graph);
464
465    int cutNum = 0;
466
467    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
468    RVisitor rvisitor(rgraph, cutMap, cutNum);
469
470    DfsVisit<RDigraph, 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 _connectivity_bits {
483
484    template <typename Digraph>
485    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
486    public:
487      typedef typename Digraph::Node Node;
488      typedef typename Digraph::Arc Arc;
489      typedef typename Digraph::Edge Edge;
490
491      CountBiNodeConnectedComponentsVisitor(const Digraph& 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 Arc& edge) {
506        _predMap.set(_graph.target(edge), _graph.source(edge));
507      }
508
509      void examine(const Arc& 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 Arc& 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 Digraph& _graph;
534      int& _compNum;
535
536      typename Digraph::template NodeMap<int> _numMap;
537      typename Digraph::template NodeMap<int> _retMap;
538      typename Digraph::template NodeMap<Node> _predMap;
539      int _num;
540    };
541
542    template <typename Digraph, typename ArcMap>
543    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
544    public:
545      typedef typename Digraph::Node Node;
546      typedef typename Digraph::Arc Arc;
547      typedef typename Digraph::Edge Edge;
548
549      BiNodeConnectedComponentsVisitor(const Digraph& graph,
550                                       ArcMap& 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 Arc& edge) {
565        Node target = _graph.target(edge);
566        _predMap.set(target, edge);
567        _edgeStack.push(edge);
568      }
569
570      void examine(const Arc& 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.oppositeArc(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 Arc& 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 Digraph& _graph;
611      ArcMap& _compMap;
612      int& _compNum;
613
614      typename Digraph::template NodeMap<int> _numMap;
615      typename Digraph::template NodeMap<int> _retMap;
616      typename Digraph::template NodeMap<Arc> _predMap;
617      std::stack<Edge> _edgeStack;
618      int _num;
619    };
620
621
622    template <typename Digraph, typename NodeMap>
623    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
624    public:
625      typedef typename Digraph::Node Node;
626      typedef typename Digraph::Arc Arc;
627      typedef typename Digraph::Edge Edge;
628
629      BiNodeConnectedCutNodesVisitor(const Digraph& 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 Arc& edge) {
646        _predMap.set(_graph.target(edge), _graph.source(edge));
647      }
648
649      void examine(const Arc& 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 Arc& 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 Digraph& _graph;
687      NodeMap& _cutMap;
688      int& _cutNum;
689
690      typename Digraph::template NodeMap<int> _numMap;
691      typename Digraph::template NodeMap<int> _retMap;
692      typename Digraph::template NodeMap<Node> _predMap;
693      std::stack<Edge> _edgeStack;
694      int _num;
695      bool rootCut;
696    };
697
698  }
699
700  template <typename Graph>
701  int countBiNodeConnectedComponents(const Graph& graph);
702
703  /// \ingroup connectivity
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  template <typename Graph>
714  bool biNodeConnected(const Graph& graph) {
715    return countBiNodeConnectedComponents(graph) <= 1;
716  }
717
718  /// \ingroup connectivity
719  ///
720  /// \brief Count the biconnected components.
721  ///
722  /// This function finds the bi-node-connected components in an undirected
723  /// graph. The biconnected components are the classes of an equivalence
724  /// relation on the undirected edges. Two undirected edge is in relationship
725  /// when they are on same circle.
726  ///
727  /// \param graph The graph.
728  /// \return The number of components.
729  template <typename Graph>
730  int countBiNodeConnectedComponents(const Graph& graph) {
731    checkConcept<concepts::Graph, Graph>();
732    typedef typename Graph::NodeIt NodeIt;
733
734    using namespace _connectivity_bits;
735
736    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
737
738    int compNum = 0;
739    Visitor visitor(graph, compNum);
740
741    DfsVisit<Graph, Visitor> dfs(graph, visitor);
742    dfs.init();
743
744    for (NodeIt it(graph); it != INVALID; ++it) {
745      if (!dfs.reached(it)) {
746        dfs.addSource(it);
747        dfs.start();
748      }
749    }
750    return compNum;
751  }
752
753  /// \ingroup connectivity
754  ///
755  /// \brief Find the bi-node-connected components.
756  ///
757  /// This function finds the bi-node-connected components in an undirected
758  /// graph. The bi-node-connected components are the classes of an equivalence
759  /// relation on the undirected edges. Two undirected edge are in relationship
760  /// when they are on same circle.
761  ///
762  /// \param graph The graph.
763  /// \retval compMap A writable uedge map. The values will be set from 0
764  /// to the number of the biconnected components minus one. Each values
765  /// of the map will be set exactly once, the values of a certain component
766  /// will be set continuously.
767  /// \return The number of components.
768  ///
769  template <typename Graph, typename EdgeMap>
770  int biNodeConnectedComponents(const Graph& graph,
771                                EdgeMap& compMap) {
772    checkConcept<concepts::Graph, Graph>();
773    typedef typename Graph::NodeIt NodeIt;
774    typedef typename Graph::Edge Edge;
775    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
776
777    using namespace _connectivity_bits;
778
779    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
780
781    int compNum = 0;
782    Visitor visitor(graph, compMap, compNum);
783
784    DfsVisit<Graph, Visitor> dfs(graph, visitor);
785    dfs.init();
786
787    for (NodeIt it(graph); it != INVALID; ++it) {
788      if (!dfs.reached(it)) {
789        dfs.addSource(it);
790        dfs.start();
791      }
792    }
793    return compNum;
794  }
795
796  /// \ingroup connectivity
797  ///
798  /// \brief Find the bi-node-connected cut nodes.
799  ///
800  /// This function finds the bi-node-connected cut nodes in an undirected
801  /// graph. The bi-node-connected components are the classes of an equivalence
802  /// relation on the undirected edges. Two undirected edges are in
803  /// relationship when they are on same circle. The biconnected components
804  /// are separted by nodes which are the cut nodes of the components.
805  ///
806  /// \param graph The graph.
807  /// \retval cutMap A writable edge map. The values will be set true when
808  /// the node separate two or more components.
809  /// \return The number of the cut nodes.
810  template <typename Graph, typename NodeMap>
811  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
812    checkConcept<concepts::Graph, Graph>();
813    typedef typename Graph::Node Node;
814    typedef typename Graph::NodeIt NodeIt;
815    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
816
817    using namespace _connectivity_bits;
818
819    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
820
821    int cutNum = 0;
822    Visitor visitor(graph, cutMap, cutNum);
823
824    DfsVisit<Graph, Visitor> dfs(graph, visitor);
825    dfs.init();
826
827    for (NodeIt it(graph); it != INVALID; ++it) {
828      if (!dfs.reached(it)) {
829        dfs.addSource(it);
830        dfs.start();
831      }
832    }
833    return cutNum;
834  }
835
836  namespace _connectivity_bits {
837
838    template <typename Digraph>
839    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
840    public:
841      typedef typename Digraph::Node Node;
842      typedef typename Digraph::Arc Arc;
843      typedef typename Digraph::Edge Edge;
844
845      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
846        : _graph(graph), _compNum(compNum),
847          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
848
849      void start(const Node& node) {
850        _predMap.set(node, INVALID);
851      }
852
853      void reach(const Node& node) {
854        _numMap.set(node, _num);
855        _retMap.set(node, _num);
856        ++_num;
857      }
858
859      void leave(const Node& node) {
860        if (_numMap[node] <= _retMap[node]) {
861          ++_compNum;
862        }
863      }
864
865      void discover(const Arc& edge) {
866        _predMap.set(_graph.target(edge), edge);
867      }
868
869      void examine(const Arc& edge) {
870        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
871          return;
872        }
873        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
874          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
875        }
876      }
877
878      void backtrack(const Arc& edge) {
879        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
880          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
881        }
882      }
883
884    private:
885      const Digraph& _graph;
886      int& _compNum;
887
888      typename Digraph::template NodeMap<int> _numMap;
889      typename Digraph::template NodeMap<int> _retMap;
890      typename Digraph::template NodeMap<Arc> _predMap;
891      int _num;
892    };
893
894    template <typename Digraph, typename NodeMap>
895    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
896    public:
897      typedef typename Digraph::Node Node;
898      typedef typename Digraph::Arc Arc;
899      typedef typename Digraph::Edge Edge;
900
901      BiEdgeConnectedComponentsVisitor(const Digraph& graph,
902                                       NodeMap& compMap, int &compNum)
903        : _graph(graph), _compMap(compMap), _compNum(compNum),
904          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
905
906      void start(const Node& node) {
907        _predMap.set(node, INVALID);
908      }
909
910      void reach(const Node& node) {
911        _numMap.set(node, _num);
912        _retMap.set(node, _num);
913        _nodeStack.push(node);
914        ++_num;
915      }
916
917      void leave(const Node& node) {
918        if (_numMap[node] <= _retMap[node]) {
919          while (_nodeStack.top() != node) {
920            _compMap.set(_nodeStack.top(), _compNum);
921            _nodeStack.pop();
922          }
923          _compMap.set(node, _compNum);
924          _nodeStack.pop();
925          ++_compNum;
926        }
927      }
928
929      void discover(const Arc& edge) {
930        _predMap.set(_graph.target(edge), edge);
931      }
932
933      void examine(const Arc& edge) {
934        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
935          return;
936        }
937        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
938          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
939        }
940      }
941
942      void backtrack(const Arc& edge) {
943        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
944          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
945        }
946      }
947
948    private:
949      const Digraph& _graph;
950      NodeMap& _compMap;
951      int& _compNum;
952
953      typename Digraph::template NodeMap<int> _numMap;
954      typename Digraph::template NodeMap<int> _retMap;
955      typename Digraph::template NodeMap<Arc> _predMap;
956      std::stack<Node> _nodeStack;
957      int _num;
958    };
959
960
961    template <typename Digraph, typename ArcMap>
962    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
963    public:
964      typedef typename Digraph::Node Node;
965      typedef typename Digraph::Arc Arc;
966      typedef typename Digraph::Edge Edge;
967
968      BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
969                                     ArcMap& cutMap, int &cutNum)
970        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
971          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
972
973      void start(const Node& node) {
974        _predMap[node] = INVALID;
975      }
976
977      void reach(const Node& node) {
978        _numMap.set(node, _num);
979        _retMap.set(node, _num);
980        ++_num;
981      }
982
983      void leave(const Node& node) {
984        if (_numMap[node] <= _retMap[node]) {
985          if (_predMap[node] != INVALID) {
986            _cutMap.set(_predMap[node], true);
987            ++_cutNum;
988          }
989        }
990      }
991
992      void discover(const Arc& edge) {
993        _predMap.set(_graph.target(edge), edge);
994      }
995
996      void examine(const Arc& edge) {
997        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
998          return;
999        }
1000        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1001          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1002        }
1003      }
1004
1005      void backtrack(const Arc& edge) {
1006        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1007          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1008        }
1009      }
1010
1011    private:
1012      const Digraph& _graph;
1013      ArcMap& _cutMap;
1014      int& _cutNum;
1015
1016      typename Digraph::template NodeMap<int> _numMap;
1017      typename Digraph::template NodeMap<int> _retMap;
1018      typename Digraph::template NodeMap<Arc> _predMap;
1019      int _num;
1020    };
1021  }
1022
1023  template <typename Graph>
1024  int countBiEdgeConnectedComponents(const Graph& graph);
1025
1026  /// \ingroup connectivity
1027  ///
1028  /// \brief Checks that the graph is bi-edge-connected.
1029  ///
1030  /// This function checks that the graph is bi-edge-connected. The undirected
1031  /// graph is bi-edge-connected when any two nodes are connected with two
1032  /// edge-disjoint paths.
1033  ///
1034  /// \param graph The undirected graph.
1035  /// \return The number of components.
1036  template <typename Graph>
1037  bool biEdgeConnected(const Graph& graph) {
1038    return countBiEdgeConnectedComponents(graph) <= 1;
1039  }
1040
1041  /// \ingroup connectivity
1042  ///
1043  /// \brief Count the bi-edge-connected components.
1044  ///
1045  /// This function count the bi-edge-connected components in an undirected
1046  /// graph. The bi-edge-connected components are the classes of an equivalence
1047  /// relation on the nodes. Two nodes are in relationship when they are
1048  /// connected with at least two edge-disjoint paths.
1049  ///
1050  /// \param graph The undirected graph.
1051  /// \return The number of components.
1052  template <typename Graph>
1053  int countBiEdgeConnectedComponents(const Graph& graph) {
1054    checkConcept<concepts::Graph, Graph>();
1055    typedef typename Graph::NodeIt NodeIt;
1056
1057    using namespace _connectivity_bits;
1058
1059    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
1060
1061    int compNum = 0;
1062    Visitor visitor(graph, compNum);
1063
1064    DfsVisit<Graph, Visitor> dfs(graph, visitor);
1065    dfs.init();
1066
1067    for (NodeIt it(graph); it != INVALID; ++it) {
1068      if (!dfs.reached(it)) {
1069        dfs.addSource(it);
1070        dfs.start();
1071      }
1072    }
1073    return compNum;
1074  }
1075
1076  /// \ingroup connectivity
1077  ///
1078  /// \brief Find the bi-edge-connected components.
1079  ///
1080  /// This function finds the bi-edge-connected components in an undirected
1081  /// graph. The bi-edge-connected components are the classes of an equivalence
1082  /// relation on the nodes. Two nodes are in relationship when they are
1083  /// connected at least two edge-disjoint paths.
1084  ///
1085  /// \param graph The graph.
1086  /// \retval compMap A writable node map. The values will be set from 0 to
1087  /// the number of the biconnected components minus one. Each values
1088  /// of the map will be set exactly once, the values of a certain component
1089  /// will be set continuously.
1090  /// \return The number of components.
1091  ///
1092  template <typename Graph, typename NodeMap>
1093  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1094    checkConcept<concepts::Graph, Graph>();
1095    typedef typename Graph::NodeIt NodeIt;
1096    typedef typename Graph::Node Node;
1097    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1098
1099    using namespace _connectivity_bits;
1100
1101    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
1102
1103    int compNum = 0;
1104    Visitor visitor(graph, compMap, compNum);
1105
1106    DfsVisit<Graph, Visitor> dfs(graph, visitor);
1107    dfs.init();
1108
1109    for (NodeIt it(graph); it != INVALID; ++it) {
1110      if (!dfs.reached(it)) {
1111        dfs.addSource(it);
1112        dfs.start();
1113      }
1114    }
1115    return compNum;
1116  }
1117
1118  /// \ingroup connectivity
1119  ///
1120  /// \brief Find the bi-edge-connected cut edges.
1121  ///
1122  /// This function finds the bi-edge-connected components in an undirected
1123  /// graph. The bi-edge-connected components are the classes of an equivalence
1124  /// relation on the nodes. Two nodes are in relationship when they are
1125  /// connected with at least two edge-disjoint paths. The bi-edge-connected
1126  /// components are separted by edges which are the cut edges of the
1127  /// components.
1128  ///
1129  /// \param graph The graph.
1130  /// \retval cutMap A writable node map. The values will be set true when the
1131  /// edge is a cut edge.
1132  /// \return The number of cut edges.
1133  template <typename Graph, typename EdgeMap>
1134  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1135    checkConcept<concepts::Graph, Graph>();
1136    typedef typename Graph::NodeIt NodeIt;
1137    typedef typename Graph::Edge Edge;
1138    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
1139
1140    using namespace _connectivity_bits;
1141
1142    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
1143
1144    int cutNum = 0;
1145    Visitor visitor(graph, cutMap, cutNum);
1146
1147    DfsVisit<Graph, Visitor> dfs(graph, visitor);
1148    dfs.init();
1149
1150    for (NodeIt it(graph); it != INVALID; ++it) {
1151      if (!dfs.reached(it)) {
1152        dfs.addSource(it);
1153        dfs.start();
1154      }
1155    }
1156    return cutNum;
1157  }
1158
1159
1160  namespace _connectivity_bits {
1161
1162    template <typename Digraph, typename IntNodeMap>
1163    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
1164    public:
1165      typedef typename Digraph::Node Node;
1166      typedef typename Digraph::Arc edge;
1167
1168      TopologicalSortVisitor(IntNodeMap& order, int num)
1169        : _order(order), _num(num) {}
1170
1171      void leave(const Node& node) {
1172        _order.set(node, --_num);
1173      }
1174
1175    private:
1176      IntNodeMap& _order;
1177      int _num;
1178    };
1179
1180  }
1181
1182  /// \ingroup connectivity
1183  ///
1184  /// \brief Sort the nodes of a DAG into topolgical order.
1185  ///
1186  /// Sort the nodes of a DAG into topolgical order.
1187  ///
1188  /// \param graph The graph. It must be directed and acyclic.
1189  /// \retval order A writable node map. The values will be set from 0 to
1190  /// the number of the nodes in the graph minus one. Each values of the map
1191  /// will be set exactly once, the values  will be set descending order.
1192  ///
1193  /// \see checkedTopologicalSort
1194  /// \see dag
1195  template <typename Digraph, typename NodeMap>
1196  void topologicalSort(const Digraph& graph, NodeMap& order) {
1197    using namespace _connectivity_bits;
1198
1199    checkConcept<concepts::Digraph, Digraph>();
1200    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
1201
1202    typedef typename Digraph::Node Node;
1203    typedef typename Digraph::NodeIt NodeIt;
1204    typedef typename Digraph::Arc Arc;
1205
1206    TopologicalSortVisitor<Digraph, NodeMap>
1207      visitor(order, countNodes(graph));
1208
1209    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1210      dfs(graph, visitor);
1211
1212    dfs.init();
1213    for (NodeIt it(graph); it != INVALID; ++it) {
1214      if (!dfs.reached(it)) {
1215        dfs.addSource(it);
1216        dfs.start();
1217      }
1218    }
1219  }
1220
1221  /// \ingroup connectivity
1222  ///
1223  /// \brief Sort the nodes of a DAG into topolgical order.
1224  ///
1225  /// Sort the nodes of a DAG into topolgical order. It also checks
1226  /// that the given graph is DAG.
1227  ///
1228  /// \param digraph The graph. It must be directed and acyclic.
1229  /// \retval order A readable - writable node map. The values will be set
1230  /// from 0 to the number of the nodes in the graph minus one. Each values
1231  /// of the map will be set exactly once, the values will be set descending
1232  /// order.
1233  /// \return %False when the graph is not DAG.
1234  ///
1235  /// \see topologicalSort
1236  /// \see dag
1237  template <typename Digraph, typename NodeMap>
1238  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1239    using namespace _connectivity_bits;
1240
1241    checkConcept<concepts::Digraph, Digraph>();
1242    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
1243      NodeMap>();
1244
1245    typedef typename Digraph::Node Node;
1246    typedef typename Digraph::NodeIt NodeIt;
1247    typedef typename Digraph::Arc Arc;
1248
1249    for (NodeIt it(digraph); it != INVALID; ++it) {
1250      order.set(it, -1);
1251    }
1252
1253    TopologicalSortVisitor<Digraph, NodeMap>
1254      visitor(order, countNodes(digraph));
1255
1256    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1257      dfs(digraph, visitor);
1258
1259    dfs.init();
1260    for (NodeIt it(digraph); it != INVALID; ++it) {
1261      if (!dfs.reached(it)) {
1262        dfs.addSource(it);
1263        while (!dfs.emptyQueue()) {
1264           Arc arc = dfs.nextArc();
1265           Node target = digraph.target(arc);
1266           if (dfs.reached(target) && order[target] == -1) {
1267             return false;
1268           }
1269           dfs.processNextArc();
1270         }
1271      }
1272    }
1273    return true;
1274  }
1275
1276  /// \ingroup connectivity
1277  ///
1278  /// \brief Check that the given directed graph is a DAG.
1279  ///
1280  /// Check that the given directed graph is a DAG. The DAG is
1281  /// an Directed Acyclic Digraph.
1282  /// \return %False when the graph is not DAG.
1283  /// \see acyclic
1284  template <typename Digraph>
1285  bool dag(const Digraph& digraph) {
1286
1287    checkConcept<concepts::Digraph, Digraph>();
1288
1289    typedef typename Digraph::Node Node;
1290    typedef typename Digraph::NodeIt NodeIt;
1291    typedef typename Digraph::Arc Arc;
1292
1293    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1294
1295    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1296      Create dfs(digraph);
1297
1298    ProcessedMap processed(digraph);
1299    dfs.processedMap(processed);
1300
1301    dfs.init();
1302    for (NodeIt it(digraph); it != INVALID; ++it) {
1303      if (!dfs.reached(it)) {
1304        dfs.addSource(it);
1305        while (!dfs.emptyQueue()) {
1306          Arc edge = dfs.nextArc();
1307          Node target = digraph.target(edge);
1308          if (dfs.reached(target) && !processed[target]) {
1309            return false;
1310          }
1311          dfs.processNextArc();
1312        }
1313      }
1314    }
1315    return true;
1316  }
1317
1318  /// \ingroup connectivity
1319  ///
1320  /// \brief Check that the given undirected graph is acyclic.
1321  ///
1322  /// Check that the given undirected graph acyclic.
1323  /// \param graph The undirected graph.
1324  /// \return %True when there is no circle in the graph.
1325  /// \see dag
1326  template <typename Graph>
1327  bool acyclic(const Graph& graph) {
1328    checkConcept<concepts::Graph, Graph>();
1329    typedef typename Graph::Node Node;
1330    typedef typename Graph::NodeIt NodeIt;
1331    typedef typename Graph::Arc Arc;
1332    Dfs<Graph> dfs(graph);
1333    dfs.init();
1334    for (NodeIt it(graph); it != INVALID; ++it) {
1335      if (!dfs.reached(it)) {
1336        dfs.addSource(it);
1337        while (!dfs.emptyQueue()) {
1338          Arc edge = dfs.nextArc();
1339          Node source = graph.source(edge);
1340          Node target = graph.target(edge);
1341          if (dfs.reached(target) &&
1342              dfs.predArc(source) != graph.oppositeArc(edge)) {
1343            return false;
1344          }
1345          dfs.processNextArc();
1346        }
1347      }
1348    }
1349    return true;
1350  }
1351
1352  /// \ingroup connectivity
1353  ///
1354  /// \brief Check that the given undirected graph is tree.
1355  ///
1356  /// Check that the given undirected graph is tree.
1357  /// \param graph The undirected graph.
1358  /// \return %True when the graph is acyclic and connected.
1359  template <typename Graph>
1360  bool tree(const Graph& graph) {
1361    checkConcept<concepts::Graph, Graph>();
1362    typedef typename Graph::Node Node;
1363    typedef typename Graph::NodeIt NodeIt;
1364    typedef typename Graph::Arc Arc;
1365    Dfs<Graph> dfs(graph);
1366    dfs.init();
1367    dfs.addSource(NodeIt(graph));
1368    while (!dfs.emptyQueue()) {
1369      Arc edge = dfs.nextArc();
1370      Node source = graph.source(edge);
1371      Node target = graph.target(edge);
1372      if (dfs.reached(target) &&
1373          dfs.predArc(source) != graph.oppositeArc(edge)) {
1374        return false;
1375      }
1376      dfs.processNextArc();
1377    }
1378    for (NodeIt it(graph); it != INVALID; ++it) {
1379      if (!dfs.reached(it)) {
1380        return false;
1381      }
1382    }
1383    return true;
1384  }
1385
1386  namespace _connectivity_bits {
1387
1388    template <typename Digraph>
1389    class BipartiteVisitor : public BfsVisitor<Digraph> {
1390    public:
1391      typedef typename Digraph::Arc Arc;
1392      typedef typename Digraph::Node Node;
1393
1394      BipartiteVisitor(const Digraph& graph, bool& bipartite)
1395        : _graph(graph), _part(graph), _bipartite(bipartite) {}
1396
1397      void start(const Node& node) {
1398        _part[node] = true;
1399      }
1400      void discover(const Arc& edge) {
1401        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1402      }
1403      void examine(const Arc& edge) {
1404        _bipartite = _bipartite &&
1405          _part[_graph.target(edge)] != _part[_graph.source(edge)];
1406      }
1407
1408    private:
1409
1410      const Digraph& _graph;
1411      typename Digraph::template NodeMap<bool> _part;
1412      bool& _bipartite;
1413    };
1414
1415    template <typename Digraph, typename PartMap>
1416    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
1417    public:
1418      typedef typename Digraph::Arc Arc;
1419      typedef typename Digraph::Node Node;
1420
1421      BipartitePartitionsVisitor(const Digraph& graph,
1422                                 PartMap& part, bool& bipartite)
1423        : _graph(graph), _part(part), _bipartite(bipartite) {}
1424
1425      void start(const Node& node) {
1426        _part.set(node, true);
1427      }
1428      void discover(const Arc& edge) {
1429        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1430      }
1431      void examine(const Arc& edge) {
1432        _bipartite = _bipartite &&
1433          _part[_graph.target(edge)] != _part[_graph.source(edge)];
1434      }
1435
1436    private:
1437
1438      const Digraph& _graph;
1439      PartMap& _part;
1440      bool& _bipartite;
1441    };
1442  }
1443
1444  /// \ingroup connectivity
1445  ///
1446  /// \brief Check if the given undirected graph is bipartite or not
1447  ///
1448  /// The function checks if the given undirected \c graph graph is bipartite
1449  /// or not. The \ref Bfs algorithm is used to calculate the result.
1450  /// \param graph The undirected graph.
1451  /// \return %True if \c graph is bipartite, %false otherwise.
1452  /// \sa bipartitePartitions
1453  template<typename Graph>
1454  inline bool bipartite(const Graph &graph){
1455    using namespace _connectivity_bits;
1456
1457    checkConcept<concepts::Graph, Graph>();
1458
1459    typedef typename Graph::NodeIt NodeIt;
1460    typedef typename Graph::ArcIt ArcIt;
1461
1462    bool bipartite = true;
1463
1464    BipartiteVisitor<Graph>
1465      visitor(graph, bipartite);
1466    BfsVisit<Graph, BipartiteVisitor<Graph> >
1467      bfs(graph, visitor);
1468    bfs.init();
1469    for(NodeIt it(graph); it != INVALID; ++it) {
1470      if(!bfs.reached(it)){
1471        bfs.addSource(it);
1472        while (!bfs.emptyQueue()) {
1473          bfs.processNextNode();
1474          if (!bipartite) return false;
1475        }
1476      }
1477    }
1478    return true;
1479  }
1480
1481  /// \ingroup connectivity
1482  ///
1483  /// \brief Check if the given undirected graph is bipartite or not
1484  ///
1485  /// The function checks if the given undirected graph is bipartite
1486  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
1487  /// During the execution, the \c partMap will be set as the two
1488  /// partitions of the graph.
1489  /// \param graph The undirected graph.
1490  /// \retval partMap A writable bool map of nodes. It will be set as the
1491  /// two partitions of the graph.
1492  /// \return %True if \c graph is bipartite, %false otherwise.
1493  template<typename Graph, typename NodeMap>
1494  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1495    using namespace _connectivity_bits;
1496
1497    checkConcept<concepts::Graph, Graph>();
1498
1499    typedef typename Graph::Node Node;
1500    typedef typename Graph::NodeIt NodeIt;
1501    typedef typename Graph::ArcIt ArcIt;
1502
1503    bool bipartite = true;
1504
1505    BipartitePartitionsVisitor<Graph, NodeMap>
1506      visitor(graph, partMap, bipartite);
1507    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
1508      bfs(graph, visitor);
1509    bfs.init();
1510    for(NodeIt it(graph); it != INVALID; ++it) {
1511      if(!bfs.reached(it)){
1512        bfs.addSource(it);
1513        while (!bfs.emptyQueue()) {
1514          bfs.processNextNode();
1515          if (!bipartite) return false;
1516        }
1517      }
1518    }
1519    return true;
1520  }
1521
1522  /// \brief Returns true when there are not loop edges in the graph.
1523  ///
1524  /// Returns true when there are not loop edges in the graph.
1525  template <typename Digraph>
1526  bool loopFree(const Digraph& digraph) {
1527    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
1528      if (digraph.source(it) == digraph.target(it)) return false;
1529    }
1530    return true;
1531  }
1532
1533  /// \brief Returns true when there are not parallel edges in the graph.
1534  ///
1535  /// Returns true when there are not parallel edges in the graph.
1536  template <typename Digraph>
1537  bool parallelFree(const Digraph& digraph) {
1538    typename Digraph::template NodeMap<bool> reached(digraph, false);
1539    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1540      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1541        if (reached[digraph.target(a)]) return false;
1542        reached.set(digraph.target(a), true);
1543      }
1544      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1545        reached.set(digraph.target(a), false);
1546      }
1547    }
1548    return true;
1549  }
1550
1551  /// \brief Returns true when there are not loop edges and parallel
1552  /// edges in the graph.
1553  ///
1554  /// Returns true when there are not loop edges and parallel edges in
1555  /// the graph.
1556  template <typename Digraph>
1557  bool simpleDigraph(const Digraph& digraph) {
1558    typename Digraph::template NodeMap<bool> reached(digraph, false);
1559    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1560      reached.set(n, true);
1561      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1562        if (reached[digraph.target(a)]) return false;
1563        reached.set(digraph.target(a), true);
1564      }
1565      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1566        reached.set(digraph.target(a), false);
1567      }
1568      reached.set(n, false);
1569    }
1570    return true;
1571  }
1572
1573} //namespace lemon
1574
1575#endif //LEMON_CONNECTIVITY_H
Note: See TracBrowser for help on using the repository browser.