|
1 /* -*- C++ -*- |
|
2 * lemon/sub_graph.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_SUB_GRAPH_H |
|
18 #define LEMON_SUB_GRAPH_H |
|
19 |
|
20 #include <lemon/graph_adaptor.h> |
|
21 |
|
22 namespace lemon { |
|
23 |
|
24 /// \brief Base for the SubGraph. |
|
25 /// |
|
26 /// Base for the SubGraph. |
|
27 template <typename _Graph> |
|
28 class SubGraphBase : public GraphAdaptorBase<const _Graph> { |
|
29 public: |
|
30 typedef _Graph Graph; |
|
31 typedef SubGraphBase<_Graph> SubGraph; |
|
32 typedef GraphAdaptorBase<const _Graph> Parent; |
|
33 typedef Parent Base; |
|
34 |
|
35 typedef typename Parent::Node Node; |
|
36 typedef typename Parent::Edge Edge; |
|
37 |
|
38 |
|
39 protected: |
|
40 |
|
41 class NodesImpl; |
|
42 class EdgesImpl; |
|
43 |
|
44 SubGraphBase() {} |
|
45 |
|
46 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) { |
|
47 Parent::setGraph(_graph); |
|
48 nodes = &_nodes; |
|
49 edges = &_edges; |
|
50 firstNode = INVALID; |
|
51 |
|
52 Node node; |
|
53 Parent::first(node); |
|
54 while (node != INVALID) { |
|
55 (*nodes)[node].prev = node; |
|
56 (*nodes)[node].firstIn = INVALID; |
|
57 (*nodes)[node].firstOut = INVALID; |
|
58 Parent::next(node); |
|
59 } |
|
60 |
|
61 Edge edge; |
|
62 Parent::first(edge); |
|
63 while (edge != INVALID) { |
|
64 (*edges)[edge].prevOut = edge; |
|
65 Parent::next(edge); |
|
66 } |
|
67 } |
|
68 |
|
69 public: |
|
70 |
|
71 void first(Node& node) const { |
|
72 node = firstNode; |
|
73 } |
|
74 void next(Node& node) const { |
|
75 node = (*nodes)[node].next; |
|
76 } |
|
77 |
|
78 void first(Edge& edge) const { |
|
79 Node node = firstNode; |
|
80 while (node != INVALID && (*nodes)[node].firstOut == INVALID) { |
|
81 node = (*nodes)[node].next; |
|
82 } |
|
83 if (node == INVALID) { |
|
84 edge = INVALID; |
|
85 } else { |
|
86 edge = (*nodes)[node].firstOut; |
|
87 } |
|
88 } |
|
89 void next(Edge& edge) const { |
|
90 if ((*edges)[edge].nextOut != INVALID) { |
|
91 edge = (*edges)[edge].nextOut; |
|
92 } else { |
|
93 Node node = (*nodes)[source(edge)].next; |
|
94 while (node != INVALID && (*nodes)[node].firstOut == INVALID) { |
|
95 node = (*nodes)[node].next; |
|
96 } |
|
97 if (node == INVALID) { |
|
98 edge = INVALID; |
|
99 } else { |
|
100 edge = (*nodes)[node].firstOut; |
|
101 } |
|
102 } |
|
103 } |
|
104 |
|
105 void firstOut(Edge& edge, const Node& node) const { |
|
106 edge = (*nodes)[node].firstOut; |
|
107 } |
|
108 void nextOut(Edge& edge) const { |
|
109 edge = (*edges)[edge].nextOut; |
|
110 } |
|
111 |
|
112 void firstIn(Edge& edge, const Node& node) const { |
|
113 edge = (*nodes)[node].firstIn; |
|
114 } |
|
115 void nextIn(Edge& edge) const { |
|
116 edge = (*edges)[edge].nextIn; |
|
117 } |
|
118 |
|
119 /// \brief Returns true when the given node is hidden. |
|
120 /// |
|
121 /// Returns true when the given node is hidden. |
|
122 bool hidden(const Node& node) const { |
|
123 return (*nodes)[node].prev == node; |
|
124 } |
|
125 |
|
126 /// \brief Hide the given node in the sub-graph. |
|
127 /// |
|
128 /// Hide the given node in the sub graph. It just lace out from |
|
129 /// the linked lists the given node. If there are incoming or outgoing |
|
130 /// edges into or from this node then all of these will be hidden. |
|
131 void hide(const Node& node) { |
|
132 if (hidden(node)) return; |
|
133 Edge edge; |
|
134 firstOut(edge, node); |
|
135 while (edge != INVALID) { |
|
136 hide(edge); |
|
137 firstOut(edge, node); |
|
138 } |
|
139 |
|
140 firstOut(edge, node); |
|
141 while (edge != INVALID) { |
|
142 hide(edge); |
|
143 firstOut(edge, node); |
|
144 } |
|
145 if ((*nodes)[node].prev != INVALID) { |
|
146 (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next; |
|
147 } else { |
|
148 firstNode = (*nodes)[node].next; |
|
149 } |
|
150 if ((*nodes)[node].next != INVALID) { |
|
151 (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev; |
|
152 } |
|
153 (*nodes)[node].prev = node; |
|
154 (*nodes)[node].firstIn = INVALID; |
|
155 (*nodes)[node].firstOut = INVALID; |
|
156 } |
|
157 |
|
158 /// \brief Unhide the given node in the sub-graph. |
|
159 /// |
|
160 /// Unhide the given node in the sub graph. It just lace in the given |
|
161 /// node into the linked lists. |
|
162 void unHide(const Node& node) { |
|
163 if (!hidden(node)) return; |
|
164 (*nodes)[node].next = firstNode; |
|
165 (*nodes)[node].prev = INVALID; |
|
166 if ((*nodes)[node].next != INVALID) { |
|
167 (*nodes)[(*nodes)[node].next].prev = node; |
|
168 } |
|
169 firstNode = node; |
|
170 } |
|
171 |
|
172 /// \brief Returns true when the given edge is hidden. |
|
173 /// |
|
174 /// Returns true when the given edge is hidden. |
|
175 bool hidden(const Edge& edge) const { |
|
176 return (*edges)[edge].prevOut == edge; |
|
177 } |
|
178 |
|
179 /// \brief Hide the given edge in the sub-graph. |
|
180 /// |
|
181 /// Hide the given edge in the sub graph. It just lace out from |
|
182 /// the linked lists the given edge. |
|
183 void hide(const Edge& edge) { |
|
184 if (hidden(edge)) return; |
|
185 if ((*edges)[edge].prevOut == edge) return; |
|
186 if ((*edges)[edge].prevOut != INVALID) { |
|
187 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut; |
|
188 } else { |
|
189 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut; |
|
190 } |
|
191 if ((*edges)[edge].nextOut != INVALID) { |
|
192 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut; |
|
193 } |
|
194 |
|
195 if ((*edges)[edge].prevIn != INVALID) { |
|
196 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn; |
|
197 } else { |
|
198 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn; |
|
199 } |
|
200 if ((*edges)[edge].nextIn != INVALID) { |
|
201 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn; |
|
202 } |
|
203 (*edges)[edge].next = edge; |
|
204 } |
|
205 |
|
206 /// \brief Unhide the given edge in the sub-graph. |
|
207 /// |
|
208 /// Unhide the given edge in the sub graph. It just lace in the given |
|
209 /// edge into the linked lists. If the source or the target of the |
|
210 /// node is hidden then it will unhide it. |
|
211 void unHide(const Edge& edge) { |
|
212 if (!hidden(edge)) return; |
|
213 |
|
214 Node node; |
|
215 |
|
216 node = Parent::source(edge); |
|
217 unHide(node); |
|
218 (*edges)[edge].nextOut = (*nodes)[node].firstOut; |
|
219 (*edges)[edge].prevOut = INVALID; |
|
220 if ((*edges)[edge].nextOut != INVALID) { |
|
221 (*edges)[(*edges)[edge].nextOut].prevOut = edge; |
|
222 } |
|
223 (*nodes)[node].firstOut = edge; |
|
224 |
|
225 node = Parent::target(edge); |
|
226 unHide(node); |
|
227 (*edges)[edge].nextIn = (*nodes)[node].firstIn; |
|
228 (*edges)[edge].prevIn = INVALID; |
|
229 if ((*edges)[edge].nextIn != INVALID) { |
|
230 (*edges)[(*edges)[edge].nextIn].prevIn = edge; |
|
231 } |
|
232 (*nodes)[node].firstIn = edge; |
|
233 } |
|
234 |
|
235 typedef False NodeNumTag; |
|
236 typedef False EdgeNumTag; |
|
237 |
|
238 protected: |
|
239 struct NodeT { |
|
240 Node prev, next; |
|
241 Edge firstIn, firstOut; |
|
242 }; |
|
243 class NodesImpl : public Graph::template NodeMap<NodeT> { |
|
244 friend class SubGraphBase; |
|
245 public: |
|
246 typedef typename Graph::template NodeMap<NodeT> Parent; |
|
247 |
|
248 NodesImpl(SubGraph& _adaptor, const Graph& _graph) |
|
249 : Parent(_graph), adaptor(_adaptor) {} |
|
250 |
|
251 virtual ~NodesImpl() {} |
|
252 |
|
253 virtual void build() { |
|
254 Parent::build(); |
|
255 Node node; |
|
256 adaptor.Base::first(node); |
|
257 while (node != INVALID) { |
|
258 Parent::operator[](node).prev = node; |
|
259 Parent::operator[](node).firstIn = INVALID; |
|
260 Parent::operator[](node).firstOut = INVALID; |
|
261 adaptor.Base::next(node); |
|
262 } |
|
263 } |
|
264 |
|
265 virtual void clear() { |
|
266 adaptor.firstNode = INVALID; |
|
267 Parent::clear(); |
|
268 } |
|
269 |
|
270 virtual void add(const Node& node) { |
|
271 Parent::add(node); |
|
272 Parent::operator[](node).prev = node; |
|
273 Parent::operator[](node).firstIn = INVALID; |
|
274 Parent::operator[](node).firstOut = INVALID; |
|
275 } |
|
276 virtual void add(const std::vector<Node>& nodes) { |
|
277 Parent::add(nodes); |
|
278 for (int i = 0; i < (int)nodes.size(); ++i) { |
|
279 Parent::operator[](nodes[i]).prev = nodes[i]; |
|
280 Parent::operator[](nodes[i]).firstIn = INVALID; |
|
281 Parent::operator[](nodes[i]).firstOut = INVALID; |
|
282 } |
|
283 } |
|
284 |
|
285 virtual void erase(const Node& node) { |
|
286 adaptor.hide(node); |
|
287 Parent::erase(node); |
|
288 } |
|
289 |
|
290 virtual void erase(const std::vector<Node>& nodes) { |
|
291 for (int i = 0; i < (int)nodes.size(); ++i) { |
|
292 adaptor.hide(nodes[i]); |
|
293 } |
|
294 Parent::erase(nodes); |
|
295 } |
|
296 |
|
297 private: |
|
298 SubGraph& adaptor; |
|
299 }; |
|
300 |
|
301 struct EdgeT { |
|
302 Edge prevOut, nextOut; |
|
303 Edge prevIn, nextIn; |
|
304 }; |
|
305 class EdgesImpl : public Graph::template EdgeMap<EdgeT> { |
|
306 friend class SubGraphBase; |
|
307 public: |
|
308 typedef typename Graph::template EdgeMap<EdgeT> Parent; |
|
309 |
|
310 EdgesImpl(SubGraph& _adaptor, const Graph& _graph) |
|
311 : Parent(_graph), adaptor(_adaptor) {} |
|
312 |
|
313 virtual ~EdgesImpl() {} |
|
314 |
|
315 virtual void build() { |
|
316 Parent::build(); |
|
317 Edge edge; |
|
318 adaptor.Base::first(edge); |
|
319 while (edge != INVALID) { |
|
320 Parent::operator[](edge).prevOut = edge; |
|
321 adaptor.Base::next(edge); |
|
322 } |
|
323 } |
|
324 |
|
325 virtual void clear() { |
|
326 Node node; |
|
327 adaptor.first(node); |
|
328 while (node != INVALID) { |
|
329 (*adaptor.nodes).firstIn = INVALID; |
|
330 (*adaptor.nodes).firstOut = INVALID; |
|
331 adaptor.next(node); |
|
332 } |
|
333 Parent::clear(); |
|
334 } |
|
335 |
|
336 virtual void add(const Edge& edge) { |
|
337 Parent::add(edge); |
|
338 Parent::operator[](edge).prevOut = edge; |
|
339 } |
|
340 |
|
341 virtual void add(const std::vector<Edge>& edges) { |
|
342 Parent::add(edges); |
|
343 for (int i = 0; i < (int)edges.size(); ++i) { |
|
344 Parent::operator[](edges[i]).prevOut = edges[i]; |
|
345 } |
|
346 } |
|
347 |
|
348 virtual void erase(const Edge& edge) { |
|
349 adaptor.hide(edge); |
|
350 Parent::erase(edge); |
|
351 } |
|
352 |
|
353 virtual void erase(const std::vector<Edge>& edges) { |
|
354 for (int i = 0; i < (int)edges.size(); ++i) { |
|
355 adaptor.hide(edges[i]); |
|
356 } |
|
357 Parent::erase(edge); |
|
358 } |
|
359 |
|
360 private: |
|
361 SubGraph& adaptor; |
|
362 }; |
|
363 |
|
364 NodesImpl* nodes; |
|
365 EdgesImpl* edges; |
|
366 Node firstNode; |
|
367 }; |
|
368 |
|
369 /// \ingroup semi_adaptors |
|
370 /// |
|
371 /// \brief Graph which uses a subset of an other graph's nodes and edges. |
|
372 /// |
|
373 /// Graph which uses a subset of an other graph's nodes and edges. This class |
|
374 /// is an alternative to the SubGraphAdaptor which is created for the |
|
375 /// same reason. The main difference between the two class that it |
|
376 /// makes linked lists on the unhidden nodes and edges what cause that |
|
377 /// on sparse subgraphs the algorithms can be more efficient and some times |
|
378 /// provide better time complexity. On other way this implemetation is |
|
379 /// less efficient in most case when the subgraph filters out only |
|
380 /// a few nodes or edges. |
|
381 /// |
|
382 /// \see SubGraphAdaptor |
|
383 /// \see EdgeSubGraphBase |
|
384 template <typename Graph> |
|
385 class SubGraph |
|
386 : public IterableGraphExtender< SubGraphBase<Graph> > { |
|
387 public: |
|
388 typedef IterableGraphExtender< SubGraphBase<Graph> > Parent; |
|
389 public: |
|
390 /// \brief Constructor for sub-graph. |
|
391 /// |
|
392 /// Constructor for sub-graph. Initially all the edges and nodes |
|
393 /// are hidden in the graph. |
|
394 SubGraph(const Graph& _graph) |
|
395 : Parent(), nodes(*this, _graph), edges(*this, _graph) { |
|
396 Parent::construct(_graph, nodes, edges); |
|
397 } |
|
398 private: |
|
399 typename Parent::NodesImpl nodes; |
|
400 typename Parent::EdgesImpl edges; |
|
401 }; |
|
402 |
|
403 /// \brief Base for the EdgeSubGraph. |
|
404 /// |
|
405 /// Base for the EdgeSubGraph. |
|
406 template <typename _Graph> |
|
407 class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> { |
|
408 public: |
|
409 typedef _Graph Graph; |
|
410 typedef EdgeSubGraphBase<_Graph> SubGraph; |
|
411 typedef GraphAdaptorBase<const _Graph> Parent; |
|
412 typedef Parent Base; |
|
413 |
|
414 typedef typename Parent::Node Node; |
|
415 typedef typename Parent::Edge Edge; |
|
416 |
|
417 |
|
418 protected: |
|
419 |
|
420 class NodesImpl; |
|
421 class EdgesImpl; |
|
422 |
|
423 EdgeSubGraphBase() {} |
|
424 |
|
425 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) { |
|
426 Parent::setGraph(_graph); |
|
427 nodes = &_nodes; |
|
428 edges = &_edges; |
|
429 |
|
430 Node node; |
|
431 Parent::first(node); |
|
432 while (node != INVALID) { |
|
433 (*nodes)[node].firstIn = INVALID; |
|
434 (*nodes)[node].firstOut = INVALID; |
|
435 Parent::next(node); |
|
436 } |
|
437 |
|
438 Edge edge; |
|
439 Parent::first(edge); |
|
440 while (edge != INVALID) { |
|
441 (*edges)[edge].prevOut = edge; |
|
442 Parent::next(edge); |
|
443 } |
|
444 } |
|
445 |
|
446 public: |
|
447 |
|
448 void first(Node& node) const { |
|
449 Parent::first(node); |
|
450 } |
|
451 void next(Node& node) const { |
|
452 Parent::next(node); |
|
453 } |
|
454 |
|
455 void first(Edge& edge) const { |
|
456 Node node; |
|
457 Parent::first(node); |
|
458 while (node != INVALID && (*nodes)[node].firstOut == INVALID) { |
|
459 Parent::next(node); |
|
460 } |
|
461 if (node == INVALID) { |
|
462 edge = INVALID; |
|
463 } else { |
|
464 edge = (*nodes)[node].firstOut; |
|
465 } |
|
466 } |
|
467 void next(Edge& edge) const { |
|
468 if ((*edges)[edge].nextOut != INVALID) { |
|
469 edge = (*edges)[edge].nextOut; |
|
470 } else { |
|
471 Node node = source(edge); |
|
472 Parent::next(node); |
|
473 while (node != INVALID && (*nodes)[node].firstOut == INVALID) { |
|
474 Parent::next(node); |
|
475 } |
|
476 if (node == INVALID) { |
|
477 edge = INVALID; |
|
478 } else { |
|
479 edge = (*nodes)[node].firstOut; |
|
480 } |
|
481 } |
|
482 } |
|
483 |
|
484 void firstOut(Edge& edge, const Node& node) const { |
|
485 edge = (*nodes)[node].firstOut; |
|
486 } |
|
487 void nextOut(Edge& edge) const { |
|
488 edge = (*edges)[edge].nextOut; |
|
489 } |
|
490 |
|
491 void firstIn(Edge& edge, const Node& node) const { |
|
492 edge = (*nodes)[node].firstIn; |
|
493 } |
|
494 void nextIn(Edge& edge) const { |
|
495 edge = (*edges)[edge].nextIn; |
|
496 } |
|
497 |
|
498 /// \brief Returns true when the given edge is hidden. |
|
499 /// |
|
500 /// Returns true when the given edge is hidden. |
|
501 bool hidden(const Edge& edge) const { |
|
502 return (*edges)[edge].prevOut == edge; |
|
503 } |
|
504 |
|
505 /// \brief Hide the given edge in the sub-graph. |
|
506 /// |
|
507 /// Hide the given edge in the sub graph. It just lace out from |
|
508 /// the linked lists the given edge. |
|
509 void hide(const Edge& edge) { |
|
510 if (hidden(edge)) return; |
|
511 if ((*edges)[edge].prevOut != INVALID) { |
|
512 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut; |
|
513 } else { |
|
514 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut; |
|
515 } |
|
516 if ((*edges)[edge].nextOut != INVALID) { |
|
517 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut; |
|
518 } |
|
519 |
|
520 if ((*edges)[edge].prevIn != INVALID) { |
|
521 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn; |
|
522 } else { |
|
523 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn; |
|
524 } |
|
525 if ((*edges)[edge].nextIn != INVALID) { |
|
526 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn; |
|
527 } |
|
528 (*edges)[edge].prevOut = edge; |
|
529 } |
|
530 |
|
531 /// \brief Unhide the given edge in the sub-graph. |
|
532 /// |
|
533 /// Unhide the given edge in the sub graph. It just lace in the given |
|
534 /// edge into the linked lists. |
|
535 void unHide(const Edge& edge) { |
|
536 if (!hidden(edge)) return; |
|
537 Node node; |
|
538 |
|
539 node = Parent::source(edge); |
|
540 (*edges)[edge].nextOut = (*nodes)[node].firstOut; |
|
541 (*edges)[edge].prevOut = INVALID; |
|
542 if ((*edges)[edge].nextOut != INVALID) { |
|
543 (*edges)[(*edges)[edge].nextOut].prevOut = edge; |
|
544 } |
|
545 (*nodes)[node].firstOut = edge; |
|
546 |
|
547 node = Parent::target(edge); |
|
548 (*edges)[edge].nextIn = (*nodes)[node].firstIn; |
|
549 (*edges)[edge].prevIn = INVALID; |
|
550 if ((*edges)[edge].nextIn != INVALID) { |
|
551 (*edges)[(*edges)[edge].nextIn].prevIn = edge; |
|
552 } |
|
553 (*nodes)[node].firstIn = edge; |
|
554 } |
|
555 |
|
556 protected: |
|
557 struct NodeT { |
|
558 Edge firstIn, firstOut; |
|
559 }; |
|
560 class NodesImpl : public Graph::template NodeMap<NodeT> { |
|
561 friend class EdgeSubGraphBase; |
|
562 public: |
|
563 typedef typename Graph::template NodeMap<NodeT> Parent; |
|
564 |
|
565 NodesImpl(SubGraph& _adaptor, const Graph& _graph) |
|
566 : Parent(_graph), adaptor(_adaptor) {} |
|
567 |
|
568 virtual ~NodesImpl() {} |
|
569 |
|
570 virtual void build() { |
|
571 Parent::build(); |
|
572 Node node; |
|
573 adaptor.Base::first(node); |
|
574 while (node != INVALID) { |
|
575 Parent::operator[](node).firstIn = INVALID; |
|
576 Parent::operator[](node).firstOut = INVALID; |
|
577 adaptor.Base::next(node); |
|
578 } |
|
579 } |
|
580 |
|
581 virtual void add(const Node& node) { |
|
582 Parent::add(node); |
|
583 Parent::operator[](node).firstIn = INVALID; |
|
584 Parent::operator[](node).firstOut = INVALID; |
|
585 } |
|
586 |
|
587 private: |
|
588 SubGraph& adaptor; |
|
589 }; |
|
590 |
|
591 struct EdgeT { |
|
592 Edge prevOut, nextOut; |
|
593 Edge prevIn, nextIn; |
|
594 }; |
|
595 class EdgesImpl : public Graph::template EdgeMap<EdgeT> { |
|
596 friend class EdgeSubGraphBase; |
|
597 public: |
|
598 typedef typename Graph::template EdgeMap<EdgeT> Parent; |
|
599 |
|
600 EdgesImpl(SubGraph& _adaptor, const Graph& _graph) |
|
601 : Parent(_graph), adaptor(_adaptor) {} |
|
602 |
|
603 virtual ~EdgesImpl() {} |
|
604 |
|
605 virtual void build() { |
|
606 Parent::build(); |
|
607 Edge edge; |
|
608 adaptor.Base::first(edge); |
|
609 while (edge != INVALID) { |
|
610 Parent::operator[](edge).prevOut = edge; |
|
611 adaptor.Base::next(edge); |
|
612 } |
|
613 } |
|
614 |
|
615 virtual void clear() { |
|
616 Node node; |
|
617 adaptor.Base::first(node); |
|
618 while (node != INVALID) { |
|
619 (*adaptor.nodes)[node].firstIn = INVALID; |
|
620 (*adaptor.nodes)[node].firstOut = INVALID; |
|
621 adaptor.Base::next(node); |
|
622 } |
|
623 Parent::clear(); |
|
624 } |
|
625 |
|
626 virtual void add(const Edge& edge) { |
|
627 Parent::add(edge); |
|
628 Parent::operator[](edge).prevOut = edge; |
|
629 } |
|
630 |
|
631 virtual void add(const std::vector<Edge>& edges) { |
|
632 Parent::add(edges); |
|
633 for (int i = 0; i < (int)edges.size(); ++i) { |
|
634 Parent::operator[](edges[i]).prevOut = edges[i]; |
|
635 } |
|
636 } |
|
637 |
|
638 virtual void erase(const Edge& edge) { |
|
639 adaptor.hide(edge); |
|
640 Parent::erase(edge); |
|
641 } |
|
642 |
|
643 virtual void erase(const std::vector<Edge>& edges) { |
|
644 for (int i = 0; i < (int)edges.size(); ++i) { |
|
645 adaptor.hide(edges[i]); |
|
646 } |
|
647 Parent::erase(edge); |
|
648 } |
|
649 |
|
650 private: |
|
651 SubGraph& adaptor; |
|
652 }; |
|
653 |
|
654 NodesImpl* nodes; |
|
655 EdgesImpl* edges; |
|
656 }; |
|
657 |
|
658 /// \ingroup semi_adaptors |
|
659 /// |
|
660 /// \brief Graph which uses a subset of an other graph's edges. |
|
661 /// |
|
662 /// Graph which uses a subset of an other graph's edges. This class |
|
663 /// is an alternative to the EdgeSubGraphAdaptor which is created for the |
|
664 /// same reason. The main difference between the two class that it |
|
665 /// makes linked lists on the unhidden edges what cause that |
|
666 /// on sparse subgraphs the algorithms can be more efficient and some times |
|
667 /// provide better time complexity. On other way this implemetation is |
|
668 /// less efficient in most case when the subgraph filters out only |
|
669 /// a few edges. |
|
670 /// |
|
671 /// \see EdgeSubGraphAdaptor |
|
672 /// \see EdgeSubGraphBase |
|
673 template <typename Graph> |
|
674 class EdgeSubGraph |
|
675 : public IterableGraphExtender< EdgeSubGraphBase<Graph> > { |
|
676 public: |
|
677 typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent; |
|
678 public: |
|
679 /// \brief Constructor for sub-graph. |
|
680 /// |
|
681 /// Constructor for sub-graph. Initially all the edges are hidden in the |
|
682 /// graph. |
|
683 EdgeSubGraph(const Graph& _graph) |
|
684 : Parent(), nodes(*this, _graph), edges(*this, _graph) { |
|
685 Parent::construct(_graph, nodes, edges); |
|
686 } |
|
687 private: |
|
688 typename Parent::NodesImpl nodes; |
|
689 typename Parent::EdgesImpl edges; |
|
690 }; |
|
691 |
|
692 |
|
693 // template<typename Graph, typename Number, |
|
694 // typename CapacityMap, typename FlowMap> |
|
695 // class ResGraph |
|
696 // : public IterableGraphExtender<EdgeSubGraphBase< |
|
697 // UndirGraphAdaptor<Graph> > > { |
|
698 // public: |
|
699 // typedef IterableGraphExtender<EdgeSubGraphBase< |
|
700 // UndirGraphAdaptor<Graph> > > Parent; |
|
701 |
|
702 // protected: |
|
703 // UndirGraphAdaptor<Graph> undir; |
|
704 |
|
705 // const CapacityMap* capacity; |
|
706 // FlowMap* flow; |
|
707 |
|
708 // typename Parent::NodesImpl nodes; |
|
709 // typename Parent::EdgesImpl edges; |
|
710 |
|
711 // void setCapacityMap(const CapacityMap& _capacity) { |
|
712 // capacity=&_capacity; |
|
713 // } |
|
714 |
|
715 // void setFlowMap(FlowMap& _flow) { |
|
716 // flow=&_flow; |
|
717 // } |
|
718 |
|
719 // public: |
|
720 |
|
721 // typedef typename UndirGraphAdaptor<Graph>::Node Node; |
|
722 // typedef typename UndirGraphAdaptor<Graph>::Edge Edge; |
|
723 // typedef typename UndirGraphAdaptor<Graph>::UndirEdge UndirEdge; |
|
724 |
|
725 // ResGraphAdaptor(Graph& _graph, |
|
726 // const CapacityMap& _capacity, FlowMap& _flow) |
|
727 // : Parent(), undir(_graph), capacity(&_capacity), flow(&_flow), |
|
728 // nodes(*this, _graph), edges(*this, _graph) { |
|
729 // Parent::construct(undir, nodes, edges); |
|
730 // setFlowMap(_flow); |
|
731 // setCapacityMap(_capacity); |
|
732 // typename Graph::Edge edge; |
|
733 // for (_graph.first(edge); edge != INVALID; _graph.next(edge)) { |
|
734 // if ((*flow)[edge] != (*capacity)[edge]) { |
|
735 // Parent::unHide(direct(edge, true)); |
|
736 // } |
|
737 // if ((*flow)[edge] != 0) { |
|
738 // Parent::unHide(direct(edge, false)); |
|
739 // } |
|
740 // } |
|
741 // } |
|
742 |
|
743 // void augment(const Edge& e, Number a) { |
|
744 // if (direction(e)) { |
|
745 // flow->set(e, (*flow)[e]+a); |
|
746 // } else { |
|
747 // flow->set(e, (*flow)[e]-a); |
|
748 // } |
|
749 // if ((*flow)[e] == (*capacity)[e]) { |
|
750 // Parent::hide(e); |
|
751 // } else { |
|
752 // Parent::unHide(e); |
|
753 // } |
|
754 // if ((*flow)[e] == 0) { |
|
755 // Parent::hide(oppositeEdge(e)); |
|
756 // } else { |
|
757 // Parent::unHide(oppositeEdge(e)); |
|
758 // } |
|
759 // } |
|
760 |
|
761 // Number resCap(const Edge& e) { |
|
762 // if (direction(e)) { |
|
763 // return (*capacity)[e]-(*flow)[e]; |
|
764 // } else { |
|
765 // return (*flow)[e]; |
|
766 // } |
|
767 // } |
|
768 |
|
769 // bool direction(const Edge& edge) const { |
|
770 // return Parent::getGraph().direction(edge); |
|
771 // } |
|
772 |
|
773 // Edge direct(const UndirEdge& edge, bool direction) const { |
|
774 // return Parent::getGraph().direct(edge, direction); |
|
775 // } |
|
776 |
|
777 // Edge direct(const UndirEdge& edge, const Node& node) const { |
|
778 // return Parent::getGraph().direct(edge, node); |
|
779 // } |
|
780 |
|
781 // Edge oppositeEdge(const Edge& edge) const { |
|
782 // return Parent::getGraph().oppositeEdge(edge); |
|
783 // } |
|
784 |
|
785 // /// \brief Residual capacity map. |
|
786 // /// |
|
787 // /// In generic residual graphs the residual capacity can be obtained |
|
788 // /// as a map. |
|
789 // class ResCap { |
|
790 // protected: |
|
791 // const ResGraphAdaptor* res_graph; |
|
792 // public: |
|
793 // typedef Number Value; |
|
794 // typedef Edge Key; |
|
795 // ResCap(const ResGraphAdaptor& _res_graph) |
|
796 // : res_graph(&_res_graph) {} |
|
797 // Number operator[](const Edge& e) const { |
|
798 // return res_graph->resCap(e); |
|
799 // } |
|
800 // }; |
|
801 // }; |
|
802 |
|
803 } |
|
804 |
|
805 #endif |