COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/sub_graph.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

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