COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/sub_graph.h @ 1990:15fb7a4ea6be

Last change on this file since 1990:15fb7a4ea6be was 1990:15fb7a4ea6be, checked in by Balazs Dezso, 14 years ago

Some classes assumed that the GraphMaps? should be inherited
from an ObserverBase?. These classes parents replaced with
DefaultMap? which cause that the graph maps should not be
inherited from the ObserverBase?.

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