18 #define LEMON_TOPOLOGY_H |
18 #define LEMON_TOPOLOGY_H |
19 |
19 |
20 #include <lemon/dfs.h> |
20 #include <lemon/dfs.h> |
21 #include <lemon/bfs.h> |
21 #include <lemon/bfs.h> |
22 #include <lemon/graph_utils.h> |
22 #include <lemon/graph_utils.h> |
|
23 #include <lemon/graph_adaptor.h> |
|
24 #include <lemon/maps.h> |
23 |
25 |
24 #include <lemon/concept/graph.h> |
26 #include <lemon/concept/graph.h> |
25 #include <lemon/concept/undir_graph.h> |
27 #include <lemon/concept/undir_graph.h> |
26 #include <lemon/concept_check.h> |
28 #include <lemon/concept_check.h> |
27 |
29 |
28 /// \ingroup flowalgs |
30 #include <lemon/bin_heap.h> |
|
31 #include <lemon/linear_heap.h> |
|
32 |
|
33 #include <stack> |
|
34 #include <functional> |
|
35 |
|
36 /// \ingroup topology |
29 /// \file |
37 /// \file |
30 /// \brief Topology related algorithms |
38 /// \brief Topology related algorithms |
31 /// |
39 /// |
32 /// Topology related algorithms |
40 /// Topology related algorithms |
33 ///\todo Place the file contents is the module tree. |
|
34 |
41 |
35 namespace lemon { |
42 namespace lemon { |
36 |
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 |
37 namespace _topology_bits { |
155 namespace _topology_bits { |
38 |
156 |
39 template <typename NodeMap> |
157 template <typename Graph, typename Iterator > |
40 class BackCounterMap { |
158 struct LeaveOrderVisitor : public DfsVisitor<Graph> { |
41 public: |
159 public: |
42 BackCounterMap(NodeMap& _nodeMap, int _counter) |
160 typedef typename Graph::Node Node; |
43 : nodeMap(_nodeMap), counter(_counter) {} |
161 LeaveOrderVisitor(Iterator it) : _it(it) {} |
44 |
162 |
45 void set(typename NodeMap::Key key, bool val) { |
163 void leave(const Node& node) { |
46 if (val) { |
164 *(_it++) = node; |
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 } |
165 } |
56 |
166 |
57 private: |
167 private: |
58 NodeMap& nodeMap; |
168 Iterator _it; |
59 int counter; |
|
60 }; |
169 }; |
61 } |
170 |
62 |
171 template <typename Graph, typename Map> |
63 // \todo Its to special output // ReadWriteMap |
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 |
64 template <typename Graph, typename NodeMap> |
357 template <typename Graph, typename NodeMap> |
65 bool topological_sort(const Graph& graph, NodeMap& 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 |
66 using namespace _topology_bits; |
364 using namespace _topology_bits; |
67 |
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) { |
68 checkConcept<concept::StaticGraph, Graph>(); |
422 checkConcept<concept::StaticGraph, Graph>(); |
69 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>(); |
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>(); |
70 |
1187 |
71 typedef typename Graph::Node Node; |
1188 typedef typename Graph::Node Node; |
72 typedef typename Graph::NodeIt NodeIt; |
1189 typedef typename Graph::NodeIt NodeIt; |
73 typedef typename Graph::Edge Edge; |
1190 typedef typename Graph::Edge Edge; |
74 |
1191 |
75 typedef BackCounterMap<NodeMap> ProcessedMap; |
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; |
76 |
1277 |
77 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>:: |
1278 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>:: |
78 Create dfs(graph); |
1279 Create dfs(graph); |
79 |
1280 |
80 ProcessedMap processed(nodeMap, countNodes(graph)); |
1281 ProcessedMap processed(graph); |
81 |
|
82 dfs.processedMap(processed); |
1282 dfs.processedMap(processed); |
|
1283 |
83 dfs.init(); |
1284 dfs.init(); |
84 for (NodeIt it(graph); it != INVALID; ++it) { |
1285 for (NodeIt it(graph); it != INVALID; ++it) { |
85 if (!dfs.reached(it)) { |
1286 if (!dfs.reached(it)) { |
86 dfs.addSource(it); |
1287 dfs.addSource(it); |
87 while (!dfs.emptyQueue()) { |
1288 while (!dfs.emptyQueue()) { |