COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/sub_graph.h @ 1979:c2992fd74dad

Last change on this file since 1979:c2992fd74dad was 1979:c2992fd74dad, checked in by Balazs Dezso, 14 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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
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
279      virtual void add(const std::vector<Node>& nodes) {
280        Parent::add(nodes);
281        for (int i = 0; i < (int)nodes.size(); ++i) {
282          Parent::operator[](nodes[i]).prev = nodes[i];
283          Parent::operator[](nodes[i]).firstIn = INVALID;
284          Parent::operator[](nodes[i]).firstOut = INVALID;
285        }
286      }
287
288      virtual void erase(const Node& node) {
289        adaptor.hide(node);
290        Parent::erase(node);
291      }
292
293      virtual void erase(const std::vector<Node>& nodes) {
294        for (int i = 0; i < (int)nodes.size(); ++i) {
295          adaptor.hide(nodes[i]);
296        }
297        Parent::erase(nodes);
298      }
299
300    private:
301      SubGraph& adaptor;
302    };
303
304    struct EdgeT {
305      Edge prevOut, nextOut;
306      Edge prevIn, nextIn;
307    };
308    class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
309      friend class SubGraphBase;
310    public:
311      typedef typename Graph::template EdgeMap<EdgeT> Parent;
312
313      EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
314        : Parent(_graph), adaptor(_adaptor) {}
315
316      virtual ~EdgesImpl() {}
317
318      virtual void build() {
319        Parent::build();
320        Edge edge;
321        adaptor.Base::first(edge);
322        while (edge != INVALID) {
323          Parent::operator[](edge).prevOut = edge;
324          adaptor.Base::next(edge);
325        }
326      }
327
328      virtual void clear() {
329        Node node;
330        adaptor.first(node);
331        while (node != INVALID) {
332          (*adaptor.nodes).firstIn = INVALID;
333          (*adaptor.nodes).firstOut = INVALID;
334          adaptor.next(node);
335        }
336        Parent::clear();
337      }
338
339      virtual void add(const Edge& edge) {
340        Parent::add(edge);
341        Parent::operator[](edge).prevOut = edge;
342      }
343
344      virtual void add(const std::vector<Edge>& edges) {
345        Parent::add(edges);
346        for (int i = 0; i < (int)edges.size(); ++i) {
347          Parent::operator[](edges[i]).prevOut = edges[i];
348        }
349      }
350
351      virtual void erase(const Edge& edge) {
352        adaptor.hide(edge);
353        Parent::erase(edge);
354      }
355
356      virtual void erase(const std::vector<Edge>& edges) {
357        for (int i = 0; i < (int)edges.size(); ++i) {
358          adaptor.hide(edges[i]);
359        }
360        Parent::erase(edges);
361      }
362
363    private:
364      SubGraph& adaptor;
365    };
366
367    NodesImpl* nodes;
368    EdgesImpl* edges;
369    Node firstNode;
370  };
371
372  /// \ingroup semi_adaptors
373  ///
374  /// \brief Graph which uses a subset of an other graph's nodes and edges.
375  ///
376  /// Graph which uses a subset of an other graph's nodes and edges. This class
377  /// is an alternative to the SubGraphAdaptor which is created for the
378  /// same reason. The main difference between the two class that it
379  /// makes linked lists on the unhidden nodes and edges what cause that
380  /// on sparse subgraphs the algorithms can be more efficient and some times
381  /// provide better time complexity. On other way this implemetation is
382  /// less efficient in most case when the subgraph filters out only
383  /// a few nodes or edges.
384  ///
385  /// \see SubGraphAdaptor
386  /// \see EdgeSubGraphBase
387  template <typename Graph>
388  class SubGraph
389    : public GraphAdaptorExtender< SubGraphBase<Graph> > {
390  public:
391    typedef GraphAdaptorExtender< SubGraphBase<Graph> > Parent;
392  public:
393    /// \brief Constructor for sub-graph.
394    ///
395    /// Constructor for sub-graph. Initially all the edges and nodes
396    /// are hidden in the graph.
397    SubGraph(const Graph& _graph)
398      : Parent(), nodes(*this, _graph), edges(*this, _graph) {
399      Parent::construct(_graph, nodes, edges);
400    }
401  private:
402    typename Parent::NodesImpl nodes;
403    typename Parent::EdgesImpl edges;
404  };
405
406  /// \brief Base for the EdgeSubGraph.
407  ///
408  /// Base for the EdgeSubGraph.
409  template <typename _Graph>
410  class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
411  public:
412    typedef _Graph Graph;
413    typedef EdgeSubGraphBase<_Graph> SubGraph;
414    typedef GraphAdaptorBase<const _Graph> Parent;
415    typedef Parent Base;
416
417    typedef typename Parent::Node Node;
418    typedef typename Parent::Edge Edge;
419
420
421  protected:
422
423    class NodesImpl;
424    class EdgesImpl;
425
426    EdgeSubGraphBase() {}
427
428    void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
429      Parent::setGraph(_graph);
430      nodes = &_nodes;
431      edges = &_edges;
432
433      Node node;
434      Parent::first(node);
435      while (node != INVALID) {
436        (*nodes)[node].firstIn = INVALID;
437        (*nodes)[node].firstOut = INVALID;
438        Parent::next(node);
439      }
440
441      Edge edge;
442      Parent::first(edge);
443      while (edge != INVALID) {
444        (*edges)[edge].prevOut = edge;
445        Parent::next(edge);
446      }
447    }
448
449  public:
450
451    void first(Node& node) const {
452      Parent::first(node);
453    }
454    void next(Node& node) const {
455      Parent::next(node);
456    }
457
458    void first(Edge& edge) const {
459      Node node;
460      Parent::first(node);
461      while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
462        Parent::next(node);
463      }
464      if (node == INVALID) {
465        edge = INVALID;
466      } else {
467        edge = (*nodes)[node].firstOut;
468      }
469    }
470    void next(Edge& edge) const {
471      if ((*edges)[edge].nextOut != INVALID) {
472        edge = (*edges)[edge].nextOut;
473      } else {
474        Node node = source(edge);
475        Parent::next(node);
476        while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
477          Parent::next(node);
478        }
479        if (node == INVALID) {
480          edge = INVALID;
481        } else {
482          edge = (*nodes)[node].firstOut;
483        }
484      }
485    }
486
487    void firstOut(Edge& edge, const Node& node) const {
488      edge = (*nodes)[node].firstOut;
489    }
490    void nextOut(Edge& edge) const {
491      edge = (*edges)[edge].nextOut;
492    }
493
494    void firstIn(Edge& edge, const Node& node) const {
495      edge = (*nodes)[node].firstIn;
496    }
497    void nextIn(Edge& edge) const {
498      edge = (*edges)[edge].nextIn;
499    }
500
501    /// \brief Returns true when the given edge is hidden.
502    ///
503    /// Returns true when the given edge is hidden.
504    bool hidden(const Edge& edge) const {
505      return (*edges)[edge].prevOut == edge;
506    }
507
508    /// \brief Hide the given edge in the sub-graph.
509    ///
510    /// Hide the given edge in the sub graph. It just lace out from
511    /// the linked lists the given edge.
512    void hide(const Edge& edge) {
513      if (hidden(edge)) return;
514      if ((*edges)[edge].prevOut != INVALID) {
515        (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
516      } else {
517        (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
518      }
519      if ((*edges)[edge].nextOut != INVALID) {
520        (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
521      }
522
523      if ((*edges)[edge].prevIn != INVALID) {
524        (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
525      } else {
526        (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
527      }
528      if ((*edges)[edge].nextIn != INVALID) {
529        (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
530      }
531      (*edges)[edge].prevOut = edge;
532    }
533
534    /// \brief Unhide the given edge in the sub-graph.
535    ///
536    /// Unhide the given edge in the sub graph. It just lace in the given
537    /// edge into the linked lists.
538    void unHide(const Edge& edge) {
539      if (!hidden(edge)) return;
540      Node node;
541
542      node = Parent::source(edge);
543      (*edges)[edge].nextOut = (*nodes)[node].firstOut;
544      (*edges)[edge].prevOut = INVALID;
545      if ((*edges)[edge].nextOut != INVALID) {
546        (*edges)[(*edges)[edge].nextOut].prevOut = edge;
547      }
548      (*nodes)[node].firstOut = edge;
549
550      node = Parent::target(edge);
551      (*edges)[edge].nextIn = (*nodes)[node].firstIn;
552      (*edges)[edge].prevIn = INVALID;
553      if ((*edges)[edge].nextIn != INVALID) {
554        (*edges)[(*edges)[edge].nextIn].prevIn = edge;
555      }
556      (*nodes)[node].firstIn = edge;     
557    }
558   
559  protected:
560    struct NodeT {
561      Edge firstIn, firstOut;
562    };
563    class NodesImpl : public Graph::template NodeMap<NodeT> {
564      friend class EdgeSubGraphBase;
565    public:
566      typedef typename Graph::template NodeMap<NodeT> Parent;
567
568      NodesImpl(SubGraph& _adaptor, const Graph& _graph)
569        : Parent(_graph), adaptor(_adaptor) {}
570
571      virtual ~NodesImpl() {}
572
573      virtual void build() {
574        Parent::build();
575        Node node;
576        adaptor.Base::first(node);
577        while (node != INVALID) {
578          Parent::operator[](node).firstIn = INVALID;
579          Parent::operator[](node).firstOut = INVALID;
580          adaptor.Base::next(node);
581        }
582      }
583
584      virtual void add(const Node& node) {
585        Parent::add(node);
586        Parent::operator[](node).firstIn = INVALID;
587        Parent::operator[](node).firstOut = INVALID;
588      }
589
590      virtual void add(const std::vector<Node>& nodes) {
591        Parent::add(nodes);
592        for (int i = 0; i < (int)nodes.size(); ++i) {
593          Parent::operator[](nodes[i]).firstIn = INVALID;
594          Parent::operator[](nodes[i]).firstOut = INVALID;
595        }
596      }
597
598    private:
599      SubGraph& adaptor;
600    };
601
602    struct EdgeT {
603      Edge prevOut, nextOut;
604      Edge prevIn, nextIn;
605    };
606    class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
607      friend class EdgeSubGraphBase;
608    public:
609      typedef typename Graph::template EdgeMap<EdgeT> Parent;
610
611      EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
612        : Parent(_graph), adaptor(_adaptor) {}
613
614      virtual ~EdgesImpl() {}
615
616      virtual void build() {
617        Parent::build();
618        Edge edge;
619        adaptor.Base::first(edge);
620        while (edge != INVALID) {
621          Parent::operator[](edge).prevOut = edge;
622          adaptor.Base::next(edge);
623        }
624      }
625
626      virtual void clear() {
627        Node node;
628        adaptor.Base::first(node);
629        while (node != INVALID) {
630          (*adaptor.nodes)[node].firstIn = INVALID;
631          (*adaptor.nodes)[node].firstOut = INVALID;
632          adaptor.Base::next(node);
633        }
634        Parent::clear();
635      }
636
637      virtual void add(const Edge& edge) {
638        Parent::add(edge);
639        Parent::operator[](edge).prevOut = edge;
640      }
641
642      virtual void add(const std::vector<Edge>& edges) {
643        Parent::add(edges);
644        for (int i = 0; i < (int)edges.size(); ++i) {
645          Parent::operator[](edges[i]).prevOut = edges[i];
646        }
647      }
648
649      virtual void erase(const Edge& edge) {
650        adaptor.hide(edge);
651        Parent::erase(edge);
652      }
653
654      virtual void erase(const std::vector<Edge>& edges) {
655        for (int i = 0; i < (int)edges.size(); ++i) {
656          adaptor.hide(edges[i]);
657        }
658        Parent::erase(edges);
659      }
660
661    private:
662      SubGraph& adaptor;
663    };
664
665    NodesImpl* nodes;
666    EdgesImpl* edges;
667  };
668
669  /// \ingroup semi_adaptors
670  ///
671  /// \brief Graph which uses a subset of an other graph's edges.
672  ///
673  /// Graph which uses a subset of an other graph's edges. This class
674  /// is an alternative to the EdgeSubGraphAdaptor which is created for the
675  /// same reason. The main difference between the two class that it
676  /// makes linked lists on the unhidden edges what cause that
677  /// on sparse subgraphs the algorithms can be more efficient and some times
678  /// provide better time complexity. On other way this implemetation is
679  /// less efficient in most case when the subgraph filters out only
680  /// a few edges.
681  ///
682  /// \see EdgeSubGraphAdaptor
683  /// \see EdgeSubGraphBase
684  template <typename Graph>
685  class EdgeSubGraph
686    : public GraphAdaptorExtender< EdgeSubGraphBase<Graph> > {
687  public:
688    typedef GraphAdaptorExtender< EdgeSubGraphBase<Graph> > Parent;
689  public:
690    /// \brief Constructor for sub-graph.
691    ///
692    /// Constructor for sub-graph. Initially all the edges are hidden in the
693    /// graph.
694    EdgeSubGraph(const Graph& _graph)
695      : Parent(), nodes(*this, _graph), edges(*this, _graph) {
696      Parent::construct(_graph, nodes, edges);
697    }
698  private:
699    typename Parent::NodesImpl nodes;
700    typename Parent::EdgesImpl edges;
701  };
702
703
704//   template<typename Graph, typename Number,
705//         typename CapacityMap, typename FlowMap>
706//   class ResGraph
707//     : public IterableGraphExtender<EdgeSubGraphBase<
708//     UGraphAdaptor<Graph> > > {
709//   public:
710//     typedef IterableGraphExtender<EdgeSubGraphBase<
711//       UGraphAdaptor<Graph> > > Parent;
712
713//   protected:
714//     UGraphAdaptor<Graph> u;
715
716//     const CapacityMap* capacity;
717//     FlowMap* flow;
718
719//     typename Parent::NodesImpl nodes;
720//     typename Parent::EdgesImpl edges;
721
722//     void setCapacityMap(const CapacityMap& _capacity) {
723//       capacity=&_capacity;
724//     }
725
726//     void setFlowMap(FlowMap& _flow) {
727//       flow=&_flow;
728//     }
729
730//   public:
731
732//     typedef typename UGraphAdaptor<Graph>::Node Node;
733//     typedef typename UGraphAdaptor<Graph>::Edge Edge;
734//     typedef typename UGraphAdaptor<Graph>::UEdge UEdge;
735
736//     ResGraphAdaptor(Graph& _graph,
737//                  const CapacityMap& _capacity, FlowMap& _flow)
738//       : Parent(), u(_graph), capacity(&_capacity), flow(&_flow),
739//      nodes(*this, _graph), edges(*this, _graph) {
740//       Parent::construct(u, nodes, edges);
741//       setFlowMap(_flow);
742//       setCapacityMap(_capacity);
743//       typename Graph::Edge edge;
744//       for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
745//      if ((*flow)[edge] != (*capacity)[edge]) {
746//        Parent::unHide(direct(edge, true));
747//      }
748//      if ((*flow)[edge] != 0) {
749//        Parent::unHide(direct(edge, false));
750//      }
751//       }
752//     }
753
754//     void augment(const Edge& e, Number a) {
755//       if (direction(e)) {
756//      flow->set(e, (*flow)[e]+a);
757//       } else {
758//      flow->set(e, (*flow)[e]-a);
759//       }
760//       if ((*flow)[e] == (*capacity)[e]) {
761//      Parent::hide(e);
762//       } else {
763//      Parent::unHide(e);
764//       }
765//       if ((*flow)[e] == 0) {
766//      Parent::hide(oppositeEdge(e));
767//       } else {
768//      Parent::unHide(oppositeEdge(e));
769//       }
770//     }
771
772//     Number resCap(const Edge& e) {
773//       if (direction(e)) {
774//      return (*capacity)[e]-(*flow)[e];
775//       } else {
776//      return (*flow)[e];
777//       }
778//     }
779   
780//     bool direction(const Edge& edge) const {
781//       return Parent::getGraph().direction(edge);
782//     }
783
784//     Edge direct(const UEdge& edge, bool direction) const {
785//       return Parent::getGraph().direct(edge, direction);
786//     }
787
788//     Edge direct(const UEdge& edge, const Node& node) const {
789//       return Parent::getGraph().direct(edge, node);
790//     }
791
792//     Edge oppositeEdge(const Edge& edge) const {
793//       return Parent::getGraph().oppositeEdge(edge);
794//     }
795
796//     /// \brief Residual capacity map.
797//     ///
798//     /// In generic residual graphs the residual capacity can be obtained
799//     /// as a map.
800//     class ResCap {
801//     protected:
802//       const ResGraphAdaptor* res_graph;
803//     public:
804//       typedef Number Value;
805//       typedef Edge Key;
806//       ResCap(const ResGraphAdaptor& _res_graph)
807//      : res_graph(&_res_graph) {}
808//       Number operator[](const Edge& e) const {
809//      return res_graph->resCap(e);
810//       }
811//     };
812//   };
813
814}
815
816#endif
Note: See TracBrowser for help on using the repository browser.