COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/sub_graph.h @ 2116:b6a68c15a6a3

Last change on this file since 2116:b6a68c15a6a3 was 2006:00d59f733817, checked in by Alpar Juttner, 14 years ago

Spellcheck

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 another graph's nodes and edges.
377  ///
378  /// Graph which uses a subset of another 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 another graph's edges.
674  ///
675  /// Graph which uses a subset of another 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.