COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/topology.h @ 1698:755cdc461ddd

Last change on this file since 1698:755cdc461ddd was 1698:755cdc461ddd, checked in by Balazs Dezso, 18 years ago

Small functions for discovering graph topology

File size: 5.7 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
33namespace lemon {
34
35  namespace _topology_bits {
36   
37    template <typename NodeMap>
38    class BackCounterMap {
39    public:
40      BackCounterMap(NodeMap& _nodeMap, int _counter)
41        : nodeMap(_nodeMap), counter(_counter) {}
42
43      void set(typename NodeMap::Key key, bool val) {
44        if (val) {
45          nodeMap.set(key, --counter);
46        } else {
47          nodeMap.set(key, -1);
48        }
49      }
50
51      bool operator[](typename NodeMap::Key key) const {
52        return nodeMap[key] != -1;
53      }
54
55    private:
56      NodeMap& nodeMap;
57      int counter;
58    };
59  }
60
61  // \todo Its to special output // ReadWriteMap
62  template <typename Graph, typename NodeMap>
63  bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
64    using namespace _topology_bits;
65
66    checkConcept<concept::StaticGraph, Graph>();
67    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
68
69    typedef typename Graph::Node Node;
70    typedef typename Graph::NodeIt NodeIt;
71    typedef typename Graph::Edge Edge;
72
73    typedef BackCounterMap<NodeMap> ProcessedMap;
74
75    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
76      Dfs dfs(graph);
77
78    ProcessedMap processed(nodeMap, countNodes(graph));
79
80    dfs.processedMap(processed);
81    dfs.init();
82    for (NodeIt it(graph); it != INVALID; ++it) {
83      if (!dfs.reached(it)) {
84        dfs.addSource(it);
85        while (!dfs.emptyQueue()) {
86          Edge edge = dfs.nextEdge();
87          Node target = graph.target(edge);
88          if (dfs.reached(target) && !processed[target]) {
89            return false;
90          }
91          dfs.processNextEdge();
92        }
93      }
94    }   
95    return true;
96  }
97
98  /// \brief Check that the given graph is a DAG.
99  ///
100  /// Check that the given graph is a DAG. The DAG is
101  /// an Directed Acyclic Graph.
102  template <typename Graph>
103  bool dag(const Graph& graph) {
104
105    checkConcept<concept::StaticGraph, Graph>();
106
107    typedef typename Graph::Node Node;
108    typedef typename Graph::NodeIt NodeIt;
109    typedef typename Graph::Edge Edge;
110
111    typedef typename Graph::template NodeMap<bool> ProcessedMap;
112
113    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
114      Dfs dfs(graph);
115
116    ProcessedMap processed(graph);
117    dfs.processedMap(processed);
118
119    dfs.init();
120    for (NodeIt it(graph); it != INVALID; ++it) {
121      if (!dfs.reached(it)) {
122        dfs.addSource(it);
123        while (!dfs.emptyQueue()) {
124          Edge edge = dfs.nextEdge();
125          Node target = graph.target(edge);
126          if (dfs.reached(target) && !processed[target]) {
127            return false;
128          }
129          dfs.processNextEdge();
130        }
131      }
132    }   
133    return true;
134  }
135
136  // UndirGraph algorithms
137
138  /// \brief Check that the given undirected graph is connected.
139  ///
140  /// Check that the given undirected graph connected.
141  template <typename UndirGraph>
142  bool connected(const UndirGraph& graph) {
143    checkConcept<concept::UndirGraph, UndirGraph>();
144    typedef typename UndirGraph::NodeIt NodeIt;
145    if (NodeIt(graph) == INVALID) return false;
146    Dfs<UndirGraph> dfs(graph);
147    dfs.run(NodeIt(graph));
148    for (NodeIt it(graph); it != INVALID; ++it) {
149      if (!dfs.reached(it)) {
150        return false;
151      }
152    }
153    return true;
154  }
155
156  /// \brief Check that the given undirected graph is acyclic.
157  ///
158  /// Check that the given undirected graph acyclic.
159  template <typename UndirGraph>
160  bool acyclic(const UndirGraph& graph) {
161    checkConcept<concept::UndirGraph, UndirGraph>();
162    typedef typename UndirGraph::Node Node;
163    typedef typename UndirGraph::NodeIt NodeIt;
164    typedef typename UndirGraph::Edge Edge;
165    Dfs<UndirGraph> dfs(graph);
166    dfs.init();
167    for (NodeIt it(graph); it != INVALID; ++it) {
168      if (!dfs.reached(it)) {
169        dfs.addSource(it);
170        while (!dfs.emptyQueue()) {
171          Edge edge = dfs.nextEdge();
172          Node source = graph.source(edge);
173          Node target = graph.target(edge);
174          if (dfs.reached(target) &&
175              dfs.pred(source) != graph.oppositeEdge(edge)) {
176            return false;
177          }
178          dfs.processNextEdge();
179        }
180      }
181    }
182    return true;
183  }
184
185  /// \brief Check that the given undirected graph is tree.
186  ///
187  /// Check that the given undirected graph is tree.
188  template <typename UndirGraph>
189  bool tree(const UndirGraph& graph) {
190    checkConcept<concept::UndirGraph, UndirGraph>();
191    typedef typename UndirGraph::Node Node;
192    typedef typename UndirGraph::NodeIt NodeIt;
193    typedef typename UndirGraph::Edge Edge;
194    if (NodeIt(graph) == INVALID) return false;
195    Dfs<UndirGraph> dfs(graph);
196    dfs.init();
197    dfs.addSource(NodeIt(graph));
198    while (!dfs.emptyQueue()) {
199      Edge edge = dfs.nextEdge();
200      Node source = graph.source(edge);
201      Node target = graph.target(edge);
202      if (dfs.reached(target) &&
203          dfs.pred(source) != graph.oppositeEdge(edge)) {
204        return false;
205      }
206      dfs.processNextEdge();
207    }
208    for (NodeIt it(graph); it != INVALID; ++it) {
209      if (!dfs.reached(it)) {
210        return false;
211      }
212    }   
213    return true;
214  }
215 
216
217} //namespace lemon
218
219#endif //LEMON_TOPOLOGY_H
Note: See TracBrowser for help on using the repository browser.