|
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 |
|
33 namespace 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 |