COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/sub_graph.h @ 1882:2c3f6c7e01b4

Last change on this file since 1882:2c3f6c7e01b4 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

File size: 21.4 KB
Line 
1/* -*- C++ -*-
2 * lemon/sub_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 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
22namespace 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
Note: See TracBrowser for help on using the repository browser.