COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/sub_graph.h @ 2224:f973894da54e

Last change on this file since 2224:f973894da54e was 2224:f973894da54e, checked in by Balazs Dezso, 18 years ago

Moving the file into correct group

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