COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1739:b1385f5da81b

Last change on this file since 1739:b1385f5da81b was 1739:b1385f5da81b, checked in by Alpar Juttner, 14 years ago

Computing the number of the connected components and the components themselves.

File size: 7.1 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/graph_utils.h>
22
23#include <lemon/concept/graph.h>
24#include <lemon/concept/undir_graph.h>
25#include <lemon/concept_check.h>
26
27/// \ingroup flowalgs
28/// \file
29/// \brief Topology related algorithms
30///
31/// Topology related algorithms
32///\todo Place the file contents is the module tree.
33
34namespace lemon {
35
36  namespace _topology_bits {
37   
38    template <typename NodeMap>
39    class BackCounterMap {
40    public:
41      BackCounterMap(NodeMap& _nodeMap, int _counter)
42        : nodeMap(_nodeMap), counter(_counter) {}
43
44      void set(typename NodeMap::Key key, bool val) {
45        if (val) {
46          nodeMap.set(key, --counter);
47        } else {
48          nodeMap.set(key, -1);
49        }
50      }
51
52      bool operator[](typename NodeMap::Key key) const {
53        return nodeMap[key] != -1;
54      }
55
56    private:
57      NodeMap& nodeMap;
58      int counter;
59    };
60  }
61
62  // \todo Its to special output // ReadWriteMap
63  template <typename Graph, typename NodeMap>
64  bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
65    using namespace _topology_bits;
66
67    checkConcept<concept::StaticGraph, Graph>();
68    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
69
70    typedef typename Graph::Node Node;
71    typedef typename Graph::NodeIt NodeIt;
72    typedef typename Graph::Edge Edge;
73
74    typedef BackCounterMap<NodeMap> ProcessedMap;
75
76    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
77      Create dfs(graph);
78
79    ProcessedMap processed(nodeMap, countNodes(graph));
80
81    dfs.processedMap(processed);
82    dfs.init();
83    for (NodeIt it(graph); it != INVALID; ++it) {
84      if (!dfs.reached(it)) {
85        dfs.addSource(it);
86        while (!dfs.emptyQueue()) {
87          Edge edge = dfs.nextEdge();
88          Node target = graph.target(edge);
89          if (dfs.reached(target) && !processed[target]) {
90            return false;
91          }
92          dfs.processNextEdge();
93        }
94      }
95    }   
96    return true;
97  }
98
99  /// \brief Check that the given graph is a DAG.
100  ///
101  /// Check that the given graph is a DAG. The DAG is
102  /// an Directed Acyclic Graph.
103  template <typename Graph>
104  bool dag(const Graph& graph) {
105
106    checkConcept<concept::StaticGraph, Graph>();
107
108    typedef typename Graph::Node Node;
109    typedef typename Graph::NodeIt NodeIt;
110    typedef typename Graph::Edge Edge;
111
112    typedef typename Graph::template NodeMap<bool> ProcessedMap;
113
114    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
115      Create dfs(graph);
116
117    ProcessedMap processed(graph);
118    dfs.processedMap(processed);
119
120    dfs.init();
121    for (NodeIt it(graph); it != INVALID; ++it) {
122      if (!dfs.reached(it)) {
123        dfs.addSource(it);
124        while (!dfs.emptyQueue()) {
125          Edge edge = dfs.nextEdge();
126          Node target = graph.target(edge);
127          if (dfs.reached(target) && !processed[target]) {
128            return false;
129          }
130          dfs.processNextEdge();
131        }
132      }
133    }   
134    return true;
135  }
136
137  // UndirGraph algorithms
138
139  /// \brief Check that the given undirected graph is connected.
140  ///
141  /// Check that the given undirected graph connected.
142  template <typename UndirGraph>
143  bool connected(const UndirGraph& graph) {
144    checkConcept<concept::UndirGraph, UndirGraph>();
145    typedef typename UndirGraph::NodeIt NodeIt;
146    if (NodeIt(graph) == INVALID) return false;
147    Dfs<UndirGraph> dfs(graph);
148    dfs.run(NodeIt(graph));
149    for (NodeIt it(graph); it != INVALID; ++it) {
150      if (!dfs.reached(it)) {
151        return false;
152      }
153    }
154    return true;
155  }
156
157  /// \brief Check that the given undirected graph is acyclic.
158  ///
159  /// Check that the given undirected graph acyclic.
160  template <typename UndirGraph>
161  bool acyclic(const UndirGraph& graph) {
162    checkConcept<concept::UndirGraph, UndirGraph>();
163    typedef typename UndirGraph::Node Node;
164    typedef typename UndirGraph::NodeIt NodeIt;
165    typedef typename UndirGraph::Edge Edge;
166    Dfs<UndirGraph> dfs(graph);
167    dfs.init();
168    for (NodeIt it(graph); it != INVALID; ++it) {
169      if (!dfs.reached(it)) {
170        dfs.addSource(it);
171        while (!dfs.emptyQueue()) {
172          Edge edge = dfs.nextEdge();
173          Node source = graph.source(edge);
174          Node target = graph.target(edge);
175          if (dfs.reached(target) &&
176              dfs.pred(source) != graph.oppositeEdge(edge)) {
177            return false;
178          }
179          dfs.processNextEdge();
180        }
181      }
182    }
183    return true;
184  }
185
186  /// \brief Check that the given undirected graph is tree.
187  ///
188  /// Check that the given undirected graph is tree.
189  template <typename UndirGraph>
190  bool tree(const UndirGraph& graph) {
191    checkConcept<concept::UndirGraph, UndirGraph>();
192    typedef typename UndirGraph::Node Node;
193    typedef typename UndirGraph::NodeIt NodeIt;
194    typedef typename UndirGraph::Edge Edge;
195    if (NodeIt(graph) == INVALID) return false;
196    Dfs<UndirGraph> dfs(graph);
197    dfs.init();
198    dfs.addSource(NodeIt(graph));
199    while (!dfs.emptyQueue()) {
200      Edge edge = dfs.nextEdge();
201      Node source = graph.source(edge);
202      Node target = graph.target(edge);
203      if (dfs.reached(target) &&
204          dfs.pred(source) != graph.oppositeEdge(edge)) {
205        return false;
206      }
207      dfs.processNextEdge();
208    }
209    for (NodeIt it(graph); it != INVALID; ++it) {
210      if (!dfs.reached(it)) {
211        return false;
212      }
213    }   
214    return true;
215  }
216 
217  ///Count the number of connected components of an undirected graph
218
219  ///Count the number of connected components of an undirected graph
220  ///
221  ///\param g The graph. In must be undirected.
222  ///\return The number of components
223  ///\todo Test required
224  template<class UGraph>
225  int numberOfComponents(const UGraph &g)
226  {
227    int c=0;
228    Bfs<Graph> bfs(g);
229    bfs.init();
230    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
231      if(!bfs.reached(n)) {
232        c++;
233        bfs.addSource(n);
234        bfs.start();
235      }
236    return c;
237  }
238
239
240  ///Find the connected components of an undirected graph
241
242  ///Find the connected components of an undirected graph
243  ///
244  ///\param g The graph. In must be undirected.
245  ///\retval comp A writable node map. The values will be set from 0 to
246  ///the number of the connected components minus one. Each values of the map
247  ///will be set exactly once, the values of a certain component will be
248  ///set continuously.
249  ///\return The number of components
250  ///\todo Test required
251  template<class UGraph, class WMap>
252  int connectedComponents(const UGraph &g, WMap &comp)
253  {
254    int c=0;
255    Bfs<Graph> bfs(g);
256    bfs.init();
257    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
258      if(!bfs.reached(n)) {
259        bfs.addSource(n);
260        while ( bfs.nextNode()!=INVALID ) {
261          comp[bfs.nextNode()]=c;
262          processNextNode();
263          c++;
264      }
265    return c;
266  }
267
268} //namespace lemon
269
270#endif //LEMON_TOPOLOGY_H
Note: See TracBrowser for help on using the repository browser.