COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 622:b66a28401f3f

Last change on this file since 622:b66a28401f3f was 622:b66a28401f3f, checked in by marci, 20 years ago
File size: 44.6 KB
RevLine 
[556]1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
4
5///\ingroup gwrappers
6///\file
7///\brief Several graph wrappers.
8///
9///This file contains several useful graph wrapper functions.
10///
11///\author Marton Makai
12
13#include <hugo/invalid.h>
14//#include <iter_map.h>
15
16namespace hugo {
17
18  // Graph wrappers
19
20  /// \addtogroup gwrappers
21  /// A main parts of HUGOlib are the different graph structures,
22  /// generic graph algorithms, graph concepts which couple these, and
23  /// graph wrappers. While the previous ones are more or less clear, the
24  /// latter notion needs further explanation.
25  /// Graph wrappers are graph classes which serve for considering graph
26  /// structures in different ways. A short example makes the notion much
27  /// clearer.
28  /// Suppose that we have an instance \c g of a directed graph
29  /// type say \c ListGraph and an algorithm
30  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
31  /// is needed to run on the reversely oriented graph.
32  /// It may be expensive (in time or in memory usage) to copy
33  /// \c g with the reverse orientation.
34  /// Thus, a wrapper class
35  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
36  /// The code looks as follows
37  /// \code
38  /// ListGraph g;
39  /// RevGraphWrapper<ListGraph> rgw(g);
40  /// int result=algorithm(rgw);
41  /// \endcode
42  /// After running the algorithm, the original graph \c g
43  /// remains untouched. Thus the graph wrapper used above is to consider the
44  /// original graph with reverse orientation.
45  /// This techniques gives rise to an elegant code, and
46  /// based on stable graph wrappers, complex algorithms can be
47  /// implemented easily.
48  /// In flow, circulation and bipartite matching problems, the residual
49  /// graph is of particular importance. Combining a wrapper implementing
50  /// this, shortest path algorithms and minimum mean cycle algorithms,
51  /// a range of weighted and cardinality optimization algorithms can be
52  /// obtained. For lack of space, for other examples,
53  /// the interested user is referred to the detailed documentation of graph
54  /// wrappers.
55  /// The behavior of graph wrappers can be very different. Some of them keep
56  /// capabilities of the original graph while in other cases this would be
57  /// meaningless. This means that the concepts that they are a model of depend
58  /// on the graph wrapper, and the wrapped graph(s).
59  /// If an edge of \c rgw is deleted, this is carried out by
60  /// deleting the corresponding edge of \c g. But for a residual
61  /// graph, this operation has no sense.
62  /// Let we stand one more example here to simplify your work.
63  /// wrapper class
64  /// \code template<typename Graph> class RevGraphWrapper; \endcode
65  /// has constructor
66  /// <tt> RevGraphWrapper(Graph& _g)</tt>.
67  /// This means that in a situation,
68  /// when a <tt> const ListGraph& </tt> reference to a graph is given,
69  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
70  /// \code
71  /// int algorithm1(const ListGraph& g) {
72  ///   RevGraphWrapper<const ListGraph> rgw(g);
73  ///   return algorithm2(rgw);
74  /// }
75  /// \endcode
76
77  /// \addtogroup gwrappers
78  /// @{
79
80  ///Base type for the Graph Wrappers
81
82  ///This is the base type for the Graph Wrappers.
83  ///\todo Some more docs...
84  ///
[612]85  ///\author Marton Makai
[556]86  template<typename Graph>
87  class GraphWrapper {
88  protected:
89    Graph* graph;
90    GraphWrapper() : graph(0) { }
91    void setGraph(Graph& _graph) { graph=&_graph; }
92
93  public:
94    typedef Graph BaseGraph;
95    typedef Graph ParentGraph;
96
97    GraphWrapper(Graph& _graph) : graph(&_graph) { }
98//     Graph& getGraph() const { return *graph; }
99 
100//    typedef typename Graph::Node Node;
101    class Node : public Graph::Node {
102      friend class GraphWrapper<Graph>;
103    public:
104      Node() { }
105      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
106      Node(const Invalid& i) : Graph::Node(i) { }
107    };
108    class NodeIt {
109      friend class GraphWrapper<Graph>;
110      typename Graph::NodeIt n;
111     public:
112      NodeIt() { }
113      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
114      NodeIt(const Invalid& i) : n(i) { }
115      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
116      operator Node() const { return Node(typename Graph::Node(n)); }
117    };
118//    typedef typename Graph::Edge Edge;
119    class Edge : public Graph::Edge {
120      friend class GraphWrapper<Graph>;
121    public:
122      Edge() { }
123      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
124      Edge(const Invalid& i) : Graph::Edge(i) { }
125    };
126    class OutEdgeIt {
127      friend class GraphWrapper<Graph>;
128      typename Graph::OutEdgeIt e;
129    public:
130      OutEdgeIt() { }
131      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
132      OutEdgeIt(const Invalid& i) : e(i) { }
133      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
134        e(*(_G.graph), typename Graph::Node(_n)) { }
135      operator Edge() const { return Edge(typename Graph::Edge(e)); }
136    };
137    class InEdgeIt {
138      friend class GraphWrapper<Graph>;
139      typename Graph::InEdgeIt e;
140    public:
141      InEdgeIt() { }
142      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
143      InEdgeIt(const Invalid& i) : e(i) { }
144      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
145        e(*(_G.graph), typename Graph::Node(_n)) { }
146      operator Edge() const { return Edge(typename Graph::Edge(e)); }
147    };
148    //typedef typename Graph::SymEdgeIt SymEdgeIt;
149    class EdgeIt {
150      friend class GraphWrapper<Graph>;
151      typename Graph::EdgeIt e;
152    public:
153      EdgeIt() { }
154      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
155      EdgeIt(const Invalid& i) : e(i) { }
156      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
157      operator Edge() const { return Edge(typename Graph::Edge(e)); }
158    };
159   
160    NodeIt& first(NodeIt& i) const {
161      i=NodeIt(*this); return i;
162    }
163    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
164      i=OutEdgeIt(*this, p); return i;
165    }
166    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
167      i=InEdgeIt(*this, p); return i;
168    }
169    EdgeIt& first(EdgeIt& i) const {
170      i=EdgeIt(*this); return i;
171    }
172
173    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
174    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
175    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
176    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
177
178    Node tail(const Edge& e) const {
179      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
180    Node head(const Edge& e) const {
181      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
182
183    bool valid(const Node& n) const {
184      return graph->valid(static_cast<typename Graph::Node>(n)); }
185    bool valid(const Edge& e) const {
186      return graph->valid(static_cast<typename Graph::Edge>(e)); }
187
188    int nodeNum() const { return graph->nodeNum(); }
189    int edgeNum() const { return graph->edgeNum(); }
190 
191    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
192    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
193    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
194    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
195 
196    Node addNode() const { return Node(graph->addNode()); }
197    Edge addEdge(const Node& tail, const Node& head) const {
198      return Edge(graph->addEdge(tail, head)); }
199
200    void erase(const Node& i) const { graph->erase(i); }
201    void erase(const Edge& i) const { graph->erase(i); }
202 
203    void clear() const { graph->clear(); }
204   
205    template<typename T> class NodeMap : public Graph::template NodeMap<T> {
206      typedef typename Graph::template NodeMap<T> Parent;
207    public:
208      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
209      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
210    };
211
212    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
213      typedef typename Graph::template EdgeMap<T> Parent;
214    public:
215      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
216      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
217    };
218  };
219
[569]220
221
[556]222  /// A graph wrapper which reverses the orientation of the edges.
223
224  /// A graph wrapper which reverses the orientation of the edges.
[612]225  /// Thus \c Graph have to be a directed graph type.
[556]226  ///
227  ///\author Marton Makai
228  template<typename Graph>
229  class RevGraphWrapper : public GraphWrapper<Graph> {
230  protected:
[612]231    RevGraphWrapper() : GraphWrapper<Graph>() { }
[556]232  public:
233    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
234
235    typedef typename GraphWrapper<Graph>::Node Node;
236    typedef typename GraphWrapper<Graph>::Edge Edge;
237    //If Graph::OutEdgeIt is not defined
238    //and we do not want to use RevGraphWrapper::InEdgeIt,
239    //the typdef techinque does not work.
240    //Unfortunately all the typedefs are instantiated in templates.
241    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
242    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
243
244    class OutEdgeIt {
245      friend class GraphWrapper<Graph>;
246      friend class RevGraphWrapper<Graph>;
247      typename Graph::InEdgeIt e;
248    public:
249      OutEdgeIt() { }
250      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
251      OutEdgeIt(const Invalid& i) : e(i) { }
252      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
253        e(*(_G.graph), typename Graph::Node(_n)) { }
254      operator Edge() const { return Edge(typename Graph::Edge(e)); }
255    };
256    class InEdgeIt {
257      friend class GraphWrapper<Graph>;
258      friend class RevGraphWrapper<Graph>;
259      typename Graph::OutEdgeIt e;
260    public:
261      InEdgeIt() { }
262      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
263      InEdgeIt(const Invalid& i) : e(i) { }
264      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
265        e(*(_G.graph), typename Graph::Node(_n)) { }
266      operator Edge() const { return Edge(typename Graph::Edge(e)); }
267    };
268
269    using GraphWrapper<Graph>::first;
270    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
271      i=OutEdgeIt(*this, p); return i;
272    }
273    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
274      i=InEdgeIt(*this, p); return i;
275    }
276
277    using GraphWrapper<Graph>::next;
278    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
279    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
280
281    Node aNode(const OutEdgeIt& e) const {
282      return Node(this->graph->aNode(e.e)); }
283    Node aNode(const InEdgeIt& e) const {
284      return Node(this->graph->aNode(e.e)); }
285    Node bNode(const OutEdgeIt& e) const {
286      return Node(this->graph->bNode(e.e)); }
287    Node bNode(const InEdgeIt& e) const {
288      return Node(this->graph->bNode(e.e)); }
289
290    Node tail(const Edge& e) const {
291      return GraphWrapper<Graph>::head(e); }
292    Node head(const Edge& e) const {
293      return GraphWrapper<Graph>::tail(e); }
294
295  };
296
[569]297
298
[612]299  /// A graph wrapper for hiding nodes and edges from a graph.
[556]300 
301  /// This wrapper shows a graph with filtered node-set and
302  /// edge-set. The quick brown fox iterator jumps over
303  /// the lazy dog nodes or edges if the values for them are false
304  /// in the bool maps.
305  ///
306  ///\author Marton Makai
307  template<typename Graph, typename NodeFilterMap,
308           typename EdgeFilterMap>
309  class SubGraphWrapper : public GraphWrapper<Graph> {
310  protected:
311    NodeFilterMap* node_filter_map;
312    EdgeFilterMap* edge_filter_map;
313
[612]314    SubGraphWrapper() : GraphWrapper<Graph>(),
[556]315                        node_filter_map(0), edge_filter_map(0) { }
316    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
317      node_filter_map=&_node_filter_map;
318    }
319    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
320      edge_filter_map=&_edge_filter_map;
321    }
322   
323  public:
324
325    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
326                    EdgeFilterMap& _edge_filter_map) :
327      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
328      edge_filter_map(&_edge_filter_map) { } 
329
330    typedef typename GraphWrapper<Graph>::Node Node;
331    class NodeIt {
332      friend class GraphWrapper<Graph>;
333      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
334      typename Graph::NodeIt n;
335     public:
336      NodeIt() { }
337      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
338      NodeIt(const Invalid& i) : n(i) { }
339      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
340        n(*(_G.graph)) {
341        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
342          _G.graph->next(n);
343      }
344      operator Node() const { return Node(typename Graph::Node(n)); }
345    };
346    typedef typename GraphWrapper<Graph>::Edge Edge;
347    class OutEdgeIt {
348      friend class GraphWrapper<Graph>;
349      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
350      typename Graph::OutEdgeIt e;
351    public:
352      OutEdgeIt() { }
353      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
354      OutEdgeIt(const Invalid& i) : e(i) { }
355      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
356                const Node& _n) :
357        e(*(_G.graph), typename Graph::Node(_n)) {
358        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
359          _G.graph->next(e);
360      }
361      operator Edge() const { return Edge(typename Graph::Edge(e)); }
362    };
363    class InEdgeIt {
364      friend class GraphWrapper<Graph>;
365      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
366      typename Graph::InEdgeIt e;
367    public:
368      InEdgeIt() { }
369      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
370      InEdgeIt(const Invalid& i) : e(i) { }
371      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
372               const Node& _n) :
373        e(*(_G.graph), typename Graph::Node(_n)) {
374        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
375          _G.graph->next(e);
376      }
377      operator Edge() const { return Edge(typename Graph::Edge(e)); }
378    };
379    //typedef typename Graph::SymEdgeIt SymEdgeIt;
380    class EdgeIt {
381      friend class GraphWrapper<Graph>;
382      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
383      typename Graph::EdgeIt e;
384    public:
385      EdgeIt() { }
386      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
387      EdgeIt(const Invalid& i) : e(i) { }
388      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
389        e(*(_G.graph)) {
390        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
391          _G.graph->next(e);
392      }
393      operator Edge() const { return Edge(typename Graph::Edge(e)); }
394    };
395
396    NodeIt& first(NodeIt& i) const {
397      i=NodeIt(*this); return i;
398    }
399    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
400      i=OutEdgeIt(*this, p); return i;
401    }
402    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
403      i=InEdgeIt(*this, p); return i;
404    }
405    EdgeIt& first(EdgeIt& i) const {
406      i=EdgeIt(*this); return i;
407    }
408   
409    NodeIt& next(NodeIt& i) const {
410      this->graph->next(i.n);
411      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
412        this->graph->next(i.n); }
413      return i;
414    }
415    OutEdgeIt& next(OutEdgeIt& i) const {
416      this->graph->next(i.e);
417      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
418        this->graph->next(i.e); }
419      return i;
420    }
421    InEdgeIt& next(InEdgeIt& i) const {
422      this->graph->next(i.e);
423      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
424        this->graph->next(i.e); }
425      return i;
426    }
427    EdgeIt& next(EdgeIt& i) const {
428      this->graph->next(i.e);
429      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
430        this->graph->next(i.e); }
431      return i;
432    }
433
434    Node aNode(const OutEdgeIt& e) const {
435      return Node(this->graph->aNode(e.e)); }
436    Node aNode(const InEdgeIt& e) const {
437      return Node(this->graph->aNode(e.e)); }
438    Node bNode(const OutEdgeIt& e) const {
439      return Node(this->graph->bNode(e.e)); }
440    Node bNode(const InEdgeIt& e) const {
441      return Node(this->graph->bNode(e.e)); }
442
[561]443    /// This function hides \c n in the graph, i.e. the iteration
444    /// jumps over it. This is done by simply setting the value of \c n 
445    /// to be false in the corresponding node-map.
[556]446    void hide(const Node& n) const { node_filter_map->set(n, false); }
[561]447
448    /// This function hides \c e in the graph, i.e. the iteration
449    /// jumps over it. This is done by simply setting the value of \c e 
450    /// to be false in the corresponding edge-map.
[556]451    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
452
[561]453    /// The value of \c n is set to be true in the node-map which stores
454    /// hide information. If \c n was hidden previuosly, then it is shown
455    /// again
456     void unHide(const Node& n) const { node_filter_map->set(n, true); }
457
458    /// The value of \c e is set to be true in the edge-map which stores
459    /// hide information. If \c e was hidden previuosly, then it is shown
460    /// again
[556]461    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
462
[561]463    /// Returns true if \c n is hidden.
464    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
465
466    /// Returns true if \c n is hidden.
467    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
[593]468
[594]469    /// This is a linear time operation and works only if
[593]470    /// NodeIt is defined.
471    int nodeNum() const {
472      int i=0;
473      NodeIt n;
474      for (this->first(n); this->valid(n); this->next(n)) ++i;
475      return i;
476    }
477
478    /// This is a linear time operation and works only if
479    /// EdgeIt is defined.
480    int edgeNum() const {
481      int i=0;
482      EdgeIt e;
483      for (this->first(e); this->valid(e); this->next(e)) ++i;
484      return i;
485    }
486
[556]487  };
488
[569]489
490
[612]491  /// \brief A wrapper for forgetting the orientation of a graph.
492  ///
[556]493  /// A wrapper for getting an undirected graph by forgetting
494  /// the orientation of a directed one.
[589]495  ///
[612]496  /// \author Marton Makai
[556]497  template<typename Graph>
498  class UndirGraphWrapper : public GraphWrapper<Graph> {
499  protected:
500    UndirGraphWrapper() : GraphWrapper<Graph>() { }
501   
502  public:
503    typedef typename GraphWrapper<Graph>::Node Node;
504    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
505    typedef typename GraphWrapper<Graph>::Edge Edge;
506    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
507
508    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
509
510    class OutEdgeIt {
511      friend class UndirGraphWrapper<Graph>;
512      bool out_or_in; //true iff out
513      typename Graph::OutEdgeIt out;
514      typename Graph::InEdgeIt in;
515    public:
516      OutEdgeIt() { }
517      OutEdgeIt(const Invalid& i) : Edge(i) { }
518      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
519        out_or_in=true; _G.graph->first(out, _n);
520        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
521      }
522      operator Edge() const {
523        if (out_or_in) return Edge(out); else return Edge(in);
524      }
525    };
526
527//FIXME InEdgeIt
528    typedef OutEdgeIt InEdgeIt;
529
530    using GraphWrapper<Graph>::first;
531//     NodeIt& first(NodeIt& i) const {
532//       i=NodeIt(*this); return i;
533//     }
534    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
535      i=OutEdgeIt(*this, p); return i;
536    }
537//FIXME
538//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
539//       i=InEdgeIt(*this, p); return i;
540//     }
541//     EdgeIt& first(EdgeIt& i) const {
542//       i=EdgeIt(*this); return i;
543//     }
544
545    using GraphWrapper<Graph>::next;
546//     NodeIt& next(NodeIt& n) const {
547//       GraphWrapper<Graph>::next(n);
548//       return n;
549//     }
550    OutEdgeIt& next(OutEdgeIt& e) const {
551      if (e.out_or_in) {
552        typename Graph::Node n=this->graph->tail(e.out);
553        this->graph->next(e.out);
554        if (!this->graph->valid(e.out)) {
555          e.out_or_in=false; this->graph->first(e.in, n); }
556      } else {
557        this->graph->next(e.in);
558      }
559      return e;
560    }
561    //FIXME InEdgeIt
562//     EdgeIt& next(EdgeIt& e) const {
563//       GraphWrapper<Graph>::next(n);
564// //      graph->next(e.e);
565//       return e;
566//     }
567
568    Node aNode(const OutEdgeIt& e) const {
569      if (e.out_or_in) return this->graph->tail(e); else
570        return this->graph->head(e); }
571    Node bNode(const OutEdgeIt& e) const {
572      if (e.out_or_in) return this->graph->head(e); else
573        return this->graph->tail(e); }
574  };
575 
[612]576  /// \brief An undirected graph template.
577  ///
578  /// An undirected graph template.
579  /// This class works as an undirected graph and a directed graph of
580  /// class \c Graph is used for the physical storage.
581  /// \ingroup graphs
[556]582  template<typename Graph>
583  class UndirGraph : public UndirGraphWrapper<Graph> {
584    typedef UndirGraphWrapper<Graph> Parent;
585  protected:
586    Graph gr;
587  public:
588    UndirGraph() : UndirGraphWrapper<Graph>() {
589      Parent::setGraph(gr);
590    }
591  };
592
[569]593
[612]594  ///\brief A wrapper for composing bidirected graph from a directed one.
595  /// experimental, for fezso's sake.
596  ///
[576]597  /// A wrapper for composing bidirected graph from a directed one.
598  /// experimental, for fezso's sake.
[612]599  /// A bidirected graph is composed over the directed one without physical
600  /// storage. As the oppositely directed edges are logically different ones
601  /// the maps are able to attach different values for them.
[569]602  template<typename Graph>
603  class BidirGraphWrapper : public GraphWrapper<Graph> {
604  protected:
605    //const CapacityMap* capacity;
606    //FlowMap* flow;
607
608    BidirGraphWrapper() : GraphWrapper<Graph>()/*,
609                                                 capacity(0), flow(0)*/ { }
610//     void setCapacityMap(const CapacityMap& _capacity) {
611//       capacity=&_capacity;
612//     }
613//     void setFlowMap(FlowMap& _flow) {
614//       flow=&_flow;
615//     }
616
617  public:
618
619    BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
620                                     FlowMap& _flow*/) :
621      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
622
623    class Edge;
624    class OutEdgeIt;
625    friend class Edge;
626    friend class OutEdgeIt;
627
[621]628    //template<typename T> class NodeMap;   
629    template<typename T> class EdgeMap;
630
[569]631    typedef typename GraphWrapper<Graph>::Node Node;
632    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
[621]633
[569]634    class Edge : public Graph::Edge {
635      friend class BidirGraphWrapper<Graph>;
[621]636      ///\bug ez nem is kell
637      //template<typename T> friend class NodeMap;
638      template<typename T> friend class EdgeMap;
[569]639    protected:
640      bool backward; //true, iff backward
641//      typename Graph::Edge e;
642    public:
643      Edge() { }
644      Edge(const typename Graph::Edge& _e, bool _backward) :
645        Graph::Edge(_e), backward(_backward) { }
646      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
647//the unique invalid iterator
648      friend bool operator==(const Edge& u, const Edge& v) {
649        return (v.backward==u.backward &&
650                static_cast<typename Graph::Edge>(u)==
651                static_cast<typename Graph::Edge>(v));
652      }
653      friend bool operator!=(const Edge& u, const Edge& v) {
654        return (v.backward!=u.backward ||
655                static_cast<typename Graph::Edge>(u)!=
656                static_cast<typename Graph::Edge>(v));
657      }
658    };
659
660    class OutEdgeIt {
661      friend class BidirGraphWrapper<Graph>;
662    protected:
663      typename Graph::OutEdgeIt out;
664      typename Graph::InEdgeIt in;
665      bool backward;
666    public:
667      OutEdgeIt() { }
668      //FIXME
669//      OutEdgeIt(const Edge& e) : Edge(e) { }
670      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
671//the unique invalid iterator
672      OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
673        backward=false;
674        _G.graph->first(out, v);
675        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
676        if (!_G.graph->valid(out)) {
677          backward=true;
678          _G.graph->first(in, v);
679          while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
680        }
681      }
682      operator Edge() const {
683//      Edge e;
684//      e.forward=this->forward;
685//      if (this->forward) e=out; else e=in;
686//      return e;
687        if (this->backward)
688          return Edge(in, this->backward);
689        else
690          return Edge(out, this->backward);
691      }
692    };
693
694    class InEdgeIt {
695      friend class BidirGraphWrapper<Graph>;
696    protected:
697      typename Graph::OutEdgeIt out;
698      typename Graph::InEdgeIt in;
699      bool backward;
700    public:
701      InEdgeIt() { }
702      //FIXME
703//      OutEdgeIt(const Edge& e) : Edge(e) { }
704      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
705//the unique invalid iterator
706      InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
707        backward=false;
708        _G.graph->first(in, v);
709        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
710        if (!_G.graph->valid(in)) {
711          backward=true;
712          _G.graph->first(out, v);
713          while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
714        }
715      }
716      operator Edge() const {
717//      Edge e;
718//      e.forward=this->forward;
719//      if (this->forward) e=out; else e=in;
720//      return e;
721        if (this->backward)
722          return Edge(out, this->backward);
723        else
724          return Edge(in, this->backward);
725      }
726    };
727
728    class EdgeIt {
729      friend class BidirGraphWrapper<Graph>;
730    protected:
731      typename Graph::EdgeIt e;
732      bool backward;
733    public:
734      EdgeIt() { }
735      EdgeIt(const Invalid& i) : e(i), backward(true) { }
736      EdgeIt(const BidirGraphWrapper<Graph>& _G) {
737        backward=false;
738        _G.graph->first(e);
739        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
740        if (!_G.graph->valid(e)) {
741          backward=true;
742          _G.graph->first(e);
743          while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
744        }
745      }
746      operator Edge() const {
747        return Edge(e, this->backward);
748      }
749    };
750
751    using GraphWrapper<Graph>::first;
752//     NodeIt& first(NodeIt& i) const {
753//       i=NodeIt(*this); return i;
754//     }
755    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
756      i=OutEdgeIt(*this, p); return i;
757    }
758//    FIXME not tested
759    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
760      i=InEdgeIt(*this, p); return i;
761    }
762    EdgeIt& first(EdgeIt& i) const {
763      i=EdgeIt(*this); return i;
764    }
[556]765 
[569]766    using GraphWrapper<Graph>::next;
767//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
768    OutEdgeIt& next(OutEdgeIt& e) const {
769      if (!e.backward) {
770        Node v=this->graph->aNode(e.out);
771        this->graph->next(e.out);
772        while(this->graph->valid(e.out) && !enabled(e)) {
773          this->graph->next(e.out); }
774        if (!this->graph->valid(e.out)) {
775          e.backward=true;
776          this->graph->first(e.in, v);
777          while(this->graph->valid(e.in) && !enabled(e)) {
778            this->graph->next(e.in); }
779        }
780      } else {
781        this->graph->next(e.in);
782        while(this->graph->valid(e.in) && !enabled(e)) {
783          this->graph->next(e.in); }
784      }
785      return e;
786    }
787//     FIXME Not tested
788    InEdgeIt& next(InEdgeIt& e) const {
789      if (!e.backward) {
790        Node v=this->graph->aNode(e.in);
791        this->graph->next(e.in);
792        while(this->graph->valid(e.in) && !enabled(e)) {
793          this->graph->next(e.in); }
794        if (!this->graph->valid(e.in)) {
795          e.backward=true;
796          this->graph->first(e.out, v);
797          while(this->graph->valid(e.out) && !enabled(e)) {
798            this->graph->next(e.out); }
799        }
800      } else {
801        this->graph->next(e.out);
802        while(this->graph->valid(e.out) && !enabled(e)) {
803          this->graph->next(e.out); }
804      }
805      return e;
806    }
807    EdgeIt& next(EdgeIt& e) const {
808      if (!e.backward) {
809        this->graph->next(e.e);
810        while(this->graph->valid(e.e) && !enabled(e)) {
811          this->graph->next(e.e); }
812        if (!this->graph->valid(e.e)) {
813          e.backward=true;
814          this->graph->first(e.e);
815          while(this->graph->valid(e.e) && !enabled(e)) {
816            this->graph->next(e.e); }
817        }
818      } else {
819        this->graph->next(e.e);
820        while(this->graph->valid(e.e) && !enabled(e)) {
821          this->graph->next(e.e); }
822      }
823      return e;
824    }
825
826    Node tail(Edge e) const {
827      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
828    Node head(Edge e) const {
829      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
830
831    Node aNode(OutEdgeIt e) const {
832      return ((!e.backward) ? this->graph->aNode(e.out) :
833              this->graph->aNode(e.in)); }
834    Node bNode(OutEdgeIt e) const {
835      return ((!e.backward) ? this->graph->bNode(e.out) :
836              this->graph->bNode(e.in)); }
837
838    Node aNode(InEdgeIt e) const {
839      return ((!e.backward) ? this->graph->aNode(e.in) :
840              this->graph->aNode(e.out)); }
841    Node bNode(InEdgeIt e) const {
842      return ((!e.backward) ? this->graph->bNode(e.in) :
843              this->graph->bNode(e.out)); }
844
[572]845    /// Gives back the opposite edge.
846    Edge opposite(const Edge& e) const {
847      Edge f=e;
848      f.backward=!f.backward;
849      return f;
850    }
851
[569]852//    int nodeNum() const { return graph->nodeNum(); }
853    //FIXME
854    void edgeNum() const { }
855    //int edgeNum() const { return graph->edgeNum(); }
856
857
858//    int id(Node v) const { return graph->id(v); }
859
860    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
861    bool valid(Edge e) const {
862      return this->graph->valid(e);
863        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
864    }
865
866    bool forward(const Edge& e) const { return !e.backward; }
867    bool backward(const Edge& e) const { return e.backward; }
868
869//     void augment(const Edge& e, Number a) const {
870//       if (!e.backward) 
871// //   flow->set(e.out, flow->get(e.out)+a);
872//      flow->set(e, (*flow)[e]+a);
873//       else 
874// //   flow->set(e.in, flow->get(e.in)-a);
875//      flow->set(e, (*flow)[e]-a);
876//     }
877
878    bool enabled(const Edge& e) const {
879      if (!e.backward)
880//      return (capacity->get(e.out)-flow->get(e.out));
881        //return ((*capacity)[e]-(*flow)[e]);
882        return true;
883      else
884//      return (flow->get(e.in));
885        //return ((*flow)[e]);
886        return true;
887    }
888
889//     Number enabled(typename Graph::OutEdgeIt out) const {
890// //      return (capacity->get(out)-flow->get(out));
891//       return ((*capacity)[out]-(*flow)[out]);
892//     }
893   
894//     Number enabled(typename Graph::InEdgeIt in) const {
895// //      return (flow->get(in));
896//       return ((*flow)[in]);
897//     }
898
899    template <typename T>
900    class EdgeMap {
901      typename Graph::template EdgeMap<T> forward_map, backward_map;
902    public:
903      EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
904      EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
905      void set(Edge e, T a) {
906        if (!e.backward)
[622]907          forward_map.set(e/*.out*/, a);
[569]908        else
[622]909          backward_map.set(e/*.in*/, a);
[569]910      }
911      T operator[](Edge e) const {
912        if (!e.backward)
[622]913          return forward_map[e/*.out*/];
[569]914        else
[622]915          return backward_map[e/*.in*/];
[569]916      }
917//       T get(Edge e) const {
918//      if (e.out_or_in)
919//        return forward_map.get(e.out);
920//      else
921//        return backward_map.get(e.in);
922//       }
923    };
924  };
925
[612]926  /// \brief A bidirected graph template.
927  ///
928  /// A bidirected graph template.
929  /// Such a bidirected graph stores each pair of oppositely directed edges
930  /// ones in the memory, i.e. a directed graph of type
931  /// \c Graph is used for that.
932  /// As the oppositely directed edges are logically different ones
933  /// the maps are able to attach different values for them.
934  /// \ingroup graphs
935  template<typename Graph>
936  class BidirGraph : public BidirGraphWrapper<Graph> {
937    typedef UndirGraphWrapper<Graph> Parent;
938  protected:
939    Graph gr;
940  public:
941    BidirGraph() : BidirGraphWrapper<Graph>() {
942      Parent::setGraph(gr);
943    }
944  };
[569]945
[556]946
947  /// A wrapper for composing the residual graph for directed flow and circulation problems.
948
949  /// A wrapper for composing the residual graph for directed flow and circulation problems.
950  template<typename Graph, typename Number,
951           typename CapacityMap, typename FlowMap>
952  class ResGraphWrapper : public GraphWrapper<Graph> {
953  protected:
954    const CapacityMap* capacity;
955    FlowMap* flow;
956
957    ResGraphWrapper() : GraphWrapper<Graph>(0),
958                        capacity(0), flow(0) { }
[560]959    void setCapacityMap(const CapacityMap& _capacity) {
960      capacity=&_capacity;
[556]961    }
962    void setFlowMap(FlowMap& _flow) {
963      flow=&_flow;
964    }
965
966  public:
967
968    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
969                    FlowMap& _flow) :
970      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
971
972    class Edge;
973    class OutEdgeIt;
974    friend class Edge;
975    friend class OutEdgeIt;
976
977    typedef typename GraphWrapper<Graph>::Node Node;
978    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
979    class Edge : public Graph::Edge {
980      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
981    protected:
[565]982      bool backward; //true, iff backward
[556]983//      typename Graph::Edge e;
984    public:
985      Edge() { }
[565]986      Edge(const typename Graph::Edge& _e, bool _backward) :
987        Graph::Edge(_e), backward(_backward) { }
988      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
[556]989//the unique invalid iterator
990      friend bool operator==(const Edge& u, const Edge& v) {
[565]991        return (v.backward==u.backward &&
[556]992                static_cast<typename Graph::Edge>(u)==
993                static_cast<typename Graph::Edge>(v));
994      }
995      friend bool operator!=(const Edge& u, const Edge& v) {
[565]996        return (v.backward!=u.backward ||
[556]997                static_cast<typename Graph::Edge>(u)!=
998                static_cast<typename Graph::Edge>(v));
999      }
1000    };
1001
1002    class OutEdgeIt {
1003      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1004    protected:
1005      typename Graph::OutEdgeIt out;
1006      typename Graph::InEdgeIt in;
[565]1007      bool backward;
[556]1008    public:
1009      OutEdgeIt() { }
1010      //FIXME
1011//      OutEdgeIt(const Edge& e) : Edge(e) { }
[565]1012      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
[556]1013//the unique invalid iterator
[569]1014      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
[565]1015        backward=false;
[569]1016        _G.graph->first(out, v);
1017        while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1018        if (!_G.graph->valid(out)) {
[565]1019          backward=true;
[569]1020          _G.graph->first(in, v);
1021          while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
[556]1022        }
1023      }
1024      operator Edge() const {
1025//      Edge e;
1026//      e.forward=this->forward;
1027//      if (this->forward) e=out; else e=in;
1028//      return e;
[565]1029        if (this->backward)
1030          return Edge(in, this->backward);
[556]1031        else
[565]1032          return Edge(out, this->backward);
[556]1033      }
1034    };
1035
1036    class InEdgeIt {
1037      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1038    protected:
1039      typename Graph::OutEdgeIt out;
1040      typename Graph::InEdgeIt in;
[565]1041      bool backward;
[556]1042    public:
1043      InEdgeIt() { }
1044      //FIXME
1045//      OutEdgeIt(const Edge& e) : Edge(e) { }
[565]1046      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
[556]1047//the unique invalid iterator
[569]1048      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
[565]1049        backward=false;
[569]1050        _G.graph->first(in, v);
1051        while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1052        if (!_G.graph->valid(in)) {
[565]1053          backward=true;
[569]1054          _G.graph->first(out, v);
1055          while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
[556]1056        }
1057      }
1058      operator Edge() const {
1059//      Edge e;
1060//      e.forward=this->forward;
1061//      if (this->forward) e=out; else e=in;
1062//      return e;
[565]1063        if (this->backward)
1064          return Edge(out, this->backward);
[556]1065        else
[565]1066          return Edge(in, this->backward);
[556]1067      }
1068    };
1069
1070    class EdgeIt {
1071      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1072    protected:
1073      typename Graph::EdgeIt e;
[565]1074      bool backward;
[556]1075    public:
1076      EdgeIt() { }
[565]1077      EdgeIt(const Invalid& i) : e(i), backward(true) { }
[569]1078      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
[565]1079        backward=false;
[569]1080        _G.graph->first(e);
1081        while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1082        if (!_G.graph->valid(e)) {
[565]1083          backward=true;
[569]1084          _G.graph->first(e);
1085          while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
[556]1086        }
1087      }
1088      operator Edge() const {
[565]1089        return Edge(e, this->backward);
[556]1090      }
1091    };
1092
1093    using GraphWrapper<Graph>::first;
1094//     NodeIt& first(NodeIt& i) const {
1095//       i=NodeIt(*this); return i;
1096//     }
1097    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1098      i=OutEdgeIt(*this, p); return i;
1099    }
1100//    FIXME not tested
1101    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1102      i=InEdgeIt(*this, p); return i;
1103    }
1104    EdgeIt& first(EdgeIt& i) const {
1105      i=EdgeIt(*this); return i;
1106    }
1107 
1108    using GraphWrapper<Graph>::next;
1109//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1110    OutEdgeIt& next(OutEdgeIt& e) const {
[565]1111      if (!e.backward) {
[556]1112        Node v=this->graph->aNode(e.out);
1113        this->graph->next(e.out);
1114        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1115          this->graph->next(e.out); }
1116        if (!this->graph->valid(e.out)) {
[565]1117          e.backward=true;
[556]1118          this->graph->first(e.in, v);
1119          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1120            this->graph->next(e.in); }
1121        }
1122      } else {
1123        this->graph->next(e.in);
1124        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1125          this->graph->next(e.in); }
1126      }
1127      return e;
1128    }
1129//     FIXME Not tested
1130    InEdgeIt& next(InEdgeIt& e) const {
[565]1131      if (!e.backward) {
[556]1132        Node v=this->graph->aNode(e.in);
1133        this->graph->next(e.in);
1134        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1135          this->graph->next(e.in); }
1136        if (!this->graph->valid(e.in)) {
[565]1137          e.backward=true;
[556]1138          this->graph->first(e.out, v);
1139          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1140            this->graph->next(e.out); }
1141        }
1142      } else {
1143        this->graph->next(e.out);
1144        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1145          this->graph->next(e.out); }
1146      }
1147      return e;
1148    }
1149    EdgeIt& next(EdgeIt& e) const {
[565]1150      if (!e.backward) {
[556]1151        this->graph->next(e.e);
1152        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1153          this->graph->next(e.e); }
1154        if (!this->graph->valid(e.e)) {
[565]1155          e.backward=true;
[556]1156          this->graph->first(e.e);
1157          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1158            this->graph->next(e.e); }
1159        }
1160      } else {
1161        this->graph->next(e.e);
1162        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1163          this->graph->next(e.e); }
1164      }
1165      return e;
1166    }
1167
1168    Node tail(Edge e) const {
[565]1169      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
[556]1170    Node head(Edge e) const {
[565]1171      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
[556]1172
1173    Node aNode(OutEdgeIt e) const {
[565]1174      return ((!e.backward) ? this->graph->aNode(e.out) :
[556]1175              this->graph->aNode(e.in)); }
1176    Node bNode(OutEdgeIt e) const {
[565]1177      return ((!e.backward) ? this->graph->bNode(e.out) :
[556]1178              this->graph->bNode(e.in)); }
1179
1180    Node aNode(InEdgeIt e) const {
[565]1181      return ((!e.backward) ? this->graph->aNode(e.in) :
[556]1182              this->graph->aNode(e.out)); }
1183    Node bNode(InEdgeIt e) const {
[565]1184      return ((!e.backward) ? this->graph->bNode(e.in) :
[556]1185              this->graph->bNode(e.out)); }
1186
1187//    int nodeNum() const { return graph->nodeNum(); }
1188    //FIXME
1189    void edgeNum() const { }
1190    //int edgeNum() const { return graph->edgeNum(); }
1191
1192
1193//    int id(Node v) const { return graph->id(v); }
1194
1195    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1196    bool valid(Edge e) const {
1197      return this->graph->valid(e);
1198        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1199    }
1200
[565]1201    bool forward(const Edge& e) const { return !e.backward; }
1202    bool backward(const Edge& e) const { return e.backward; }
[556]1203
1204    void augment(const Edge& e, Number a) const {
[565]1205      if (!e.backward) 
[556]1206//      flow->set(e.out, flow->get(e.out)+a);
1207        flow->set(e, (*flow)[e]+a);
1208      else 
1209//      flow->set(e.in, flow->get(e.in)-a);
1210        flow->set(e, (*flow)[e]-a);
1211    }
1212
1213    Number resCap(const Edge& e) const {
[565]1214      if (!e.backward)
[556]1215//      return (capacity->get(e.out)-flow->get(e.out));
1216        return ((*capacity)[e]-(*flow)[e]);
1217      else
1218//      return (flow->get(e.in));
1219        return ((*flow)[e]);
1220    }
1221
1222//     Number resCap(typename Graph::OutEdgeIt out) const {
1223// //      return (capacity->get(out)-flow->get(out));
1224//       return ((*capacity)[out]-(*flow)[out]);
1225//     }
1226   
1227//     Number resCap(typename Graph::InEdgeIt in) const {
1228// //      return (flow->get(in));
1229//       return ((*flow)[in]);
1230//     }
1231
1232    template <typename T>
1233    class EdgeMap {
1234      typename Graph::template EdgeMap<T> forward_map, backward_map;
1235    public:
1236      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1237      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1238      void set(Edge e, T a) {
[565]1239        if (!e.backward)
[556]1240          forward_map.set(e.out, a);
1241        else
1242          backward_map.set(e.in, a);
1243      }
1244      T operator[](Edge e) const {
[565]1245        if (!e.backward)
[556]1246          return forward_map[e.out];
1247        else
1248          return backward_map[e.in];
1249      }
1250//       T get(Edge e) const {
1251//      if (e.out_or_in)
1252//        return forward_map.get(e.out);
1253//      else
1254//        return backward_map.get(e.in);
1255//       }
1256    };
1257  };
1258
[569]1259
1260
[612]1261  /// For blocking flows.
[556]1262
[612]1263  /// This graph wrapper is used for Dinits blocking flow computations.
1264  /// For each node, an out-edge is stored which is used when the
1265  /// \code
1266  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1267  /// \endcode
1268  /// is called.
[556]1269  ///
1270  ///\author Marton Makai
1271  template<typename Graph, typename FirstOutEdgesMap>
1272  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1273  protected:
1274    FirstOutEdgesMap* first_out_edges;
1275  public:
1276    ErasingFirstGraphWrapper(Graph& _graph,
1277                             FirstOutEdgesMap& _first_out_edges) :
1278      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1279
1280    typedef typename GraphWrapper<Graph>::Node Node;
1281//     class NodeIt {
1282//       friend class GraphWrapper<Graph>;
1283//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1284//       typename Graph::NodeIt n;
1285//      public:
1286//       NodeIt() { }
1287//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1288//       NodeIt(const Invalid& i) : n(i) { }
1289//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1290//      n(*(_G.graph)) { }
1291//       operator Node() const { return Node(typename Graph::Node(n)); }
1292//     };
1293    typedef typename GraphWrapper<Graph>::Edge Edge;
1294    class OutEdgeIt {
1295      friend class GraphWrapper<Graph>;
1296      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1297//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1298      typename Graph::OutEdgeIt e;
1299    public:
1300      OutEdgeIt() { }
1301      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1302      OutEdgeIt(const Invalid& i) : e(i) { }
1303      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1304                const Node& _n) :
1305        e((*_G.first_out_edges)[_n]) { }
1306      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1307    };
1308    class InEdgeIt {
1309      friend class GraphWrapper<Graph>;
1310      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1311//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
1312      typename Graph::InEdgeIt e;
1313    public:
1314      InEdgeIt() { }
1315      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1316      InEdgeIt(const Invalid& i) : e(i) { }
1317      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1318               const Node& _n) :
1319        e(*(_G.graph), typename Graph::Node(_n)) { }
1320      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1321    };
1322    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1323    class EdgeIt {
1324      friend class GraphWrapper<Graph>;
1325      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1326//      typedef typename Graph::EdgeIt GraphEdgeIt;
1327      typename Graph::EdgeIt e;
1328    public:
1329      EdgeIt() { }
1330      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1331      EdgeIt(const Invalid& i) : e(i) { }
1332      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1333        e(*(_G.graph)) { }
1334      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1335    };
1336
1337    using GraphWrapper<Graph>::first;
1338//     NodeIt& first(NodeIt& i) const {
1339//       i=NodeIt(*this); return i;
1340//     }
1341    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1342      i=OutEdgeIt(*this, p); return i;
1343    }
1344    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1345      i=InEdgeIt(*this, p); return i;
1346    }
1347    EdgeIt& first(EdgeIt& i) const {
1348      i=EdgeIt(*this); return i;
1349    }
1350
1351    using GraphWrapper<Graph>::next;
1352//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1353    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1354    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1355    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
1356   
1357    Node aNode(const OutEdgeIt& e) const {
1358      return Node(this->graph->aNode(e.e)); }
1359    Node aNode(const InEdgeIt& e) const {
1360      return Node(this->graph->aNode(e.e)); }
1361    Node bNode(const OutEdgeIt& e) const {
1362      return Node(this->graph->bNode(e.e)); }
1363    Node bNode(const InEdgeIt& e) const {
1364      return Node(this->graph->bNode(e.e)); }
1365
1366    void erase(const OutEdgeIt& e) const {
1367      OutEdgeIt f=e;
1368      this->next(f);
1369      first_out_edges->set(this->tail(e), f.e);
1370    }
1371  };
1372
1373  ///@}
1374
1375} //namespace hugo
1376
1377#endif //HUGO_GRAPH_WRAPPER_H
1378
Note: See TracBrowser for help on using the repository browser.