COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1740:4cade8579363

Last change on this file since 1740:4cade8579363 was 1740:4cade8579363, checked in by Balazs Dezso, 18 years ago

Bug fix in connectedComponents
Strongly connected components

File size: 11.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/bfs.h>
22#include <lemon/graph_utils.h>
23
24#include <lemon/concept/graph.h>
25#include <lemon/concept/undir_graph.h>
26#include <lemon/concept_check.h>
27
28/// \ingroup flowalgs
29/// \file
30/// \brief Topology related algorithms
31///
32/// Topology related algorithms
33///\todo Place the file contents is the module tree.
34
35namespace lemon {
36
37  namespace _topology_bits {
38   
39    template <typename NodeMap>
40    class BackCounterMap {
41    public:
42      BackCounterMap(NodeMap& _nodeMap, int _counter)
43        : nodeMap(_nodeMap), counter(_counter) {}
44
45      void set(typename NodeMap::Key key, bool val) {
46        if (val) {
47          nodeMap.set(key, --counter);
48        } else {
49          nodeMap.set(key, -1);
50        }
51      }
52
53      bool operator[](typename NodeMap::Key key) const {
54        return nodeMap[key] != -1;
55      }
56
57    private:
58      NodeMap& nodeMap;
59      int counter;
60    };
61  }
62
63  // \todo Its to special output // ReadWriteMap
64  template <typename Graph, typename NodeMap>
65  bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
66    using namespace _topology_bits;
67
68    checkConcept<concept::StaticGraph, Graph>();
69    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
70
71    typedef typename Graph::Node Node;
72    typedef typename Graph::NodeIt NodeIt;
73    typedef typename Graph::Edge Edge;
74
75    typedef BackCounterMap<NodeMap> ProcessedMap;
76
77    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
78      Create dfs(graph);
79
80    ProcessedMap processed(nodeMap, countNodes(graph));
81
82    dfs.processedMap(processed);
83    dfs.init();
84    for (NodeIt it(graph); it != INVALID; ++it) {
85      if (!dfs.reached(it)) {
86        dfs.addSource(it);
87        while (!dfs.emptyQueue()) {
88          Edge edge = dfs.nextEdge();
89          Node target = graph.target(edge);
90          if (dfs.reached(target) && !processed[target]) {
91            return false;
92          }
93          dfs.processNextEdge();
94        }
95      }
96    }   
97    return true;
98  }
99
100  /// \brief Check that the given graph is a DAG.
101  ///
102  /// Check that the given graph is a DAG. The DAG is
103  /// an Directed Acyclic Graph.
104  template <typename Graph>
105  bool dag(const Graph& graph) {
106
107    checkConcept<concept::StaticGraph, Graph>();
108
109    typedef typename Graph::Node Node;
110    typedef typename Graph::NodeIt NodeIt;
111    typedef typename Graph::Edge Edge;
112
113    typedef typename Graph::template NodeMap<bool> ProcessedMap;
114
115    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
116      Create dfs(graph);
117
118    ProcessedMap processed(graph);
119    dfs.processedMap(processed);
120
121    dfs.init();
122    for (NodeIt it(graph); it != INVALID; ++it) {
123      if (!dfs.reached(it)) {
124        dfs.addSource(it);
125        while (!dfs.emptyQueue()) {
126          Edge edge = dfs.nextEdge();
127          Node target = graph.target(edge);
128          if (dfs.reached(target) && !processed[target]) {
129            return false;
130          }
131          dfs.processNextEdge();
132        }
133      }
134    }   
135    return true;
136  }
137
138  // UndirGraph algorithms
139
140  /// \brief Check that the given undirected graph is connected.
141  ///
142  /// Check that the given undirected graph connected.
143  template <typename UndirGraph>
144  bool connected(const UndirGraph& graph) {
145    checkConcept<concept::UndirGraph, UndirGraph>();
146    typedef typename UndirGraph::NodeIt NodeIt;
147    if (NodeIt(graph) == INVALID) return false;
148    Dfs<UndirGraph> dfs(graph);
149    dfs.run(NodeIt(graph));
150    for (NodeIt it(graph); it != INVALID; ++it) {
151      if (!dfs.reached(it)) {
152        return false;
153      }
154    }
155    return true;
156  }
157
158  /// \brief Check that the given undirected graph is acyclic.
159  ///
160  /// Check that the given undirected graph acyclic.
161  template <typename UndirGraph>
162  bool acyclic(const UndirGraph& graph) {
163    checkConcept<concept::UndirGraph, UndirGraph>();
164    typedef typename UndirGraph::Node Node;
165    typedef typename UndirGraph::NodeIt NodeIt;
166    typedef typename UndirGraph::Edge Edge;
167    Dfs<UndirGraph> dfs(graph);
168    dfs.init();
169    for (NodeIt it(graph); it != INVALID; ++it) {
170      if (!dfs.reached(it)) {
171        dfs.addSource(it);
172        while (!dfs.emptyQueue()) {
173          Edge edge = dfs.nextEdge();
174          Node source = graph.source(edge);
175          Node target = graph.target(edge);
176          if (dfs.reached(target) &&
177              dfs.pred(source) != graph.oppositeEdge(edge)) {
178            return false;
179          }
180          dfs.processNextEdge();
181        }
182      }
183    }
184    return true;
185  }
186
187  /// \brief Check that the given undirected graph is tree.
188  ///
189  /// Check that the given undirected graph is tree.
190  template <typename UndirGraph>
191  bool tree(const UndirGraph& graph) {
192    checkConcept<concept::UndirGraph, UndirGraph>();
193    typedef typename UndirGraph::Node Node;
194    typedef typename UndirGraph::NodeIt NodeIt;
195    typedef typename UndirGraph::Edge Edge;
196    if (NodeIt(graph) == INVALID) return false;
197    Dfs<UndirGraph> dfs(graph);
198    dfs.init();
199    dfs.addSource(NodeIt(graph));
200    while (!dfs.emptyQueue()) {
201      Edge edge = dfs.nextEdge();
202      Node source = graph.source(edge);
203      Node target = graph.target(edge);
204      if (dfs.reached(target) &&
205          dfs.pred(source) != graph.oppositeEdge(edge)) {
206        return false;
207      }
208      dfs.processNextEdge();
209    }
210    for (NodeIt it(graph); it != INVALID; ++it) {
211      if (!dfs.reached(it)) {
212        return false;
213      }
214    }   
215    return true;
216  }
217 
218  ///Count the number of connected components of an undirected graph
219
220  ///Count the number of connected components of an undirected graph
221  ///
222  ///\param g The graph. In must be undirected.
223  ///\return The number of components
224  template <class UndirGraph>
225  int countConnectedComponents(const UndirGraph &g) {
226    checkConcept<concept::UndirGraph, UndirGraph>();
227    int c = 0;
228    Bfs<UndirGraph> bfs(g);
229    bfs.init();
230    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
231      if(!bfs.reached(n)) {
232        bfs.addSource(n);
233        bfs.start();
234        ++c;
235      }
236    }
237    return c;
238  }
239
240
241  ///Find the connected components of an undirected graph
242
243  ///Find the connected components of an undirected graph
244  ///
245  ///\param g The graph. In must be undirected.
246  ///\retval comp A writable node map. The values will be set from 0 to
247  ///the number of the connected components minus one. Each values of the map
248  ///will be set exactly once, the values of a certain component will be
249  ///set continuously.
250  ///\return The number of components
251  ///\todo Test required
252  template <class UndirGraph, class IntNodeMap>
253  int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
254    checkConcept<concept::UndirGraph, UndirGraph>();
255    checkConcept<concept::WriteMap<typename UndirGraph::Node, int>,
256      IntNodeMap>();
257    int c = 0;
258    Bfs<UndirGraph> bfs(g);
259    bfs.init();
260    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
261      if(!bfs.reached(n)) {
262        bfs.addSource(n);
263        while (!bfs.emptyQueue()) {
264          comp[bfs.nextNode()] = c;
265          bfs.processNextNode();
266        }
267        ++c;
268      }
269    }
270    return c;
271  }
272
273  namespace _components_bits {
274
275    template <typename Key, typename IntMap>
276    struct FillWriteMap : public MapBase<Key, bool> {
277    public:
278      FillWriteMap(IntMap& _map, int& _comp)
279        : map(_map), comp(_comp) {}
280      void set(Key key, bool value) {
281        if (value) { map.set(key, comp); }
282      }
283    private:
284      IntMap& map;
285      int& comp;
286    };
287
288    template <typename Key, typename Container = std::vector<Key> >
289    struct BackInserterWriteMap : public MapBase<Key, bool> {
290    public:
291      BackInserterWriteMap(Container& _container)
292        : container(_container) {}
293      void set(Key key, bool value) {
294        if (value) { container.push_back(key); }
295      }
296    private:
297      Container& container;
298    };
299
300  }
301
302  /// \brief Count the strongly connected components of a directed graph
303  ///
304  /// Count the strongly connected components of a directed graph
305  ///
306  /// \param g The graph.
307  /// \return The number of components
308  template <typename Graph>
309  int countStronglyConnectedComponents(const Graph& graph) {
310    checkConcept<concept::StaticGraph, Graph>();
311
312    using namespace _components_bits;
313
314    typedef typename Graph::Node Node;
315    typedef typename Graph::Edge Edge;
316    typedef typename Graph::NodeIt NodeIt;
317    typedef typename Graph::EdgeIt EdgeIt;
318   
319
320    typename Dfs<Graph>::
321      template DefProcessedMap<BackInserterWriteMap<Node> >::
322      Create dfs(graph);
323
324    std::vector<Node> nodes;
325    BackInserterWriteMap<Node> processed(nodes);
326    dfs.processedMap(processed);
327
328    dfs.init();
329    for (NodeIt it(graph); it != INVALID; ++it) {
330      if (!dfs.reached(it)) {
331        dfs.addSource(it);
332        dfs.start();
333      }
334    }
335
336    typedef RevGraphAdaptor<const Graph> RGraph;
337
338    RGraph rgraph(graph);
339
340    Dfs<RGraph> rdfs(rgraph);
341
342    int num = 0;
343
344    rdfs.init();
345    for (typename std::vector<Node>::reverse_iterator
346           it = nodes.rbegin(); it != nodes.rend(); ++it) {
347      if (!rdfs.reached(*it)) {
348        rdfs.addSource(*it);
349        rdfs.start();
350        ++num;
351      }
352    }
353    return num;
354  }
355
356  /// \brief Find the strongly connected components of a directed graph
357  ///
358  /// Find the strongly connected components of a directed graph
359  ///
360  /// \param g The graph.
361  /// \retval comp A writable node map. The values will be set from 0 to
362  /// the number of the strongly connected components minus one. Each values
363  /// of the map will be set exactly once, the values of a certain component
364  /// will be set continuously.
365  /// \return The number of components
366  template <typename Graph, typename IntNodeMap>
367  int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
368    checkConcept<concept::StaticGraph, Graph>();
369    checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
370
371    using namespace _components_bits;
372
373    typedef typename Graph::Node Node;
374    typedef typename Graph::Edge Edge;
375    typedef typename Graph::NodeIt NodeIt;
376    typedef typename Graph::EdgeIt EdgeIt;
377   
378
379    typename Dfs<Graph>::
380      template DefProcessedMap<BackInserterWriteMap<Node> >::
381      Create dfs(graph);
382
383    std::vector<Node> nodes;
384    BackInserterWriteMap<Node> processed(nodes);
385    dfs.processedMap(processed);
386
387    dfs.init();
388    for (NodeIt it(graph); it != INVALID; ++it) {
389      if (!dfs.reached(it)) {
390        dfs.addSource(it);
391        dfs.start();
392      }
393    }
394
395    typedef RevGraphAdaptor<const Graph> RGraph;
396
397    RGraph rgraph(graph);
398
399    typename Dfs<RGraph>::
400      template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
401      Create rdfs(rgraph);
402
403    int num = 0;
404    FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
405    rdfs.processedMap(rprocessed);
406
407    rdfs.init();
408    for (typename std::vector<Node>::reverse_iterator
409           it = nodes.rbegin(); it != nodes.rend(); ++it) {
410      if (!rdfs.reached(*it)) {
411        rdfs.addSource(*it);
412        rdfs.start();
413        ++num;
414      }
415    }
416    return num;
417  }
418
419} //namespace lemon
420
421#endif //LEMON_TOPOLOGY_H
Note: See TracBrowser for help on using the repository browser.