COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1762:3915867b6975

Last change on this file since 1762:3915867b6975 was 1750:5c76ebbb4818, checked in by Balazs Dezso, 14 years ago

Connected components, etc...
Based on the dfs visitor interface

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