1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_GRAPH_ADAPTOR_H |
|
20 #define LEMON_GRAPH_ADAPTOR_H |
|
21 |
|
22 ///\ingroup graph_adaptors |
|
23 ///\file |
|
24 ///\brief Several graph adaptors. |
|
25 /// |
|
26 ///This file contains several useful undirected graph adaptor classes. |
|
27 |
|
28 #include <lemon/core.h> |
|
29 #include <lemon/maps.h> |
|
30 #include <lemon/bits/graph_adaptor_extender.h> |
|
31 |
|
32 namespace lemon { |
|
33 |
|
34 template<typename _Graph> |
|
35 class GraphAdaptorBase { |
|
36 public: |
|
37 typedef _Graph Graph; |
|
38 typedef Graph ParentGraph; |
|
39 |
|
40 protected: |
|
41 Graph* _graph; |
|
42 |
|
43 GraphAdaptorBase() : _graph(0) {} |
|
44 |
|
45 void setGraph(Graph& graph) { _graph = &graph; } |
|
46 |
|
47 public: |
|
48 GraphAdaptorBase(Graph& graph) : _graph(&graph) {} |
|
49 |
|
50 typedef typename Graph::Node Node; |
|
51 typedef typename Graph::Arc Arc; |
|
52 typedef typename Graph::Edge Edge; |
|
53 |
|
54 void first(Node& i) const { _graph->first(i); } |
|
55 void first(Arc& i) const { _graph->first(i); } |
|
56 void first(Edge& i) const { _graph->first(i); } |
|
57 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); } |
|
58 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); } |
|
59 void firstInc(Edge &i, bool &d, const Node &n) const { |
|
60 _graph->firstInc(i, d, n); |
|
61 } |
|
62 |
|
63 void next(Node& i) const { _graph->next(i); } |
|
64 void next(Arc& i) const { _graph->next(i); } |
|
65 void next(Edge& i) const { _graph->next(i); } |
|
66 void nextIn(Arc& i) const { _graph->nextIn(i); } |
|
67 void nextOut(Arc& i) const { _graph->nextOut(i); } |
|
68 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); } |
|
69 |
|
70 Node u(const Edge& e) const { return _graph->u(e); } |
|
71 Node v(const Edge& e) const { return _graph->v(e); } |
|
72 |
|
73 Node source(const Arc& a) const { return _graph->source(a); } |
|
74 Node target(const Arc& a) const { return _graph->target(a); } |
|
75 |
|
76 typedef NodeNumTagIndicator<Graph> NodeNumTag; |
|
77 int nodeNum() const { return _graph->nodeNum(); } |
|
78 |
|
79 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; |
|
80 int arcNum() const { return _graph->arcNum(); } |
|
81 int edgeNum() const { return _graph->edgeNum(); } |
|
82 |
|
83 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
84 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { |
|
85 return _graph->findArc(u, v, prev); |
|
86 } |
|
87 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { |
|
88 return _graph->findEdge(u, v, prev); |
|
89 } |
|
90 |
|
91 Node addNode() { return _graph->addNode(); } |
|
92 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); } |
|
93 |
|
94 void erase(const Node& i) { _graph->erase(i); } |
|
95 void erase(const Edge& i) { _graph->erase(i); } |
|
96 |
|
97 void clear() { _graph->clear(); } |
|
98 |
|
99 bool direction(const Arc& a) const { return _graph->direction(a); } |
|
100 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); } |
|
101 |
|
102 int id(const Node& v) const { return _graph->id(v); } |
|
103 int id(const Arc& a) const { return _graph->id(a); } |
|
104 int id(const Edge& e) const { return _graph->id(e); } |
|
105 |
|
106 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); } |
|
107 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); } |
|
108 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); } |
|
109 |
|
110 int maxNodeId() const { return _graph->maxNodeId(); } |
|
111 int maxArcId() const { return _graph->maxArcId(); } |
|
112 int maxEdgeId() const { return _graph->maxEdgeId(); } |
|
113 |
|
114 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; |
|
115 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } |
|
116 |
|
117 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; |
|
118 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } |
|
119 |
|
120 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; |
|
121 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } |
|
122 |
|
123 template <typename _Value> |
|
124 class NodeMap : public Graph::template NodeMap<_Value> { |
|
125 public: |
|
126 typedef typename Graph::template NodeMap<_Value> Parent; |
|
127 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) |
|
128 : Parent(*adapter._graph) {} |
|
129 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) |
|
130 : Parent(*adapter._graph, value) {} |
|
131 |
|
132 private: |
|
133 NodeMap& operator=(const NodeMap& cmap) { |
|
134 return operator=<NodeMap>(cmap); |
|
135 } |
|
136 |
|
137 template <typename CMap> |
|
138 NodeMap& operator=(const CMap& cmap) { |
|
139 Parent::operator=(cmap); |
|
140 return *this; |
|
141 } |
|
142 |
|
143 }; |
|
144 |
|
145 template <typename _Value> |
|
146 class ArcMap : public Graph::template ArcMap<_Value> { |
|
147 public: |
|
148 typedef typename Graph::template ArcMap<_Value> Parent; |
|
149 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) |
|
150 : Parent(*adapter._graph) {} |
|
151 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) |
|
152 : Parent(*adapter._graph, value) {} |
|
153 |
|
154 private: |
|
155 ArcMap& operator=(const ArcMap& cmap) { |
|
156 return operator=<ArcMap>(cmap); |
|
157 } |
|
158 |
|
159 template <typename CMap> |
|
160 ArcMap& operator=(const CMap& cmap) { |
|
161 Parent::operator=(cmap); |
|
162 return *this; |
|
163 } |
|
164 }; |
|
165 |
|
166 template <typename _Value> |
|
167 class EdgeMap : public Graph::template EdgeMap<_Value> { |
|
168 public: |
|
169 typedef typename Graph::template EdgeMap<_Value> Parent; |
|
170 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) |
|
171 : Parent(*adapter._graph) {} |
|
172 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) |
|
173 : Parent(*adapter._graph, value) {} |
|
174 |
|
175 private: |
|
176 EdgeMap& operator=(const EdgeMap& cmap) { |
|
177 return operator=<EdgeMap>(cmap); |
|
178 } |
|
179 |
|
180 template <typename CMap> |
|
181 EdgeMap& operator=(const CMap& cmap) { |
|
182 Parent::operator=(cmap); |
|
183 return *this; |
|
184 } |
|
185 }; |
|
186 |
|
187 }; |
|
188 |
|
189 template <typename _Graph, typename NodeFilterMap, |
|
190 typename EdgeFilterMap, bool checked = true> |
|
191 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { |
|
192 public: |
|
193 typedef _Graph Graph; |
|
194 typedef SubGraphAdaptorBase Adaptor; |
|
195 typedef GraphAdaptorBase<_Graph> Parent; |
|
196 protected: |
|
197 |
|
198 NodeFilterMap* _node_filter_map; |
|
199 EdgeFilterMap* _edge_filter_map; |
|
200 |
|
201 SubGraphAdaptorBase() |
|
202 : Parent(), _node_filter_map(0), _edge_filter_map(0) { } |
|
203 |
|
204 void setNodeFilterMap(NodeFilterMap& node_filter_map) { |
|
205 _node_filter_map=&node_filter_map; |
|
206 } |
|
207 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { |
|
208 _edge_filter_map=&edge_filter_map; |
|
209 } |
|
210 |
|
211 public: |
|
212 |
|
213 typedef typename Parent::Node Node; |
|
214 typedef typename Parent::Arc Arc; |
|
215 typedef typename Parent::Edge Edge; |
|
216 |
|
217 void first(Node& i) const { |
|
218 Parent::first(i); |
|
219 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); |
|
220 } |
|
221 |
|
222 void first(Arc& i) const { |
|
223 Parent::first(i); |
|
224 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
225 || !(*_node_filter_map)[Parent::source(i)] |
|
226 || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i); |
|
227 } |
|
228 |
|
229 void first(Edge& i) const { |
|
230 Parent::first(i); |
|
231 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
232 || !(*_node_filter_map)[Parent::u(i)] |
|
233 || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i); |
|
234 } |
|
235 |
|
236 void firstIn(Arc& i, const Node& n) const { |
|
237 Parent::firstIn(i, n); |
|
238 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
239 || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i); |
|
240 } |
|
241 |
|
242 void firstOut(Arc& i, const Node& n) const { |
|
243 Parent::firstOut(i, n); |
|
244 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
245 || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i); |
|
246 } |
|
247 |
|
248 void firstInc(Edge& i, bool& d, const Node& n) const { |
|
249 Parent::firstInc(i, d, n); |
|
250 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
251 || !(*_node_filter_map)[Parent::u(i)] |
|
252 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); |
|
253 } |
|
254 |
|
255 void next(Node& i) const { |
|
256 Parent::next(i); |
|
257 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); |
|
258 } |
|
259 |
|
260 void next(Arc& i) const { |
|
261 Parent::next(i); |
|
262 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
263 || !(*_node_filter_map)[Parent::source(i)] |
|
264 || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i); |
|
265 } |
|
266 |
|
267 void next(Edge& i) const { |
|
268 Parent::next(i); |
|
269 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
270 || !(*_node_filter_map)[Parent::u(i)] |
|
271 || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i); |
|
272 } |
|
273 |
|
274 void nextIn(Arc& i) const { |
|
275 Parent::nextIn(i); |
|
276 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
277 || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i); |
|
278 } |
|
279 |
|
280 void nextOut(Arc& i) const { |
|
281 Parent::nextOut(i); |
|
282 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
283 || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i); |
|
284 } |
|
285 |
|
286 void nextInc(Edge& i, bool& d) const { |
|
287 Parent::nextInc(i, d); |
|
288 while (i!=INVALID && (!(*_edge_filter_map)[i] |
|
289 || !(*_node_filter_map)[Parent::u(i)] |
|
290 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); |
|
291 } |
|
292 |
|
293 void hide(const Node& n) const { _node_filter_map->set(n, false); } |
|
294 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } |
|
295 |
|
296 void unHide(const Node& n) const { _node_filter_map->set(n, true); } |
|
297 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } |
|
298 |
|
299 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } |
|
300 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } |
|
301 |
|
302 typedef False NodeNumTag; |
|
303 typedef False EdgeNumTag; |
|
304 |
|
305 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
306 Arc findArc(const Node& u, const Node& v, |
|
307 const Arc& prev = INVALID) { |
|
308 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { |
|
309 return INVALID; |
|
310 } |
|
311 Arc arc = Parent::findArc(u, v, prev); |
|
312 while (arc != INVALID && !(*_edge_filter_map)[arc]) { |
|
313 arc = Parent::findArc(u, v, arc); |
|
314 } |
|
315 return arc; |
|
316 } |
|
317 Edge findEdge(const Node& u, const Node& v, |
|
318 const Edge& prev = INVALID) { |
|
319 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { |
|
320 return INVALID; |
|
321 } |
|
322 Edge edge = Parent::findEdge(u, v, prev); |
|
323 while (edge != INVALID && !(*_edge_filter_map)[edge]) { |
|
324 edge = Parent::findEdge(u, v, edge); |
|
325 } |
|
326 return edge; |
|
327 } |
|
328 |
|
329 template <typename _Value> |
|
330 class NodeMap : public SubMapExtender<Adaptor, |
|
331 typename Parent::template NodeMap<_Value> > { |
|
332 public: |
|
333 typedef _Value Value; |
|
334 typedef SubMapExtender<Adaptor, typename Parent:: |
|
335 template NodeMap<Value> > MapParent; |
|
336 |
|
337 NodeMap(const Adaptor& adaptor) |
|
338 : MapParent(adaptor) {} |
|
339 NodeMap(const Adaptor& adaptor, const Value& value) |
|
340 : MapParent(adaptor, value) {} |
|
341 |
|
342 private: |
|
343 NodeMap& operator=(const NodeMap& cmap) { |
|
344 return operator=<NodeMap>(cmap); |
|
345 } |
|
346 |
|
347 template <typename CMap> |
|
348 NodeMap& operator=(const CMap& cmap) { |
|
349 MapParent::operator=(cmap); |
|
350 return *this; |
|
351 } |
|
352 }; |
|
353 |
|
354 template <typename _Value> |
|
355 class ArcMap : public SubMapExtender<Adaptor, |
|
356 typename Parent::template ArcMap<_Value> > { |
|
357 public: |
|
358 typedef _Value Value; |
|
359 typedef SubMapExtender<Adaptor, typename Parent:: |
|
360 template ArcMap<Value> > MapParent; |
|
361 |
|
362 ArcMap(const Adaptor& adaptor) |
|
363 : MapParent(adaptor) {} |
|
364 ArcMap(const Adaptor& adaptor, const Value& value) |
|
365 : MapParent(adaptor, value) {} |
|
366 |
|
367 private: |
|
368 ArcMap& operator=(const ArcMap& cmap) { |
|
369 return operator=<ArcMap>(cmap); |
|
370 } |
|
371 |
|
372 template <typename CMap> |
|
373 ArcMap& operator=(const CMap& cmap) { |
|
374 MapParent::operator=(cmap); |
|
375 return *this; |
|
376 } |
|
377 }; |
|
378 |
|
379 template <typename _Value> |
|
380 class EdgeMap : public SubMapExtender<Adaptor, |
|
381 typename Parent::template EdgeMap<_Value> > { |
|
382 public: |
|
383 typedef _Value Value; |
|
384 typedef SubMapExtender<Adaptor, typename Parent:: |
|
385 template EdgeMap<Value> > MapParent; |
|
386 |
|
387 EdgeMap(const Adaptor& adaptor) |
|
388 : MapParent(adaptor) {} |
|
389 |
|
390 EdgeMap(const Adaptor& adaptor, const Value& value) |
|
391 : MapParent(adaptor, value) {} |
|
392 |
|
393 private: |
|
394 EdgeMap& operator=(const EdgeMap& cmap) { |
|
395 return operator=<EdgeMap>(cmap); |
|
396 } |
|
397 |
|
398 template <typename CMap> |
|
399 EdgeMap& operator=(const CMap& cmap) { |
|
400 MapParent::operator=(cmap); |
|
401 return *this; |
|
402 } |
|
403 }; |
|
404 |
|
405 }; |
|
406 |
|
407 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> |
|
408 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> |
|
409 : public GraphAdaptorBase<_Graph> { |
|
410 public: |
|
411 typedef _Graph Graph; |
|
412 typedef SubGraphAdaptorBase Adaptor; |
|
413 typedef GraphAdaptorBase<_Graph> Parent; |
|
414 protected: |
|
415 NodeFilterMap* _node_filter_map; |
|
416 EdgeFilterMap* _edge_filter_map; |
|
417 SubGraphAdaptorBase() : Parent(), |
|
418 _node_filter_map(0), _edge_filter_map(0) { } |
|
419 |
|
420 void setNodeFilterMap(NodeFilterMap& node_filter_map) { |
|
421 _node_filter_map=&node_filter_map; |
|
422 } |
|
423 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { |
|
424 _edge_filter_map=&edge_filter_map; |
|
425 } |
|
426 |
|
427 public: |
|
428 |
|
429 typedef typename Parent::Node Node; |
|
430 typedef typename Parent::Arc Arc; |
|
431 typedef typename Parent::Edge Edge; |
|
432 |
|
433 void first(Node& i) const { |
|
434 Parent::first(i); |
|
435 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); |
|
436 } |
|
437 |
|
438 void first(Arc& i) const { |
|
439 Parent::first(i); |
|
440 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
|
441 } |
|
442 |
|
443 void first(Edge& i) const { |
|
444 Parent::first(i); |
|
445 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
|
446 } |
|
447 |
|
448 void firstIn(Arc& i, const Node& n) const { |
|
449 Parent::firstIn(i, n); |
|
450 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); |
|
451 } |
|
452 |
|
453 void firstOut(Arc& i, const Node& n) const { |
|
454 Parent::firstOut(i, n); |
|
455 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); |
|
456 } |
|
457 |
|
458 void firstInc(Edge& i, bool& d, const Node& n) const { |
|
459 Parent::firstInc(i, d, n); |
|
460 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); |
|
461 } |
|
462 |
|
463 void next(Node& i) const { |
|
464 Parent::next(i); |
|
465 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); |
|
466 } |
|
467 void next(Arc& i) const { |
|
468 Parent::next(i); |
|
469 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
|
470 } |
|
471 void next(Edge& i) const { |
|
472 Parent::next(i); |
|
473 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); |
|
474 } |
|
475 void nextIn(Arc& i) const { |
|
476 Parent::nextIn(i); |
|
477 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); |
|
478 } |
|
479 |
|
480 void nextOut(Arc& i) const { |
|
481 Parent::nextOut(i); |
|
482 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); |
|
483 } |
|
484 void nextInc(Edge& i, bool& d) const { |
|
485 Parent::nextInc(i, d); |
|
486 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); |
|
487 } |
|
488 |
|
489 void hide(const Node& n) const { _node_filter_map->set(n, false); } |
|
490 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } |
|
491 |
|
492 void unHide(const Node& n) const { _node_filter_map->set(n, true); } |
|
493 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } |
|
494 |
|
495 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } |
|
496 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } |
|
497 |
|
498 typedef False NodeNumTag; |
|
499 typedef False EdgeNumTag; |
|
500 |
|
501 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
502 Arc findArc(const Node& u, const Node& v, |
|
503 const Arc& prev = INVALID) { |
|
504 Arc arc = Parent::findArc(u, v, prev); |
|
505 while (arc != INVALID && !(*_edge_filter_map)[arc]) { |
|
506 arc = Parent::findArc(u, v, arc); |
|
507 } |
|
508 return arc; |
|
509 } |
|
510 Edge findEdge(const Node& u, const Node& v, |
|
511 const Edge& prev = INVALID) { |
|
512 Edge edge = Parent::findEdge(u, v, prev); |
|
513 while (edge != INVALID && !(*_edge_filter_map)[edge]) { |
|
514 edge = Parent::findEdge(u, v, edge); |
|
515 } |
|
516 return edge; |
|
517 } |
|
518 |
|
519 template <typename _Value> |
|
520 class NodeMap : public SubMapExtender<Adaptor, |
|
521 typename Parent::template NodeMap<_Value> > { |
|
522 public: |
|
523 typedef _Value Value; |
|
524 typedef SubMapExtender<Adaptor, typename Parent:: |
|
525 template NodeMap<Value> > MapParent; |
|
526 |
|
527 NodeMap(const Adaptor& adaptor) |
|
528 : MapParent(adaptor) {} |
|
529 NodeMap(const Adaptor& adaptor, const Value& value) |
|
530 : MapParent(adaptor, value) {} |
|
531 |
|
532 private: |
|
533 NodeMap& operator=(const NodeMap& cmap) { |
|
534 return operator=<NodeMap>(cmap); |
|
535 } |
|
536 |
|
537 template <typename CMap> |
|
538 NodeMap& operator=(const CMap& cmap) { |
|
539 MapParent::operator=(cmap); |
|
540 return *this; |
|
541 } |
|
542 }; |
|
543 |
|
544 template <typename _Value> |
|
545 class ArcMap : public SubMapExtender<Adaptor, |
|
546 typename Parent::template ArcMap<_Value> > { |
|
547 public: |
|
548 typedef _Value Value; |
|
549 typedef SubMapExtender<Adaptor, typename Parent:: |
|
550 template ArcMap<Value> > MapParent; |
|
551 |
|
552 ArcMap(const Adaptor& adaptor) |
|
553 : MapParent(adaptor) {} |
|
554 ArcMap(const Adaptor& adaptor, const Value& value) |
|
555 : MapParent(adaptor, value) {} |
|
556 |
|
557 private: |
|
558 ArcMap& operator=(const ArcMap& cmap) { |
|
559 return operator=<ArcMap>(cmap); |
|
560 } |
|
561 |
|
562 template <typename CMap> |
|
563 ArcMap& operator=(const CMap& cmap) { |
|
564 MapParent::operator=(cmap); |
|
565 return *this; |
|
566 } |
|
567 }; |
|
568 |
|
569 template <typename _Value> |
|
570 class EdgeMap : public SubMapExtender<Adaptor, |
|
571 typename Parent::template EdgeMap<_Value> > { |
|
572 public: |
|
573 typedef _Value Value; |
|
574 typedef SubMapExtender<Adaptor, typename Parent:: |
|
575 template EdgeMap<Value> > MapParent; |
|
576 |
|
577 EdgeMap(const Adaptor& adaptor) |
|
578 : MapParent(adaptor) {} |
|
579 |
|
580 EdgeMap(const Adaptor& adaptor, const _Value& value) |
|
581 : MapParent(adaptor, value) {} |
|
582 |
|
583 private: |
|
584 EdgeMap& operator=(const EdgeMap& cmap) { |
|
585 return operator=<EdgeMap>(cmap); |
|
586 } |
|
587 |
|
588 template <typename CMap> |
|
589 EdgeMap& operator=(const CMap& cmap) { |
|
590 MapParent::operator=(cmap); |
|
591 return *this; |
|
592 } |
|
593 }; |
|
594 |
|
595 }; |
|
596 |
|
597 /// \ingroup graph_adaptors |
|
598 /// |
|
599 /// \brief A graph adaptor for hiding nodes and edges from an |
|
600 /// undirected graph. |
|
601 /// |
|
602 /// SubGraphAdaptor shows the graph with filtered node-set and |
|
603 /// edge-set. If the \c checked parameter is true then it filters |
|
604 /// the edge-set to do not get invalid edges which incident node is |
|
605 /// filtered. |
|
606 /// |
|
607 /// If the \c checked template parameter is false then we have to |
|
608 /// note that the node-iterator cares only the filter on the |
|
609 /// node-set, and the edge-iterator cares only the filter on the |
|
610 /// edge-set. This way the edge-map should filter all arcs which |
|
611 /// has filtered end node. |
|
612 template<typename _Graph, typename NodeFilterMap, |
|
613 typename EdgeFilterMap, bool checked = true> |
|
614 class SubGraphAdaptor : |
|
615 public GraphAdaptorExtender< |
|
616 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { |
|
617 public: |
|
618 typedef _Graph Graph; |
|
619 typedef GraphAdaptorExtender< |
|
620 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
|
621 |
|
622 typedef typename Parent::Node Node; |
|
623 typedef typename Parent::Edge Edge; |
|
624 |
|
625 protected: |
|
626 SubGraphAdaptor() { } |
|
627 public: |
|
628 |
|
629 /// \brief Constructor |
|
630 /// |
|
631 /// Creates a sub-graph-adaptor for the given graph with |
|
632 /// given node and edge map filters. |
|
633 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, |
|
634 EdgeFilterMap& edge_filter_map) { |
|
635 setGraph(_graph); |
|
636 setNodeFilterMap(node_filter_map); |
|
637 setEdgeFilterMap(edge_filter_map); |
|
638 } |
|
639 |
|
640 /// \brief Hides the node of the graph |
|
641 /// |
|
642 /// This function hides \c n in the digraph, i.e. the iteration |
|
643 /// jumps over it. This is done by simply setting the value of \c n |
|
644 /// to be false in the corresponding node-map. |
|
645 void hide(const Node& n) const { Parent::hide(n); } |
|
646 |
|
647 /// \brief Hides the edge of the graph |
|
648 /// |
|
649 /// This function hides \c e in the digraph, i.e. the iteration |
|
650 /// jumps over it. This is done by simply setting the value of \c e |
|
651 /// to be false in the corresponding edge-map. |
|
652 void hide(const Edge& e) const { Parent::hide(e); } |
|
653 |
|
654 /// \brief Unhides the node of the graph |
|
655 /// |
|
656 /// The value of \c n is set to be true in the node-map which stores |
|
657 /// hide information. If \c n was hidden previuosly, then it is shown |
|
658 /// again |
|
659 void unHide(const Node& n) const { Parent::unHide(n); } |
|
660 |
|
661 /// \brief Unhides the edge of the graph |
|
662 /// |
|
663 /// The value of \c e is set to be true in the edge-map which stores |
|
664 /// hide information. If \c e was hidden previuosly, then it is shown |
|
665 /// again |
|
666 void unHide(const Edge& e) const { Parent::unHide(e); } |
|
667 |
|
668 /// \brief Returns true if \c n is hidden. |
|
669 /// |
|
670 /// Returns true if \c n is hidden. |
|
671 /// |
|
672 bool hidden(const Node& n) const { return Parent::hidden(n); } |
|
673 |
|
674 /// \brief Returns true if \c e is hidden. |
|
675 /// |
|
676 /// Returns true if \c e is hidden. |
|
677 /// |
|
678 bool hidden(const Edge& e) const { return Parent::hidden(e); } |
|
679 }; |
|
680 |
|
681 /// \brief Just gives back a sub-graph adaptor |
|
682 /// |
|
683 /// Just gives back a sub-graph adaptor |
|
684 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
|
685 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> |
|
686 subGraphAdaptor(const Graph& graph, |
|
687 NodeFilterMap& nfm, ArcFilterMap& efm) { |
|
688 return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> |
|
689 (graph, nfm, efm); |
|
690 } |
|
691 |
|
692 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
|
693 SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap> |
|
694 subGraphAdaptor(const Graph& graph, |
|
695 NodeFilterMap& nfm, ArcFilterMap& efm) { |
|
696 return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap> |
|
697 (graph, nfm, efm); |
|
698 } |
|
699 |
|
700 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
|
701 SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap> |
|
702 subGraphAdaptor(const Graph& graph, |
|
703 NodeFilterMap& nfm, ArcFilterMap& efm) { |
|
704 return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap> |
|
705 (graph, nfm, efm); |
|
706 } |
|
707 |
|
708 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
|
709 SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap> |
|
710 subGraphAdaptor(const Graph& graph, |
|
711 NodeFilterMap& nfm, ArcFilterMap& efm) { |
|
712 return SubGraphAdaptor<const Graph, const NodeFilterMap, |
|
713 const ArcFilterMap>(graph, nfm, efm); |
|
714 } |
|
715 |
|
716 /// \ingroup graph_adaptors |
|
717 /// |
|
718 /// \brief An adaptor for hiding nodes from an graph. |
|
719 /// |
|
720 /// An adaptor for hiding nodes from an graph. This |
|
721 /// adaptor specializes SubGraphAdaptor in the way that only the |
|
722 /// node-set can be filtered. In usual case the checked parameter is |
|
723 /// true, we get the induced subgraph. But if the checked parameter |
|
724 /// is false then we can filter only isolated nodes. |
|
725 template<typename _Graph, typename _NodeFilterMap, bool checked = true> |
|
726 class NodeSubGraphAdaptor : |
|
727 public SubGraphAdaptor<_Graph, _NodeFilterMap, |
|
728 ConstMap<typename _Graph::Edge, bool>, checked> { |
|
729 public: |
|
730 typedef _Graph Graph; |
|
731 typedef _NodeFilterMap NodeFilterMap; |
|
732 typedef SubGraphAdaptor<Graph, NodeFilterMap, |
|
733 ConstMap<typename Graph::Edge, bool> > Parent; |
|
734 |
|
735 typedef typename Parent::Node Node; |
|
736 protected: |
|
737 ConstMap<typename Graph::Edge, bool> const_true_map; |
|
738 |
|
739 NodeSubGraphAdaptor() : const_true_map(true) { |
|
740 Parent::setEdgeFilterMap(const_true_map); |
|
741 } |
|
742 |
|
743 public: |
|
744 |
|
745 /// \brief Constructor |
|
746 /// |
|
747 /// Creates a node-sub-graph-adaptor for the given graph with |
|
748 /// given node map filters. |
|
749 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : |
|
750 Parent(), const_true_map(true) { |
|
751 Parent::setGraph(_graph); |
|
752 Parent::setNodeFilterMap(node_filter_map); |
|
753 Parent::setEdgeFilterMap(const_true_map); |
|
754 } |
|
755 |
|
756 /// \brief Hides the node of the graph |
|
757 /// |
|
758 /// This function hides \c n in the digraph, i.e. the iteration |
|
759 /// jumps over it. This is done by simply setting the value of \c n |
|
760 /// to be false in the corresponding node-map. |
|
761 void hide(const Node& n) const { Parent::hide(n); } |
|
762 |
|
763 /// \brief Unhides the node of the graph |
|
764 /// |
|
765 /// The value of \c n is set to be true in the node-map which stores |
|
766 /// hide information. If \c n was hidden previuosly, then it is shown |
|
767 /// again |
|
768 void unHide(const Node& n) const { Parent::unHide(n); } |
|
769 |
|
770 /// \brief Returns true if \c n is hidden. |
|
771 /// |
|
772 /// Returns true if \c n is hidden. |
|
773 /// |
|
774 bool hidden(const Node& n) const { return Parent::hidden(n); } |
|
775 |
|
776 }; |
|
777 |
|
778 /// \brief Just gives back a node-sub-graph adaptor |
|
779 /// |
|
780 /// Just gives back a node-sub-graph adaptor |
|
781 template<typename Graph, typename NodeFilterMap> |
|
782 NodeSubGraphAdaptor<const Graph, NodeFilterMap> |
|
783 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) { |
|
784 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm); |
|
785 } |
|
786 |
|
787 template<typename Graph, typename NodeFilterMap> |
|
788 NodeSubGraphAdaptor<const Graph, const NodeFilterMap> |
|
789 nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) { |
|
790 return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm); |
|
791 } |
|
792 |
|
793 /// \ingroup graph_adaptors |
|
794 /// |
|
795 /// \brief An adaptor for hiding edges from an graph. |
|
796 /// |
|
797 /// \warning Graph adaptors are in even more experimental state |
|
798 /// than the other parts of the lib. Use them at you own risk. |
|
799 /// |
|
800 /// An adaptor for hiding edges from an graph. |
|
801 /// This adaptor specializes SubGraphAdaptor in the way that |
|
802 /// only the arc-set |
|
803 /// can be filtered. |
|
804 template<typename _Graph, typename _EdgeFilterMap> |
|
805 class EdgeSubGraphAdaptor : |
|
806 public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>, |
|
807 _EdgeFilterMap, false> { |
|
808 public: |
|
809 typedef _Graph Graph; |
|
810 typedef _EdgeFilterMap EdgeFilterMap; |
|
811 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
|
812 EdgeFilterMap, false> Parent; |
|
813 typedef typename Parent::Edge Edge; |
|
814 protected: |
|
815 ConstMap<typename Graph::Node, bool> const_true_map; |
|
816 |
|
817 EdgeSubGraphAdaptor() : const_true_map(true) { |
|
818 Parent::setNodeFilterMap(const_true_map); |
|
819 } |
|
820 |
|
821 public: |
|
822 |
|
823 /// \brief Constructor |
|
824 /// |
|
825 /// Creates a edge-sub-graph-adaptor for the given graph with |
|
826 /// given node map filters. |
|
827 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) : |
|
828 Parent(), const_true_map(true) { |
|
829 Parent::setGraph(_graph); |
|
830 Parent::setNodeFilterMap(const_true_map); |
|
831 Parent::setEdgeFilterMap(edge_filter_map); |
|
832 } |
|
833 |
|
834 /// \brief Hides the edge of the graph |
|
835 /// |
|
836 /// This function hides \c e in the digraph, i.e. the iteration |
|
837 /// jumps over it. This is done by simply setting the value of \c e |
|
838 /// to be false in the corresponding edge-map. |
|
839 void hide(const Edge& e) const { Parent::hide(e); } |
|
840 |
|
841 /// \brief Unhides the edge of the graph |
|
842 /// |
|
843 /// The value of \c e is set to be true in the edge-map which stores |
|
844 /// hide information. If \c e was hidden previuosly, then it is shown |
|
845 /// again |
|
846 void unHide(const Edge& e) const { Parent::unHide(e); } |
|
847 |
|
848 /// \brief Returns true if \c e is hidden. |
|
849 /// |
|
850 /// Returns true if \c e is hidden. |
|
851 /// |
|
852 bool hidden(const Edge& e) const { return Parent::hidden(e); } |
|
853 |
|
854 }; |
|
855 |
|
856 /// \brief Just gives back an edge-sub-graph adaptor |
|
857 /// |
|
858 /// Just gives back an edge-sub-graph adaptor |
|
859 template<typename Graph, typename EdgeFilterMap> |
|
860 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap> |
|
861 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) { |
|
862 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm); |
|
863 } |
|
864 |
|
865 template<typename Graph, typename EdgeFilterMap> |
|
866 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap> |
|
867 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) { |
|
868 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm); |
|
869 } |
|
870 |
|
871 template <typename _Graph, typename _DirectionMap> |
|
872 class DirGraphAdaptorBase { |
|
873 public: |
|
874 |
|
875 typedef _Graph Graph; |
|
876 typedef _DirectionMap DirectionMap; |
|
877 |
|
878 typedef typename Graph::Node Node; |
|
879 typedef typename Graph::Edge Arc; |
|
880 |
|
881 /// \brief Reverse arc |
|
882 /// |
|
883 /// It reverse the given arc. It simply negate the direction in the map. |
|
884 void reverseArc(const Arc& arc) { |
|
885 _direction->set(arc, !(*_direction)[arc]); |
|
886 } |
|
887 |
|
888 void first(Node& i) const { _graph->first(i); } |
|
889 void first(Arc& i) const { _graph->first(i); } |
|
890 void firstIn(Arc& i, const Node& n) const { |
|
891 bool d; |
|
892 _graph->firstInc(i, d, n); |
|
893 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); |
|
894 } |
|
895 void firstOut(Arc& i, const Node& n ) const { |
|
896 bool d; |
|
897 _graph->firstInc(i, d, n); |
|
898 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); |
|
899 } |
|
900 |
|
901 void next(Node& i) const { _graph->next(i); } |
|
902 void next(Arc& i) const { _graph->next(i); } |
|
903 void nextIn(Arc& i) const { |
|
904 bool d = !(*_direction)[i]; |
|
905 _graph->nextInc(i, d); |
|
906 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); |
|
907 } |
|
908 void nextOut(Arc& i) const { |
|
909 bool d = (*_direction)[i]; |
|
910 _graph->nextInc(i, d); |
|
911 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); |
|
912 } |
|
913 |
|
914 Node source(const Arc& e) const { |
|
915 return (*_direction)[e] ? _graph->u(e) : _graph->v(e); |
|
916 } |
|
917 Node target(const Arc& e) const { |
|
918 return (*_direction)[e] ? _graph->v(e) : _graph->u(e); |
|
919 } |
|
920 |
|
921 typedef NodeNumTagIndicator<Graph> NodeNumTag; |
|
922 int nodeNum() const { return _graph->nodeNum(); } |
|
923 |
|
924 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; |
|
925 int arcNum() const { return _graph->edgeNum(); } |
|
926 |
|
927 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
|
928 Arc findArc(const Node& u, const Node& v, |
|
929 const Arc& prev = INVALID) { |
|
930 Arc arc = prev; |
|
931 bool d = arc == INVALID ? true : (*_direction)[arc]; |
|
932 if (d) { |
|
933 arc = _graph->findEdge(u, v, arc); |
|
934 while (arc != INVALID && !(*_direction)[arc]) { |
|
935 _graph->findEdge(u, v, arc); |
|
936 } |
|
937 if (arc != INVALID) return arc; |
|
938 } |
|
939 _graph->findEdge(v, u, arc); |
|
940 while (arc != INVALID && (*_direction)[arc]) { |
|
941 _graph->findEdge(u, v, arc); |
|
942 } |
|
943 return arc; |
|
944 } |
|
945 |
|
946 Node addNode() { |
|
947 return Node(_graph->addNode()); |
|
948 } |
|
949 |
|
950 Arc addArc(const Node& u, const Node& v) { |
|
951 Arc arc = _graph->addArc(u, v); |
|
952 _direction->set(arc, _graph->source(arc) == u); |
|
953 return arc; |
|
954 } |
|
955 |
|
956 void erase(const Node& i) { _graph->erase(i); } |
|
957 void erase(const Arc& i) { _graph->erase(i); } |
|
958 |
|
959 void clear() { _graph->clear(); } |
|
960 |
|
961 int id(const Node& v) const { return _graph->id(v); } |
|
962 int id(const Arc& e) const { return _graph->id(e); } |
|
963 |
|
964 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); } |
|
965 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); } |
|
966 |
|
967 int maxNodeId() const { return _graph->maxNodeId(); } |
|
968 int maxArcId() const { return _graph->maxEdgeId(); } |
|
969 |
|
970 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; |
|
971 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } |
|
972 |
|
973 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; |
|
974 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } |
|
975 |
|
976 template <typename _Value> |
|
977 class NodeMap : public _Graph::template NodeMap<_Value> { |
|
978 public: |
|
979 |
|
980 typedef typename _Graph::template NodeMap<_Value> Parent; |
|
981 |
|
982 explicit NodeMap(const DirGraphAdaptorBase& adapter) |
|
983 : Parent(*adapter._graph) {} |
|
984 |
|
985 NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value) |
|
986 : Parent(*adapter._graph, value) {} |
|
987 |
|
988 private: |
|
989 NodeMap& operator=(const NodeMap& cmap) { |
|
990 return operator=<NodeMap>(cmap); |
|
991 } |
|
992 |
|
993 template <typename CMap> |
|
994 NodeMap& operator=(const CMap& cmap) { |
|
995 Parent::operator=(cmap); |
|
996 return *this; |
|
997 } |
|
998 |
|
999 }; |
|
1000 |
|
1001 template <typename _Value> |
|
1002 class ArcMap : public _Graph::template EdgeMap<_Value> { |
|
1003 public: |
|
1004 |
|
1005 typedef typename Graph::template EdgeMap<_Value> Parent; |
|
1006 |
|
1007 explicit ArcMap(const DirGraphAdaptorBase& adapter) |
|
1008 : Parent(*adapter._graph) { } |
|
1009 |
|
1010 ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value) |
|
1011 : Parent(*adapter._graph, value) { } |
|
1012 |
|
1013 private: |
|
1014 ArcMap& operator=(const ArcMap& cmap) { |
|
1015 return operator=<ArcMap>(cmap); |
|
1016 } |
|
1017 |
|
1018 template <typename CMap> |
|
1019 ArcMap& operator=(const CMap& cmap) { |
|
1020 Parent::operator=(cmap); |
|
1021 return *this; |
|
1022 } |
|
1023 }; |
|
1024 |
|
1025 |
|
1026 |
|
1027 protected: |
|
1028 Graph* _graph; |
|
1029 DirectionMap* _direction; |
|
1030 |
|
1031 void setDirectionMap(DirectionMap& direction) { |
|
1032 _direction = &direction; |
|
1033 } |
|
1034 |
|
1035 void setGraph(Graph& graph) { |
|
1036 _graph = &graph; |
|
1037 } |
|
1038 |
|
1039 }; |
|
1040 |
|
1041 |
|
1042 /// \ingroup graph_adaptors |
|
1043 /// |
|
1044 /// \brief A directed graph is made from an graph by an adaptor |
|
1045 /// |
|
1046 /// This adaptor gives a direction for each edge in the undirected |
|
1047 /// graph. The direction of the arcs stored in the |
|
1048 /// DirectionMap. This map is a bool map on the edges. If |
|
1049 /// the edge is mapped to true then the direction of the directed |
|
1050 /// arc will be the same as the default direction of the edge. The |
|
1051 /// arcs can be easily reverted by the \ref |
|
1052 /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the |
|
1053 /// adaptor. |
|
1054 /// |
|
1055 /// It can be used to solve orientation problems on directed graphs. |
|
1056 /// For example how can we orient an graph to get the minimum |
|
1057 /// number of strongly connected components. If we orient the arcs with |
|
1058 /// the dfs algorithm out from the source then we will get such an |
|
1059 /// orientation. |
|
1060 /// |
|
1061 /// We use the \ref DfsVisitor "visitor" interface of the |
|
1062 /// \ref DfsVisit "dfs" algorithm: |
|
1063 ///\code |
|
1064 /// template <typename DirMap> |
|
1065 /// class OrientVisitor : public DfsVisitor<Graph> { |
|
1066 /// public: |
|
1067 /// |
|
1068 /// OrientVisitor(const Graph& graph, DirMap& dirMap) |
|
1069 /// : _graph(graph), _dirMap(dirMap), _processed(graph, false) {} |
|
1070 /// |
|
1071 /// void discover(const Arc& arc) { |
|
1072 /// _processed.set(arc, true); |
|
1073 /// _dirMap.set(arc, _graph.direction(arc)); |
|
1074 /// } |
|
1075 /// |
|
1076 /// void examine(const Arc& arc) { |
|
1077 /// if (_processed[arc]) return; |
|
1078 /// _processed.set(arc, true); |
|
1079 /// _dirMap.set(arc, _graph.direction(arc)); |
|
1080 /// } |
|
1081 /// |
|
1082 /// private: |
|
1083 /// const Graph& _graph; |
|
1084 /// DirMap& _dirMap; |
|
1085 /// Graph::EdgeMap<bool> _processed; |
|
1086 /// }; |
|
1087 ///\endcode |
|
1088 /// |
|
1089 /// And now we can use the orientation: |
|
1090 ///\code |
|
1091 /// Graph::EdgeMap<bool> dmap(graph); |
|
1092 /// |
|
1093 /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor; |
|
1094 /// Visitor visitor(graph, dmap); |
|
1095 /// |
|
1096 /// DfsVisit<Graph, Visitor> dfs(graph, visitor); |
|
1097 /// |
|
1098 /// dfs.run(); |
|
1099 /// |
|
1100 /// typedef DirGraphAdaptor<Graph> DGraph; |
|
1101 /// DGraph dgraph(graph, dmap); |
|
1102 /// |
|
1103 /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == |
|
1104 /// countBiArcConnectedComponents(graph), "Wrong Orientation"); |
|
1105 ///\endcode |
|
1106 /// |
|
1107 /// The number of the bi-connected components is a lower bound for |
|
1108 /// the number of the strongly connected components in the directed |
|
1109 /// graph because if we contract the bi-connected components to |
|
1110 /// nodes we will get a tree therefore we cannot orient arcs in |
|
1111 /// both direction between bi-connected components. In the other way |
|
1112 /// the algorithm will orient one component to be strongly |
|
1113 /// connected. The two relations proof that the assertion will |
|
1114 /// be always true and the found solution is optimal. |
|
1115 /// |
|
1116 /// \sa DirGraphAdaptorBase |
|
1117 /// \sa dirGraphAdaptor |
|
1118 template<typename _Graph, |
|
1119 typename DirectionMap = typename _Graph::template EdgeMap<bool> > |
|
1120 class DirGraphAdaptor : |
|
1121 public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > { |
|
1122 public: |
|
1123 typedef _Graph Graph; |
|
1124 typedef DigraphAdaptorExtender< |
|
1125 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent; |
|
1126 typedef typename Parent::Arc Arc; |
|
1127 protected: |
|
1128 DirGraphAdaptor() { } |
|
1129 public: |
|
1130 |
|
1131 /// \brief Constructor of the adaptor |
|
1132 /// |
|
1133 /// Constructor of the adaptor |
|
1134 DirGraphAdaptor(Graph& graph, DirectionMap& direction) { |
|
1135 setGraph(graph); |
|
1136 setDirectionMap(direction); |
|
1137 } |
|
1138 |
|
1139 /// \brief Reverse arc |
|
1140 /// |
|
1141 /// It reverse the given arc. It simply negate the direction in the map. |
|
1142 void reverseArc(const Arc& a) { |
|
1143 Parent::reverseArc(a); |
|
1144 } |
|
1145 }; |
|
1146 |
|
1147 /// \brief Just gives back a DirGraphAdaptor |
|
1148 /// |
|
1149 /// Just gives back a DirGraphAdaptor |
|
1150 template<typename Graph, typename DirectionMap> |
|
1151 DirGraphAdaptor<const Graph, DirectionMap> |
|
1152 dirGraphAdaptor(const Graph& graph, DirectionMap& dm) { |
|
1153 return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm); |
|
1154 } |
|
1155 |
|
1156 template<typename Graph, typename DirectionMap> |
|
1157 DirGraphAdaptor<const Graph, const DirectionMap> |
|
1158 dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) { |
|
1159 return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm); |
|
1160 } |
|
1161 |
|
1162 } |
|
1163 |
|
1164 #endif |
|