COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 335:999eb3cd7b49

Last change on this file since 335:999eb3cd7b49 was 335:999eb3cd7b49, checked in by marci, 17 years ago

jflsjfljskf

File size: 73.8 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
4
5#include <invalid.h>
6
7namespace hugo {
8
9  /// Graph wrappers
10
11  /// The main parts of HUGOlib are the different graph structures,
12  /// generic graph algorithms, graph concepts which couple these, and
13  /// graph wrappers. While the previous ones are more or less clear, the
14  /// latter notion needs further explanation.
15  /// Graph wrappers are graph classes which serve for considering graph
16  /// structures in different ways. A short example makes the notion much more
17  /// clear.
18  /// Suppose that we have an instance \code g \endcode of a directed graph
19  /// type say \code ListGraph \endcode and an algorithm
20  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
21  /// is needed to run on the reversed oriented graph.
22  /// It can be expensive (in time or in memory usage) to copy
23  /// \code g \endcode with the reversed orientation.
24  /// Thus, a wrapper class
25  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
26  /// The code looks as follows
27  /// \code
28  /// ListGraph g;
29  /// RevGraphWrapper<ListGraph> rgw(g);
30  /// int result=algorithm(rgw);
31  /// \endcode
32  /// After running the algorithm, the original graph \code g \endcode
33  /// is untouched. Thus the above used graph wrapper is to consider the
34  /// original graph with reversed orientation.
35  /// This techniques gives rise to an elegant code, and
36  /// based on stable graph wrappers, complex algorithms can be
37  /// implemented easily.
38  /// In flow, circulation and bipartite matching problems, the residual
39  /// graph is of particualar significance. Combining a wrapper impleneting
40  /// this, shortest path algorithms and mimimum mean cycle algorithms,
41  /// a range of weighted and cardinality optimization algorithms can be
42  /// obtained. For lack of space, for other examples,
43  /// the interested user is referred to the detailed domumentation of graph
44  /// wrappers.
45  /// The behavior of graph wrappers are very different. Some of them keep
46  /// capabilities of the original graph while in other cases this would be
47  /// meaningless. This means that the concepts that they are model of depend
48  /// on the graph wrapper, and the wrapped graph(s).
49  /// If an edge of \code rgw \endcode is deleted, this is carried out by
50  /// deleting the corresponding edge of \code g \endcode. But for a residual
51  /// graph, this operation has no sense.
52  /// Let we stand one more example here to simplify your work.
53  /// wrapper class
54  /// \code template<typename Graph> class RevGraphWrapper; \endcode
55  /// has constructor
56  /// \code RevGraphWrapper(Graph& _g); \endcode.
57  /// This means that in a situation,
58  /// when a \code const ListGraph& \endcode reference to a graph is given,
59  /// then it have to be instatiated with Graph=const ListGraph.
60  /// \code
61  /// int algorithm1(const ListGraph& g) {
62  ///   RevGraphWrapper<const ListGraph> rgw(g);
63  ///   return algorithm2(rgw);
64  /// }
65  /// \endcode
66  template<typename Graph>
67  class GraphWrapper {
68  protected:
69    Graph* graph;
70 
71  public:
72    typedef Graph BaseGraph;
73    typedef Graph ParentGraph;
74
75//     GraphWrapper() : graph(0) { }
76    GraphWrapper(Graph& _graph) : graph(&_graph) { }
77//     void setGraph(Graph& _graph) { graph=&_graph; }
78//     Graph& getGraph() const { return *graph; }
79 
80//    typedef typename Graph::Node Node;
81    class Node : public Graph::Node {
82      friend class GraphWrapper<Graph>;
83    public:
84      Node() { }
85      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
86      Node(const Invalid& i) : Graph::Node(i) { }
87    };
88    class NodeIt {
89      friend class GraphWrapper<Graph>;
90      typename Graph::NodeIt n;
91     public:
92      NodeIt() { }
93      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
94      NodeIt(const Invalid& i) : n(i) { }
95      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
96      operator Node() const { return Node(typename Graph::Node(n)); }
97    };
98//    typedef typename Graph::Edge Edge;
99    class Edge : public Graph::Edge {
100      friend class GraphWrapper<Graph>;
101    public:
102      Edge() { }
103      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
104      Edge(const Invalid& i) : Graph::Edge(i) { }
105    };
106    class OutEdgeIt {
107      friend class GraphWrapper<Graph>;
108//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
109      typename Graph::OutEdgeIt e;
110    public:
111      OutEdgeIt() { }
112      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
113      OutEdgeIt(const Invalid& i) : e(i) { }
114      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
115        e(*(_G.graph), typename Graph::Node(_n)) { }
116      operator Edge() const { return Edge(typename Graph::Edge(e)); }
117    };
118    class InEdgeIt {
119      friend class GraphWrapper<Graph>;
120//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
121      typename Graph::InEdgeIt e;
122    public:
123      InEdgeIt() { }
124      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
125      InEdgeIt(const Invalid& i) : e(i) { }
126      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
127        e(*(_G.graph), typename Graph::Node(_n)) { }
128      operator Edge() const { return Edge(typename Graph::Edge(e)); }
129    };
130    //typedef typename Graph::SymEdgeIt SymEdgeIt;
131    class EdgeIt {
132      friend class GraphWrapper<Graph>;
133//      typedef typename Graph::EdgeIt GraphEdgeIt;
134      typename Graph::EdgeIt e;
135    public:
136      EdgeIt() { }
137      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
138      EdgeIt(const Invalid& i) : e(i) { }
139      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
140      operator Edge() const { return Edge(typename Graph::Edge(e)); }
141    };
142   
143    NodeIt& first(NodeIt& i) const {
144      i=NodeIt(*this); return i;
145    }
146    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
147      i=OutEdgeIt(*this, p); return i;
148    }
149    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
150      i=InEdgeIt(*this, p); return i;
151    }
152    EdgeIt& first(EdgeIt& i) const {
153      i=EdgeIt(*this); return i;
154    }
155//     template<typename I> I& first(I& i) const {       
156//       i=I(*this);
157//       return i;
158//     }
159//     template<typename I, typename P> I& first(I& i, const P& p) const {
160//       i=I(*this, p);
161//       return i;
162//     }
163   
164    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
165    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
166    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
167    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
168//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
169//     template< typename It > It first() const {
170//       It e; this->first(e); return e; }
171
172//     template< typename It > It first(const Node& v) const {
173//       It e; this->first(e, v); return e; }
174
175    Node head(const Edge& e) const {
176      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
177    Node tail(const Edge& e) const {
178      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
179
180    bool valid(const Node& n) const {
181      return graph->valid(static_cast<typename Graph::Node>(n)); }
182    bool valid(const Edge& e) const {
183      return graph->valid(static_cast<typename Graph::Edge>(e)); }
184//    template<typename I> bool valid(const I& i) const {
185//      return graph->valid(i); }
186 
187    //template<typename I> void setInvalid(const I &i);
188    //{ return graph->setInvalid(i); }
189
190    int nodeNum() const { return graph->nodeNum(); }
191    int edgeNum() const { return graph->edgeNum(); }
192 
193    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
194    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
195    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
196    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
197//     template<typename I> Node aNode(const I& e) const {
198//       return Node(graph->aNode(e.e)); }
199//     template<typename I> Node bNode(const I& e) const {
200//       return Node(graph->bNode(e.e)); }
201 
202    Node addNode() const { return Node(graph->addNode()); }
203    Edge addEdge(const Node& tail, const Node& head) const {
204      return Edge(graph->addEdge(tail, head)); }
205
206    void erase(const Node& i) const { graph->erase(i); }
207    void erase(const Edge& i) const { graph->erase(i); }
208//    template<typename I> void erase(const I& i) const { graph->erase(i); }
209 
210    void clear() const { graph->clear(); }
211   
212    template<typename T> class NodeMap : public Graph::NodeMap<T> {
213    public:
214      NodeMap(const GraphWrapper<Graph>& _G) : 
215        Graph::NodeMap<T>(*(_G.graph)) { }
216      NodeMap(const GraphWrapper<Graph>& _G, T a) :
217        Graph::NodeMap<T>(*(_G.graph), a) { }
218    };
219
220    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
221    public:
222      EdgeMap(const GraphWrapper<Graph>& _G) : 
223        Graph::EdgeMap<T>(*(_G.graph)) { }
224      EdgeMap(const GraphWrapper<Graph>& _G, T a) :
225        Graph::EdgeMap<T>(*(_G.graph), a) { }
226    };
227  };
228
229
230//   template<typename Graph>
231//   class RevGraphWrapper
232//   {
233//   protected:
234//     Graph* graph;
235 
236//   public:
237//     typedef Graph ParentGraph;
238
239//     typedef typename Graph::Node Node;   
240//     typedef typename Graph::NodeIt NodeIt;
241 
242//     typedef typename Graph::Edge Edge;
243//     typedef typename Graph::OutEdgeIt InEdgeIt;
244//     typedef typename Graph::InEdgeIt OutEdgeIt;
245//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
246//     typedef typename Graph::EdgeIt EdgeIt;
247
248//     //RevGraphWrapper() : graph(0) { }
249//     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
250
251//     void setGraph(Graph& _graph) { graph = &_graph; }
252//     Graph& getGraph() const { return (*graph); }
253   
254//     template<typename I> I& first(I& i) const { return graph->first(i); }
255//     template<typename I, typename P> I& first(I& i, const P& p) const {
256//       return graph->first(i, p); }
257
258//     template<typename I> I& next(I &i) const { return graph->next(i); }   
259
260//     template< typename It > It first() const {
261//       It e; first(e); return e; }
262
263//     template< typename It > It first(const Node& v) const {
264//       It e; first(e, v); return e; }
265
266//     Node head(const Edge& e) const { return graph->tail(e); }
267//     Node tail(const Edge& e) const { return graph->head(e); }
268 
269//     template<typename I> bool valid(const I& i) const
270//       { return graph->valid(i); }
271 
272//     //template<typename I> void setInvalid(const I &i);
273//     //{ return graph->setInvalid(i); }
274 
275//     template<typename I> Node aNode(const I& e) const {
276//       return graph->aNode(e); }
277//     template<typename I> Node bNode(const I& e) const {
278//       return graph->bNode(e); }
279
280//     Node addNode() const { return graph->addNode(); }
281//     Edge addEdge(const Node& tail, const Node& head) const {
282//       return graph->addEdge(tail, head); }
283 
284//     int nodeNum() const { return graph->nodeNum(); }
285//     int edgeNum() const { return graph->edgeNum(); }
286 
287//     template<typename I> void erase(const I& i) const { graph->erase(i); }
288 
289//     void clear() const { graph->clear(); }
290
291//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
292//     public:
293//       NodeMap(const RevGraphWrapper<Graph>& _G) :
294//      Graph::NodeMap<T>(_G.getGraph()) { }
295//       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
296//      Graph::NodeMap<T>(_G.getGraph(), a) { }
297//     };
298
299//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
300//     public:
301//       EdgeMap(const RevGraphWrapper<Graph>& _G) :
302//      Graph::EdgeMap<T>(_G.getGraph()) { }
303//       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
304//      Graph::EdgeMap<T>(_G.getGraph(), a) { }
305//     };
306//   };
307
308
309  template<typename Graph>
310  class RevGraphWrapper : public GraphWrapper<Graph> {
311  public:
312    typedef typename GraphWrapper<Graph>::Node Node;
313    typedef typename GraphWrapper<Graph>::Edge Edge;
314    //FIXME
315    //If Graph::OutEdgeIt is not defined
316    //and we do not want to use RevGraphWrapper::InEdgeIt,
317    //this won't work, because of typedef
318    //OR
319    //graphs have to define their non-existing iterators to void
320    //Unfortunately all the typedefs are instantiated in templates,
321    //unlike other stuff
322    typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
323    typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
324
325//     RevGraphWrapper() : GraphWrapper<Graph>() { }
326    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
327
328    Node head(const Edge& e) const
329      { return GraphWrapper<Graph>::tail(e); }
330    Node tail(const Edge& e) const
331      { return GraphWrapper<Graph>::head(e); }
332  };
333
334  /// Wrapper for hiding nodes and edges from a graph.
335 
336  /// This wrapper shows a graph with filtered node-set and
337  /// edge-set. The quick brown fox iterators jumps over
338  /// the lazy dog nodes or edges if the values for them are false
339  /// in the bool maps.
340  template<typename Graph, typename NodeFilterMap,
341           typename EdgeFilterMap>
342  class SubGraphWrapper : public GraphWrapper<Graph> {
343  protected:
344    NodeFilterMap* node_filter_map;
345    EdgeFilterMap* edge_filter_map;
346  public:
347//     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
348    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
349                    EdgeFilterMap& _edge_filter_map) :
350      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
351      edge_filter_map(&_edge_filter_map) { } 
352
353    typedef typename GraphWrapper<Graph>::Node Node;
354    class NodeIt {
355      friend class GraphWrapper<Graph>;
356      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
357      typename Graph::NodeIt n;
358     public:
359      NodeIt() { }
360      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
361      NodeIt(const Invalid& i) : n(i) { }
362      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
363        n(*(_G.graph)) {
364        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
365          _G.graph->next(n);
366      }
367      operator Node() const { return Node(typename Graph::Node(n)); }
368    };
369//     class NodeIt : public Graph::NodeIt {
370// //      typedef typename Graph::NodeIt GraphNodeIt;
371//     public:
372//       NodeIt() { }
373//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
374//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
375//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
376//      Graph::NodeIt(*(_G.graph)) {
377//      while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
378//             !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
379//        _G.graph->next((*this)/*.GraphNodeIt*/);
380//       }
381//     };
382    typedef typename GraphWrapper<Graph>::Edge Edge;
383    class OutEdgeIt {
384      friend class GraphWrapper<Graph>;
385      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
386//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
387      typename Graph::OutEdgeIt e;
388    public:
389      OutEdgeIt() { }
390      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
391      OutEdgeIt(const Invalid& i) : e(i) { }
392      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
393                const Node& _n) :
394        e(*(_G.graph), typename Graph::Node(_n)) {
395        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
396          _G.graph->next(e);
397      }
398      operator Edge() const { return Edge(typename Graph::Edge(e)); }
399    };
400    class InEdgeIt {
401      friend class GraphWrapper<Graph>;
402      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
403//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
404      typename Graph::InEdgeIt e;
405    public:
406      InEdgeIt() { }
407      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
408      InEdgeIt(const Invalid& i) : e(i) { }
409      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
410               const Node& _n) :
411        e(*(_G.graph), typename Graph::Node(_n)) {
412        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
413          _G.graph->next(e);
414      }
415      operator Edge() const { return Edge(typename Graph::Edge(e)); }
416    };
417    //typedef typename Graph::SymEdgeIt SymEdgeIt;
418    class EdgeIt {
419      friend class GraphWrapper<Graph>;
420      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
421//      typedef typename Graph::EdgeIt GraphEdgeIt;
422      typename Graph::EdgeIt e;
423    public:
424      EdgeIt() { }
425      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
426      EdgeIt(const Invalid& i) : e(i) { }
427      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
428        e(*(_G.graph)) {
429        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
430          _G.graph->next(e);
431      }
432      operator Edge() const { return Edge(typename Graph::Edge(e)); }
433    };
434//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
435//     };
436//     class OutEdgeIt : public Graph::OutEdgeIt {
437// //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
438//     public:
439//       OutEdgeIt() { }
440//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
441//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
442//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
443//              _G, const Node& n) :
444//      Graph::OutEdgeIt(*(_G.graph), n) {
445//      while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
446//             !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
447//        _G.graph->next((*this)/*.GraphOutEdgeIt*/);
448//       }
449//     };
450//     class InEdgeIt : public Graph::InEdgeIt {
451// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
452//     public:
453//       InEdgeIt() { }
454//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
455//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
456//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
457//             const Node& n) :
458//      Graph::InEdgeIt(*(_G.graph), n) {
459//      while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
460//             !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
461//        _G.graph->next((*this)/*.GraphInEdgeIt*/);
462//       }
463//     };
464// //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
465//     class EdgeIt : public Graph::EdgeIt {
466// //      typedef typename Graph::EdgeIt GraphEdgeIt;
467//     public:
468//       EdgeIt() { }
469//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
470//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
471//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
472//      Graph::EdgeIt(*(_G.graph)) {
473//      while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
474//             !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
475//        _G.graph->next((*this)/*.GraphEdgeIt*/);
476//       }
477//     };
478   
479
480    NodeIt& first(NodeIt& i) const {
481      i=NodeIt(*this); return i;
482    }
483    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
484      i=OutEdgeIt(*this, p); return i;
485    }
486    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
487      i=InEdgeIt(*this, p); return i;
488    }
489    EdgeIt& first(EdgeIt& i) const {
490      i=EdgeIt(*this); return i;
491    }
492   
493//     template<typename I> I& first(I& i) const {
494//       graph->first(i);
495//       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
496//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
497//       return i;
498//     }
499//     template<typename I, typename P> I& first(I& i, const P& p) const {
500//       graph->first(i, p);
501// //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
502//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
503//       return i;
504//     }
505
506    NodeIt& next(NodeIt& i) const {
507      graph->next(i.n);
508      while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
509      return i;
510    }
511    OutEdgeIt& next(OutEdgeIt& i) const {
512      graph->next(i.e);
513      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
514      return i;
515    }
516    InEdgeIt& next(InEdgeIt& i) const {
517      graph->next(i.e);
518      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
519      return i;
520    }
521    EdgeIt& next(EdgeIt& i) const {
522      graph->next(i.e);
523      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
524      return i;
525    }
526
527//     template<typename I> I& next(I &i) const {
528//       graph->next(i);
529// //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
530//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
531//       return i;
532//     }
533
534    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
535    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
536    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
537    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
538
539    void hide(const Node& n) const { node_filter_map->set(n, false); }
540    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
541
542    void unHide(const Node& n) const { node_filter_map->set(n, true); }
543    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
544
545    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
546    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
547
548//     template< typename It > It first() const {
549//       It e; this->first(e); return e; }
550   
551//     template< typename It > It first(const Node& v) const {
552//       It e; this->first(e, v); return e; }
553  };
554
555//   //Subgraph on the same node-set and partial edge-set
556//   template<typename Graph, typename NodeFilterMap,
557//         typename EdgeFilterMap>
558//   class SubGraphWrapper : public GraphWrapper<Graph> {
559//   protected:
560//     NodeFilterMap* node_filter_map;
561//     EdgeFilterMap* edge_filter_map;
562//   public:
563// //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
564//     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
565//                  EdgeFilterMap& _edge_filter_map) :
566//       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
567//       edge_filter_map(&_edge_filter_map) { } 
568
569
570//     typedef typename Graph::Node Node;
571//     class NodeIt : public Graph::NodeIt {
572// //      typedef typename Graph::NodeIt GraphNodeIt;
573//     public:
574//       NodeIt() { }
575//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
576//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
577//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
578//      Graph::NodeIt(*(_G.graph)) {
579//      while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
580//             !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
581//        _G.graph->next((*this)/*.GraphNodeIt*/);
582//       }
583//     };
584//     typedef typename Graph::Edge Edge;
585//     class OutEdgeIt : public Graph::OutEdgeIt {
586// //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
587//     public:
588//       OutEdgeIt() { }
589//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
590//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
591//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
592//              _G, const Node& n) :
593//      Graph::OutEdgeIt(*(_G.graph), n) {
594//      while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
595//             !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
596//        _G.graph->next((*this)/*.GraphOutEdgeIt*/);
597//       }
598//     };
599//     class InEdgeIt : public Graph::InEdgeIt {
600// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
601//     public:
602//       InEdgeIt() { }
603//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
604//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
605//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
606//             const Node& n) :
607//      Graph::InEdgeIt(*(_G.graph), n) {
608//      while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
609//             !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
610//        _G.graph->next((*this)/*.GraphInEdgeIt*/);
611//       }
612//     };
613// //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
614//     class EdgeIt : public Graph::EdgeIt {
615// //      typedef typename Graph::EdgeIt GraphEdgeIt;
616//     public:
617//       EdgeIt() { }
618//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
619//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
620//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
621//      Graph::EdgeIt(*(_G.graph)) {
622//      while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
623//             !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
624//        _G.graph->next((*this)/*.GraphEdgeIt*/);
625//       }
626//     };
627   
628//     NodeIt& first(NodeIt& i) const {
629//       i=NodeIt(*this);
630//       return i;
631//     }
632//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
633//       i=OutEdgeIt(*this, n);
634//       return i;
635//     }
636//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
637//       i=InEdgeIt(*this, n);
638//       return i;
639//     }
640//     EdgeIt& first(EdgeIt& i) const {
641//       i=EdgeIt(*this);
642//       return i;
643//     }
644   
645// //     template<typename I> I& first(I& i) const {
646// //       graph->first(i);
647// //       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
648// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
649// //       return i;
650// //     }
651// //     template<typename I, typename P> I& first(I& i, const P& p) const {
652// //       graph->first(i, p);
653// // //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
654// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
655// //       return i;
656// //     }
657
658//     NodeIt& next(NodeIt& i) const {
659//       graph->next(i);
660//       while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
661//       return i;
662//     }
663//     OutEdgeIt& next(OutEdgeIt& i) const {
664//       graph->next(i);
665//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
666//       return i;
667//     }
668//     InEdgeIt& next(InEdgeIt& i) const {
669//       graph->next(i);
670//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
671//       return i;
672//     }
673//     EdgeIt& next(EdgeIt& i) const {
674//       graph->next(i);
675//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
676//       return i;
677//     }
678
679// //     template<typename I> I& next(I &i) const {
680// //       graph->next(i);
681// // //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
682// //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
683// //       return i;
684// //     }
685   
686//     template< typename It > It first() const {
687//       It e; this->first(e); return e; }
688   
689//     template< typename It > It first(const Node& v) const {
690//       It e; this->first(e, v); return e; }
691//   };
692
693  template<typename Graph>
694  class UndirGraphWrapper : public GraphWrapper<Graph> {
695//  protected:
696//    typedef typename Graph::Edge GraphEdge;
697//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
698//    typedef typename Graph::InEdgeIt GraphInEdgeIt;   
699  public:
700    typedef typename GraphWrapper<Graph>::Node Node;
701    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
702    typedef typename GraphWrapper<Graph>::Edge Edge;
703    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
704
705//     UndirGraphWrapper() : GraphWrapper<Graph>() { }
706    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
707
708   
709//     class Edge {
710//       friend class UndirGraphWrapper<Graph>;
711//     protected:
712//       bool out_or_in; //true iff out
713//       GraphOutEdgeIt out;
714//       GraphInEdgeIt in;
715//     public:
716//       Edge() : out_or_in(), out(), in() { }
717//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
718//       operator GraphEdge() const {
719//      if (out_or_in) return(out); else return(in);
720//       }
721// //FIXME
722// //2 edges are equal if they "refer" to the same physical edge
723// //is it good?
724//       friend bool operator==(const Edge& u, const Edge& v) {
725//      if (v.out_or_in)
726//        if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
727//      //return (u.out_or_in && u.out==v.out);
728//      else
729//        if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
730//      //return (!u.out_or_in && u.in==v.in);
731//       }
732//       friend bool operator!=(const Edge& u, const Edge& v) {
733//      if (v.out_or_in)
734//        if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
735//      //return (!u.out_or_in || u.out!=v.out);
736//      else
737//        if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
738//      //return (u.out_or_in || u.in!=v.in);
739//       }
740//     };
741
742    class OutEdgeIt {
743      friend class UndirGraphWrapper<Graph>;
744      bool out_or_in; //true iff out
745      typename Graph::OutEdgeIt out;
746      typename Graph::InEdgeIt in;
747    public:
748      OutEdgeIt() { }
749      OutEdgeIt(const Invalid& i) : Edge(i) { }
750      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
751        out_or_in=true; _G.graph->first(out, _n);
752        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
753      }
754      operator Edge() const {
755        if (out_or_in) return Edge(out); else return Edge(in);
756      }
757    };
758//     class OutEdgeIt : public Edge {
759//       friend class UndirGraphWrapper<Graph>;
760//     public:
761//       OutEdgeIt() : Edge() { }
762//       OutEdgeIt(const Invalid& i) : Edge(i) { }
763//       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
764//      : Edge() {
765//      out_or_in=true; _G.graph->first(out, n);
766//      if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
767//       }
768//     };
769
770//FIXME InEdgeIt
771    typedef OutEdgeIt InEdgeIt;
772
773//     class EdgeIt : public Edge {
774//       friend class UndirGraphWrapper<Graph>;
775//     protected:
776//       NodeIt v;
777//     public:
778//       EdgeIt() : Edge() { }
779//       EdgeIt(const Invalid& i) : Edge(i) { }
780//       EdgeIt(const UndirGraphWrapper<Graph>& _G)
781//      : Edge() {
782//      out_or_in=true;
783//      //Node v;
784//      _G.first(v);
785//      if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
786//      while (_G.valid(v) && !_G.graph->valid(out)) {
787//        _G.graph->next(v);
788//        if (_G.valid(v)) _G.graph->first(out);
789//      }
790//       }
791//     };
792
793    NodeIt& first(NodeIt& i) const {
794      i=NodeIt(*this); return i;
795    }
796    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
797      i=OutEdgeIt(*this, p); return i;
798    }
799//FIXME
800//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
801//       i=InEdgeIt(*this, p); return i;
802//     }
803    EdgeIt& first(EdgeIt& i) const {
804      i=EdgeIt(*this); return i;
805    }
806
807//     template<typename I> I& first(I& i) const { graph->first(i); return i; }
808//     template<typename I, typename P> I& first(I& i, const P& p) const {
809//       graph->first(i, p); return i; }
810
811    NodeIt& next(NodeIt& n) const {
812      GraphWrapper<Graph>::next(n);
813      return n;
814    }
815    OutEdgeIt& next(OutEdgeIt& e) const {
816      if (e.out_or_in) {
817        typename Graph::Node n=graph->tail(e.out);
818        graph->next(e.out);
819        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
820      } else {
821        graph->next(e.in);
822      }
823      return e;
824    }
825    //FIXME InEdgeIt
826    EdgeIt& next(EdgeIt& e) const {
827      GraphWrapper<Graph>::next(n);
828//      graph->next(e.e);
829      return e;
830    }
831
832//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
833//     template< typename It > It first() const {
834//       It e; this->first(e); return e; }
835
836//     template< typename It > It first(const Node& v) const {
837//       It e; this->first(e, v); return e; }
838
839//    Node head(const Edge& e) const { return gw.head(e); }
840//    Node tail(const Edge& e) const { return gw.tail(e); }
841
842//    template<typename I> bool valid(const I& i) const
843//      { return gw.valid(i); }
844 
845//    int nodeNum() const { return gw.nodeNum(); }
846//    int edgeNum() const { return gw.edgeNum(); }
847 
848//     template<typename I> Node aNode(const I& e) const {
849//       return graph->aNode(e); }
850//     template<typename I> Node bNode(const I& e) const {
851//       return graph->bNode(e); }
852
853    Node aNode(const OutEdgeIt& e) const {
854      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
855    Node bNode(const OutEdgeIt& e) const {
856      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
857 
858//    Node addNode() const { return gw.addNode(); }
859
860// FIXME: ez igy nem jo, mert nem
861//    Edge addEdge(const Node& tail, const Node& head) const {
862//      return graph->addEdge(tail, head); }
863 
864//    template<typename I> void erase(const I& i) const { gw.erase(i); }
865 
866//    void clear() const { gw.clear(); }
867   
868//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
869//     public:
870//       NodeMap(const UndirGraphWrapper<Graph>& _G) :
871//      Graph::NodeMap<T>(_G.gw) { }
872//       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
873//      Graph::NodeMap<T>(_G.gw, a) { }
874//     };
875
876//     template<typename T> class EdgeMap :
877//       public GraphWrapperSkeleton<Graph>::EdgeMap<T> {
878//     public:
879//       EdgeMap(const UndirGraphWrapper<Graph>& _G) :
880//      GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }
881//       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
882//      Graph::EdgeMap<T>(_G.gw, a) { }
883//     };
884   };
885
886
887
888
889
890//   template<typename Graph>
891//   class SymGraphWrapper
892//   {
893//     Graph* graph;
894 
895//   public:
896//     typedef Graph ParentGraph;
897
898//     typedef typename Graph::Node Node;
899//     typedef typename Graph::Edge Edge;
900 
901//     typedef typename Graph::NodeIt NodeIt;
902   
903//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
904//     //iranyitatlant, ami van
905//     //mert csak 1 dolgot lehet be typedef-elni
906//     typedef typename Graph::OutEdgeIt SymEdgeIt;
907//     //typedef typename Graph::InEdgeIt SymEdgeIt;
908//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
909//     typedef typename Graph::EdgeIt EdgeIt;
910
911//     int nodeNum() const { return graph->nodeNum(); }
912//     int edgeNum() const { return graph->edgeNum(); }
913   
914//     template<typename I> I& first(I& i) const { return graph->first(i); }
915//     template<typename I, typename P> I& first(I& i, const P& p) const {
916//       return graph->first(i, p); }
917//     //template<typename I> I next(const I i); { return graph->goNext(i); }
918//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
919
920//     template< typename It > It first() const {
921//       It e; first(e); return e; }
922
923//     template< typename It > It first(Node v) const {
924//       It e; first(e, v); return e; }
925
926//     Node head(const Edge& e) const { return graph->head(e); }
927//     Node tail(const Edge& e) const { return graph->tail(e); }
928 
929//     template<typename I> Node aNode(const I& e) const {
930//       return graph->aNode(e); }
931//     template<typename I> Node bNode(const I& e) const {
932//       return graph->bNode(e); }
933 
934//     //template<typename I> bool valid(const I i);
935//     //{ return graph->valid(i); }
936 
937//     //template<typename I> void setInvalid(const I &i);
938//     //{ return graph->setInvalid(i); }
939 
940//     Node addNode() { return graph->addNode(); }
941//     Edge addEdge(const Node& tail, const Node& head) {
942//       return graph->addEdge(tail, head); }
943 
944//     template<typename I> void erase(const I& i) { graph->erase(i); }
945 
946//     void clear() { graph->clear(); }
947 
948//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
949//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
950 
951//     void setGraph(Graph& _graph) { graph = &_graph; }
952//     Graph& getGraph() { return (*graph); }
953
954//     //SymGraphWrapper() : graph(0) { }
955//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
956//   };
957
958
959 
960
961  template<typename Graph, typename Number,
962           typename CapacityMap, typename FlowMap>
963  class ResGraphWrapper : public GraphWrapper<Graph> {
964  protected:
965//    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
966//    typedef typename Graph::InEdgeIt GraphInEdgeIt;
967//    typedef typename Graph::Edge GraphEdge;
968    const CapacityMap* capacity;
969    FlowMap* flow;
970  public:
971
972    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
973                    FlowMap& _flow) :
974      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
975
976    class Edge;
977    class OutEdgeIt;
978    friend class Edge;
979    friend class OutEdgeIt;
980
981    typedef typename GraphWrapper<Graph>::Node Node;
982    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
983    class Edge : public Graph::Edge {
984      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
985    protected:
986      bool forward; //true, iff forward
987//      typename Graph::Edge e;
988    public:
989      Edge() { }
990      Edge(const typename Graph::Edge& _e, bool _forward) :
991        Graph::Edge(_e), forward(_forward) { }
992      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
993//the unique invalid iterator
994      friend bool operator==(const Edge& u, const Edge& v) {
995        return (v.forward==u.forward &&
996                static_cast<typename Graph::Edge>(u)==
997                static_cast<typename Graph::Edge>(v));
998      }
999      friend bool operator!=(const Edge& u, const Edge& v) {
1000        return (v.forward!=u.forward ||
1001                static_cast<typename Graph::Edge>(u)!=
1002                static_cast<typename Graph::Edge>(v));
1003      }
1004    };
1005//     class Edge {
1006//       friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>;
1007//     protected:
1008//       bool out_or_in; //true, iff out
1009//       GraphOutEdgeIt out;
1010//       GraphInEdgeIt in;
1011//     public:
1012//       Edge() : out_or_in(true) { }
1013//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1014// //       bool valid() const {
1015// //   return out_or_in && out.valid() || in.valid(); }
1016//       friend bool operator==(const Edge& u, const Edge& v) {
1017//      if (v.out_or_in)
1018//        return (u.out_or_in && u.out==v.out);
1019//      else
1020//        return (!u.out_or_in && u.in==v.in);
1021//       }
1022//       friend bool operator!=(const Edge& u, const Edge& v) {
1023//      if (v.out_or_in)
1024//        return (!u.out_or_in || u.out!=v.out);
1025//      else
1026//        return (u.out_or_in || u.in!=v.in);
1027//       }
1028//       operator GraphEdge() const {
1029//      if (out_or_in) return(out); else return(in);
1030//       }
1031//     };
1032    class OutEdgeIt {
1033      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1034    protected:
1035      typename Graph::OutEdgeIt out;
1036      typename Graph::InEdgeIt in;
1037      bool forward;
1038    public:
1039      OutEdgeIt() { }
1040      //FIXME
1041//      OutEdgeIt(const Edge& e) : Edge(e) { }
1042      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1043//the unique invalid iterator
1044      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1045        forward=true;
1046        resG.graph->first(out, v);
1047        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1048        if (!resG.graph->valid(out)) {
1049          forward=false;
1050          resG.graph->first(in, v);
1051          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1052        }
1053      }
1054      operator Edge() const {
1055//      Edge e;
1056//      e.forward=this->forward;
1057//      if (this->forward) e=out; else e=in;
1058//      return e;
1059        if (this->forward)
1060          return Edge(out, this->forward);
1061        else
1062          return Edge(in, this->forward);
1063      }
1064    };
1065//     class OutEdgeIt : public Edge {
1066//       friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>;
1067//     public:
1068//       OutEdgeIt() { }
1069//       //FIXME
1070//       OutEdgeIt(const Edge& e) : Edge(e) { }
1071//       OutEdgeIt(const Invalid& i) : Edge(i) { }
1072//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() {
1073//      resG.graph->first(out, v);
1074//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1075//      if (!resG.graph->valid(out)) {
1076//        out_or_in=0;
1077//        resG.graph->first(in, v);
1078//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1079//      }
1080//       }
1081//     public:
1082//       OutEdgeIt& operator++() {
1083//      if (out_or_in) {
1084//        Node v=/*resG->*/G->aNode(out);
1085//        ++out;
1086//        while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1087//        if (!out.valid()) {
1088//          out_or_in=0;
1089//          G->first(in, v);
1090//          while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1091//        }
1092//      } else {
1093//        ++in;
1094//        while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1095//      }
1096//      return *this;
1097//       }
1098//    };
1099
1100    //FIXME This is just for having InEdgeIt
1101//    class InEdgeIt : public Edge { };
1102
1103    class InEdgeIt {
1104      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1105    protected:
1106      typename Graph::OutEdgeIt out;
1107      typename Graph::InEdgeIt in;
1108      bool forward;
1109    public:
1110      InEdgeIt() { }
1111      //FIXME
1112//      OutEdgeIt(const Edge& e) : Edge(e) { }
1113      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
1114//the unique invalid iterator
1115      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
1116        forward=true;
1117        resG.graph->first(in, v);
1118        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
1119        if (!resG.graph->valid(in)) {
1120          forward=false;
1121          resG.graph->first(out, v);
1122          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
1123        }
1124      }
1125      operator Edge() const {
1126//      Edge e;
1127//      e.forward=this->forward;
1128//      if (this->forward) e=out; else e=in;
1129//      return e;
1130        if (this->forward)
1131          return Edge(in, this->forward);
1132        else
1133          return Edge(out, this->forward);
1134      }
1135    };
1136
1137    class EdgeIt {
1138      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1139    protected:
1140      typename Graph::EdgeIt e;
1141      bool forward;
1142    public:
1143      EdgeIt() { }
1144      EdgeIt(const Invalid& i) : e(i), forward(false) { }
1145      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
1146        forward=true;
1147        resG.graph->first(e);
1148        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1149        if (!resG.graph->valid(e)) {
1150          forward=false;
1151          resG.graph->first(e);
1152          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
1153        }
1154      }
1155      operator Edge() const {
1156        return Edge(e, this->forward);
1157      }
1158    };
1159//     class EdgeIt : public Edge {
1160//       friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>;
1161//       NodeIt v;
1162//     public:
1163//       EdgeIt() { }
1164//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1165//       EdgeIt(const Invalid& i) : Edge(i) { }
1166//       EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() {
1167//      resG.graph->first(v);
1168//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1169//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1170//      while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1171//        resG.graph->next(v);
1172//        if (resG.graph->valid(v)) resG.graph->first(out, v);
1173//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1174//      }
1175//      if (!resG.graph->valid(out)) {
1176//        out_or_in=0;
1177//        resG.graph->first(v);
1178//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1179//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1180//        while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1181//          resG.graph->next(v);
1182//          if (resG.graph->valid(v)) resG.graph->first(in, v);
1183//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1184//        }
1185//      }
1186//       }
1187//       EdgeIt& operator++() {
1188//      if (out_or_in) {
1189//        ++out;
1190//        while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1191//        while (v.valid() && !out.valid()) {
1192//          ++v;
1193//          if (v.valid()) G->first(out, v);
1194//          while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1195//        }
1196//        if (!out.valid()) {
1197//          out_or_in=0;
1198//          G->first(v);
1199//          if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
1200//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1201//          while (v.valid() && !in.valid()) {
1202//            ++v;
1203//            if (v.valid()) G->first(in, v);
1204//            while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1205//          } 
1206//        }
1207//      } else {
1208//        ++in;
1209//        while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1210//        while (v.valid() && !in.valid()) {
1211//          ++v;
1212//          if (v.valid()) G->first(in, v);
1213//          while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1214//        }
1215//      }
1216//      return *this;
1217//       }
1218//    };
1219
1220    NodeIt& first(NodeIt& i) const {
1221      i=NodeIt(*this); return i;
1222    }
1223    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1224      i=OutEdgeIt(*this, p); return i;
1225    }
1226//    FIXME not tested
1227    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1228      i=InEdgeIt(*this, p); return i;
1229    }
1230    EdgeIt& first(EdgeIt& i) const {
1231      i=EdgeIt(*this); return i;
1232    }
1233   
1234    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1235    OutEdgeIt& next(OutEdgeIt& e) const {
1236      if (e.forward) {
1237        Node v=graph->aNode(e.out);
1238        graph->next(e.out);
1239        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1240        if (!graph->valid(e.out)) {
1241          e.forward=false;
1242          graph->first(e.in, v);
1243          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1244        }
1245      } else {
1246        graph->next(e.in);
1247        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1248      }
1249      return e;
1250    }
1251//     FIXME Not tested
1252    InEdgeIt& next(InEdgeIt& e) const {
1253      if (e.forward) {
1254        Node v=graph->aNode(e.in);
1255        graph->next(e.in);
1256        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
1257        if (!graph->valid(e.in)) {
1258          e.forward=false;
1259          graph->first(e.out, v);
1260          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1261        }
1262      } else {
1263        graph->next(e.out);
1264        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
1265      }
1266      return e;
1267    }
1268    EdgeIt& next(EdgeIt& e) const {
1269      if (e.forward) {
1270        graph->next(e.e);
1271        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1272        if (!graph->valid(e.e)) {
1273          e.forward=false;
1274          graph->first(e.e);
1275          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1276        }
1277      } else {
1278        graph->next(e.e);
1279        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
1280      }
1281      return e;
1282    }
1283//     EdgeIt& next(EdgeIt& e) const {
1284//       if (e.out_or_in) {
1285//      graph->next(e.out);
1286//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1287//        while (graph->valid(e.v) && !graph->valid(e.out)) {
1288//          graph->next(e.v);
1289//          if (graph->valid(e.v)) graph->first(e.out, e.v);
1290//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1291//        }
1292//        if (!graph->valid(e.out)) {
1293//          e.out_or_in=0;
1294//          graph->first(e.v);
1295//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1296//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1297//          while (graph->valid(e.v) && !graph->valid(e.in)) {
1298//            graph->next(e.v);
1299//            if (graph->valid(e.v)) graph->first(e.in, e.v);
1300//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1301//          } 
1302//        }
1303//      } else {
1304//        graph->next(e.in);
1305//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1306//        while (graph->valid(e.v) && !graph->valid(e.in)) {
1307//          graph->next(e.v);
1308//          if (graph->valid(e.v)) graph->first(e.in, e.v);
1309//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1310//        }
1311//      }
1312//      return e;
1313//       }
1314   
1315
1316//     template< typename It >
1317//     It first() const {
1318//       It e;
1319//       first(e);
1320//       return e;
1321//     }
1322
1323//     template< typename It >
1324//     It first(Node v) const {
1325//       It e;
1326//       first(e, v);
1327//       return e;
1328//     }
1329
1330    Node tail(Edge e) const {
1331      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
1332    Node head(Edge e) const {
1333      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
1334
1335    Node aNode(OutEdgeIt e) const {
1336      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1337    Node bNode(OutEdgeIt e) const {
1338      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1339
1340    int nodeNum() const { return graph->nodeNum(); }
1341    //FIXME
1342    //int edgeNum() const { return graph->edgeNum(); }
1343
1344
1345//    int id(Node v) const { return graph->id(v); }
1346
1347    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1348    bool valid(Edge e) const {
1349      return graph->valid(e);
1350        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1351    }
1352
1353    void augment(const Edge& e, Number a) const {
1354      if (e.forward) 
1355//      flow->set(e.out, flow->get(e.out)+a);
1356        flow->set(e, (*flow)[e]+a);
1357      else 
1358//      flow->set(e.in, flow->get(e.in)-a);
1359        flow->set(e, (*flow)[e]-a);
1360    }
1361
1362    Number resCap(const Edge& e) const {
1363      if (e.forward)
1364//      return (capacity->get(e.out)-flow->get(e.out));
1365        return ((*capacity)[e]-(*flow)[e]);
1366      else
1367//      return (flow->get(e.in));
1368        return ((*flow)[e]);
1369    }
1370
1371//     Number resCap(typename Graph::OutEdgeIt out) const {
1372// //      return (capacity->get(out)-flow->get(out));
1373//       return ((*capacity)[out]-(*flow)[out]);
1374//     }
1375   
1376//     Number resCap(typename Graph::InEdgeIt in) const {
1377// //      return (flow->get(in));
1378//       return ((*flow)[in]);
1379//     }
1380
1381//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1382//     public:
1383//       NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G)
1384//      : Graph::NodeMap<T>(_G.gw) { }
1385//       NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G,
1386//            T a) : Graph::NodeMap<T>(_G.gw, a) { }
1387//     };
1388
1389//     template <typename T>
1390//     class NodeMap {
1391//       typename Graph::NodeMap<T> node_map;
1392//     public:
1393//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1394//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1395//       void set(Node nit, T a) { node_map.set(nit, a); }
1396//       T get(Node nit) const { return node_map.get(nit); }
1397//     };
1398
1399    template <typename T>
1400    class EdgeMap {
1401      typename Graph::EdgeMap<T> forward_map, backward_map;
1402    public:
1403      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1404      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1405      void set(Edge e, T a) {
1406        if (e.forward)
1407          forward_map.set(e.out, a);
1408        else
1409          backward_map.set(e.in, a);
1410      }
1411      T operator[](Edge e) const {
1412        if (e.forward)
1413          return forward_map[e.out];
1414        else
1415          return backward_map[e.in];
1416      }
1417//       T get(Edge e) const {
1418//      if (e.out_or_in)
1419//        return forward_map.get(e.out);
1420//      else
1421//        return backward_map.get(e.in);
1422//       }
1423    };
1424  };
1425
1426 
1427
1428//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1429//   class ResGraphWrapper : public GraphWrapper<Graph> {
1430//   protected:
1431//     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1432//     typedef typename Graph::InEdgeIt GraphInEdgeIt;
1433//     typedef typename Graph::Edge GraphEdge;
1434//     FlowMap* flow;
1435//     const CapacityMap* capacity;
1436//   public:
1437
1438//     ResGraphWrapper(Graph& _graph, FlowMap& _flow,
1439//                  const CapacityMap& _capacity) :
1440//       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
1441
1442//     class Edge;
1443//     class OutEdgeIt;
1444//     friend class Edge;
1445//     friend class OutEdgeIt;
1446
1447//     typedef typename GraphWrapper<Graph>::Node Node;
1448//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1449//     class Edge {
1450//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1451//     protected:
1452//       bool out_or_in; //true, iff out
1453//       GraphOutEdgeIt out;
1454//       GraphInEdgeIt in;
1455//     public:
1456//       Edge() : out_or_in(true) { }
1457//       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
1458// //       bool valid() const {
1459// //   return out_or_in && out.valid() || in.valid(); }
1460//       friend bool operator==(const Edge& u, const Edge& v) {
1461//      if (v.out_or_in)
1462//        return (u.out_or_in && u.out==v.out);
1463//      else
1464//        return (!u.out_or_in && u.in==v.in);
1465//       }
1466//       friend bool operator!=(const Edge& u, const Edge& v) {
1467//      if (v.out_or_in)
1468//        return (!u.out_or_in || u.out!=v.out);
1469//      else
1470//        return (u.out_or_in || u.in!=v.in);
1471//       }
1472//       operator GraphEdge() const {
1473//      if (out_or_in) return(out); else return(in);
1474//       }
1475//     };
1476//     class OutEdgeIt : public Edge {
1477//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1478//     public:
1479//       OutEdgeIt() { }
1480//       //FIXME
1481//       OutEdgeIt(const Edge& e) : Edge(e) { }
1482//       OutEdgeIt(const Invalid& i) : Edge(i) { }
1483//       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
1484//      resG.graph->first(out, v);
1485//      while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1486//      if (!resG.graph->valid(out)) {
1487//        out_or_in=0;
1488//        resG.graph->first(in, v);
1489//        while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1490//      }
1491//       }
1492// //     public:
1493// //       OutEdgeIt& operator++() {
1494// //   if (out_or_in) {
1495// //     Node v=/*resG->*/G->aNode(out);
1496// //     ++out;
1497// //     while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
1498// //     if (!out.valid()) {
1499// //       out_or_in=0;
1500// //       G->first(in, v);
1501// //       while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1502// //     }
1503// //   } else {
1504// //     ++in;
1505// //     while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
1506// //   }
1507// //   return *this;
1508// //       }
1509//     };
1510
1511//     //FIXME This is just for having InEdgeIt
1512// //    class InEdgeIt : public Edge { };
1513
1514//     class EdgeIt : public Edge {
1515//       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1516//       NodeIt v;
1517//     public:
1518//       EdgeIt() { }
1519//       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
1520//       EdgeIt(const Invalid& i) : Edge(i) { }
1521//       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
1522//      resG.graph->first(v);
1523//      if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
1524//      while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1525//      while (resG.graph->valid(v) && !resG.graph->valid(out)) {
1526//        resG.graph->next(v);
1527//        if (resG.graph->valid(v)) resG.graph->first(out, v);
1528//        while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
1529//      }
1530//      if (!resG.graph->valid(out)) {
1531//        out_or_in=0;
1532//        resG.graph->first(v);
1533//        if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
1534//        while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1535//        while (resG.graph->valid(v) && !resG.graph->valid(in)) {
1536//          resG.graph->next(v);
1537//          if (resG.graph->valid(v)) resG.graph->first(in, v);
1538//          while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
1539//        }
1540//      }
1541//       }
1542// //       EdgeIt& operator++() {
1543// //   if (out_or_in) {
1544// //     ++out;
1545// //     while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1546// //     while (v.valid() && !out.valid()) {
1547// //       ++v;
1548// //       if (v.valid()) G->first(out, v);
1549// //       while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
1550// //     }
1551// //     if (!out.valid()) {
1552// //       out_or_in=0;
1553// //       G->first(v);
1554// //       if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
1555// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1556// //       while (v.valid() && !in.valid()) {
1557// //         ++v;
1558// //         if (v.valid()) G->first(in, v);
1559// //         while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1560// //       } 
1561// //     }
1562// //   } else {
1563// //     ++in;
1564// //     while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1565// //     while (v.valid() && !in.valid()) {
1566// //       ++v;
1567// //       if (v.valid()) G->first(in, v);
1568// //       while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
1569// //     }
1570// //   }
1571// //   return *this;
1572// //       }
1573//     };
1574
1575//     NodeIt& first(NodeIt& i) const {
1576//       i=NodeIt(*this);
1577//       return i;
1578//     }
1579//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1580//       i=OutEdgeIt(*this, p);
1581//       return i;
1582//     }
1583//     //FIXME Not yet implemented
1584//     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1585//     //i=InEdgeIt(*this, p);
1586//     //  return i;
1587//     //}
1588//     EdgeIt& first(EdgeIt& e) const {
1589//       e=EdgeIt(*this);
1590//       return e;
1591//     }
1592   
1593//     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
1594//     OutEdgeIt& next(OutEdgeIt& e) const {
1595//       if (e.out_or_in) {
1596//      Node v=graph->aNode(e.out);
1597//      graph->next(e.out);
1598//      while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1599//      if (!graph->valid(e.out)) {
1600//        e.out_or_in=0;
1601//        graph->first(e.in, v);
1602//        while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1603//      }
1604//       } else {
1605//      graph->next(e.in);
1606//      while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1607//       }
1608//       return e;
1609//     }
1610//     //FIXME Not yet implemented
1611//     //InEdgeIt& next(InEdgeIt& e) const {
1612//     //  return e;
1613//     //}
1614//     EdgeIt& next(EdgeIt& e) const {
1615//       if (e.out_or_in) {
1616//      graph->next(e.out);
1617//      while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1618//        while (graph->valid(e.v) && !graph->valid(e.out)) {
1619//          graph->next(e.v);
1620//          if (graph->valid(e.v)) graph->first(e.out, e.v);
1621//          while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
1622//        }
1623//        if (!graph->valid(e.out)) {
1624//          e.out_or_in=0;
1625//          graph->first(e.v);
1626//          if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
1627//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1628//          while (graph->valid(e.v) && !graph->valid(e.in)) {
1629//            graph->next(e.v);
1630//            if (graph->valid(e.v)) graph->first(e.in, e.v);
1631//            while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1632//          } 
1633//        }
1634//      } else {
1635//        graph->next(e.in);
1636//        while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1637//        while (graph->valid(e.v) && !graph->valid(e.in)) {
1638//          graph->next(e.v);
1639//          if (graph->valid(e.v)) graph->first(e.in, e.v);
1640//          while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
1641//        }
1642//      }
1643//      return e;
1644//       }
1645   
1646
1647//     template< typename It >
1648//     It first() const {
1649//       It e;
1650//       first(e);
1651//       return e;
1652//     }
1653
1654//     template< typename It >
1655//     It first(Node v) const {
1656//       It e;
1657//       first(e, v);
1658//       return e;
1659//     }
1660
1661//     Node tail(Edge e) const {
1662//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1663//     Node head(Edge e) const {
1664//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1665
1666//     Node aNode(OutEdgeIt e) const {
1667//       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
1668//     Node bNode(OutEdgeIt e) const {
1669//       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
1670
1671//     int nodeNum() const { return graph->nodeNum(); }
1672//     //FIXME
1673//     //int edgeNum() const { return graph->edgeNum(); }
1674
1675
1676//     int id(Node v) const { return graph->id(v); }
1677
1678//     bool valid(Node n) const { return graph->valid(n); }
1679//     bool valid(Edge e) const {
1680//       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
1681
1682//     void augment(const Edge& e, Number a) const {
1683//       if (e.out_or_in) 
1684// //   flow->set(e.out, flow->get(e.out)+a);
1685//      flow->set(e.out, (*flow)[e.out]+a);
1686//       else 
1687// //   flow->set(e.in, flow->get(e.in)-a);
1688//      flow->set(e.in, (*flow)[e.in]-a);
1689//     }
1690
1691//     Number resCap(const Edge& e) const {
1692//       if (e.out_or_in)
1693// //   return (capacity->get(e.out)-flow->get(e.out));
1694//      return ((*capacity)[e.out]-(*flow)[e.out]);
1695//       else
1696// //   return (flow->get(e.in));
1697//      return ((*flow)[e.in]);
1698//     }
1699
1700//     Number resCap(GraphOutEdgeIt out) const {
1701// //      return (capacity->get(out)-flow->get(out));
1702//       return ((*capacity)[out]-(*flow)[out]);
1703//     }
1704   
1705//     Number resCap(GraphInEdgeIt in) const {
1706// //      return (flow->get(in));
1707//       return ((*flow)[in]);
1708//     }
1709
1710// //     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1711// //     public:
1712// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1713// //   : Graph::NodeMap<T>(_G.gw) { }
1714// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
1715// //         T a) : Graph::NodeMap<T>(_G.gw, a) { }
1716// //     };
1717
1718// //     template <typename T>
1719// //     class NodeMap {
1720// //       typename Graph::NodeMap<T> node_map;
1721// //     public:
1722// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
1723// //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
1724// //       void set(Node nit, T a) { node_map.set(nit, a); }
1725// //       T get(Node nit) const { return node_map.get(nit); }
1726// //     };
1727
1728//     template <typename T>
1729//     class EdgeMap {
1730//       typename Graph::EdgeMap<T> forward_map, backward_map;
1731//     public:
1732//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1733//       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1734//       void set(Edge e, T a) {
1735//      if (e.out_or_in)
1736//        forward_map.set(e.out, a);
1737//      else
1738//        backward_map.set(e.in, a);
1739//       }
1740//       T operator[](Edge e) const {
1741//      if (e.out_or_in)
1742//        return forward_map[e.out];
1743//      else
1744//        return backward_map[e.in];
1745//       }
1746// //       T get(Edge e) const {
1747// //   if (e.out_or_in)
1748// //     return forward_map.get(e.out);
1749// //   else
1750// //     return backward_map.get(e.in);
1751// //       }
1752//     };
1753//   };
1754
1755
1756  //ErasingFirstGraphWrapper for blocking flows
1757  template<typename Graph, typename FirstOutEdgesMap>
1758  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1759  protected:
1760    FirstOutEdgesMap* first_out_edges;
1761  public:
1762    ErasingFirstGraphWrapper(Graph& _graph,
1763                             FirstOutEdgesMap& _first_out_edges) :
1764      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1765
1766    typedef typename GraphWrapper<Graph>::Node Node;
1767    class NodeIt {
1768      friend class GraphWrapper<Graph>;
1769      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1770      typename Graph::NodeIt n;
1771     public:
1772      NodeIt() { }
1773      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1774      NodeIt(const Invalid& i) : n(i) { }
1775      NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1776        n(*(_G.graph)) { }
1777      operator Node() const { return Node(typename Graph::Node(n)); }
1778    };
1779    typedef typename GraphWrapper<Graph>::Edge Edge;
1780    class OutEdgeIt {
1781      friend class GraphWrapper<Graph>;
1782      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1783//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1784      typename Graph::OutEdgeIt e;
1785    public:
1786      OutEdgeIt() { }
1787      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1788      OutEdgeIt(const Invalid& i) : e(i) { }
1789      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1790                const Node& _n) :
1791        e((*_G.first_out_edges)[_n]) { }
1792      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1793    };
1794    class InEdgeIt {
1795      friend class GraphWrapper<Graph>;
1796      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1797//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
1798      typename Graph::InEdgeIt e;
1799    public:
1800      InEdgeIt() { }
1801      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1802      InEdgeIt(const Invalid& i) : e(i) { }
1803      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1804               const Node& _n) :
1805        e(*(_G.graph), typename Graph::Node(_n)) { }
1806      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1807    };
1808    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1809    class EdgeIt {
1810      friend class GraphWrapper<Graph>;
1811      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1812//      typedef typename Graph::EdgeIt GraphEdgeIt;
1813      typename Graph::EdgeIt e;
1814    public:
1815      EdgeIt() { }
1816      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1817      EdgeIt(const Invalid& i) : e(i) { }
1818      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1819        e(*(_G.graph)) { }
1820      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1821    };
1822
1823    NodeIt& first(NodeIt& i) const {
1824      i=NodeIt(*this); return i;
1825    }
1826    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1827      i=OutEdgeIt(*this, p); return i;
1828    }
1829    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1830      i=InEdgeIt(*this, p); return i;
1831    }
1832    EdgeIt& first(EdgeIt& i) const {
1833      i=EdgeIt(*this); return i;
1834    }
1835
1836//     template<typename I> I& first(I& i) const {
1837//       graph->first(i);
1838//       return i;
1839//     }
1840//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1841// //      e=first_out_edges->get(n);
1842//       e=(*first_out_edges)[n];
1843//       return e;
1844//     }
1845//     template<typename I, typename P> I& first(I& i, const P& p) const {
1846//       graph->first(i, p);
1847//       return i;
1848//     }
1849   
1850    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1851    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1852    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1853    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
1854   
1855    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1856    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1857    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1858    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1859
1860//     template<typename I> I& next(I &i) const {
1861//       graph->next(i);
1862//       return i;
1863//     }
1864   
1865//     template< typename It > It first() const {
1866//       It e; this->first(e); return e; }
1867   
1868//     template< typename It > It first(const Node& v) const {
1869//       It e; this->first(e, v); return e; }
1870
1871    void erase(const OutEdgeIt& e) const {
1872      OutEdgeIt f=e;
1873      this->next(f);
1874      first_out_edges->set(this->tail(e), f.e);
1875    }
1876  };
1877
1878//   //ErasingFirstGraphWrapper for blocking flows
1879//   template<typename Graph, typename FirstOutEdgesMap>
1880//   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1881//   protected:
1882//     FirstOutEdgesMap* first_out_edges;
1883//   public:
1884//     ErasingFirstGraphWrapper(Graph& _graph,
1885//                           FirstOutEdgesMap& _first_out_edges) :
1886//       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1887
1888//     typedef typename Graph::Node Node;
1889//     class NodeIt : public Graph::NodeIt {
1890//     public:
1891//       NodeIt() { }
1892//       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
1893//       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
1894//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1895//      Graph::NodeIt(*(_G.graph)) { }
1896//     };
1897//     typedef typename Graph::Edge Edge;
1898//     class OutEdgeIt : public Graph::OutEdgeIt {
1899//     public:
1900//       OutEdgeIt() { }
1901//       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
1902//       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
1903//       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1904//              const Node& n) :
1905//      Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
1906//     };
1907//     class InEdgeIt : public Graph::InEdgeIt {
1908//     public:
1909//       InEdgeIt() { }
1910//       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
1911//       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
1912//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1913//             const Node& n) :
1914//      Graph::InEdgeIt(*(_G.graph), n) { }
1915//     };
1916//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1917//     class EdgeIt : public Graph::EdgeIt {
1918//     public:
1919//       EdgeIt() { }
1920//       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
1921//       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
1922//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1923//      Graph::EdgeIt(*(_G.graph)) { }
1924//     };
1925
1926//     NodeIt& first(NodeIt& i) const {
1927//       i=NodeIt(*this);
1928//       return i;
1929//     }
1930//     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
1931//       i=OutEdgeIt(*this, n);
1932// //      i=(*first_out_edges)[n];
1933//       return i;
1934//     }
1935//     InEdgeIt& first(InEdgeIt& i, const Node& n) const {
1936//       i=InEdgeIt(*this, n);
1937//       return i;
1938//     }
1939//     EdgeIt& first(EdgeIt& i) const {
1940//       i=EdgeIt(*this);
1941//       return i;
1942//     }
1943
1944// //     template<typename I> I& first(I& i) const {
1945// //       graph->first(i);
1946// //       return i;
1947// //     }
1948// //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
1949// // //      e=first_out_edges->get(n);
1950// //       e=(*first_out_edges)[n];
1951// //       return e;
1952// //     }
1953// //     template<typename I, typename P> I& first(I& i, const P& p) const {
1954// //       graph->first(i, p);
1955// //       return i;
1956// //     }
1957   
1958//     NodeIt& next(NodeIt& i) const {
1959//       graph->next(i);
1960//       return i;
1961//     }
1962//     OutEdgeIt& next(OutEdgeIt& i) const {
1963//       graph->next(i);
1964//       return i;
1965//     }
1966//     InEdgeIt& next(InEdgeIt& i) const {
1967//       graph->next(i);
1968//       return i;
1969//     }
1970//     EdgeIt& next(EdgeIt& i) const {
1971//       graph->next(i);
1972//       return i;
1973//     }
1974
1975// //     template<typename I> I& next(I &i) const {
1976// //       graph->next(i);
1977// //       return i;
1978// //     }
1979   
1980//     template< typename It > It first() const {
1981//       It e; this->first(e); return e; }
1982   
1983//     template< typename It > It first(const Node& v) const {
1984//       It e; this->first(e, v); return e; }
1985
1986//     void erase(const OutEdgeIt& e) const {
1987//       OutEdgeIt f=e;
1988//       this->next(f);
1989//       first_out_edges->set(this->tail(e), f);
1990//     }
1991//   };
1992
1993
1994// // FIXME: comparison should be made better!!!
1995//   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
1996//   class ResGraphWrapper
1997//   {
1998//     Graph* graph;
1999 
2000//   public:
2001//     typedef Graph ParentGraph;
2002
2003//     typedef typename Graph::Node Node;
2004//     typedef typename Graph::Edge Edge;
2005 
2006//     typedef typename Graph::NodeIt NodeIt;
2007   
2008//     class OutEdgeIt {
2009//     public:
2010//       //Graph::Node n;
2011//       bool out_or_in;
2012//       typename Graph::OutEdgeIt o;
2013//       typename Graph::InEdgeIt i;   
2014//     };
2015//     class InEdgeIt {
2016//     public:
2017//       //Graph::Node n;
2018//       bool out_or_in;
2019//       typename Graph::OutEdgeIt o;
2020//       typename Graph::InEdgeIt i;   
2021//     };
2022//     typedef typename Graph::SymEdgeIt SymEdgeIt;
2023//     typedef typename Graph::EdgeIt EdgeIt;
2024
2025//     int nodeNum() const { return gw.nodeNum(); }
2026//     int edgeNum() const { return gw.edgeNum(); }
2027
2028//     Node& first(Node& n) const { return gw.first(n); }
2029
2030//     // Edge and SymEdge  is missing!!!!
2031//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
2032
2033//     //FIXME
2034//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
2035//       {
2036//      e.n=n;
2037//      gw.first(e.o,n);
2038//      while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
2039//        gw.goNext(e.o);
2040//      if(!gw.valid(e.o)) {
2041//        gw.first(e.i,n);
2042//        while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
2043//          gw.goNext(e.i);
2044//      }
2045//      return e;
2046//       }
2047// /*
2048//   OutEdgeIt &goNext(OutEdgeIt &e)
2049//   {
2050//   if(gw.valid(e.o)) {
2051//   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
2052//   gw.goNext(e.o);
2053//   if(gw.valid(e.o)) return e;
2054//   else gw.first(e.i,e.n);
2055//   }
2056//   else {
2057//   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
2058//   gw.goNext(e.i);
2059//   return e;
2060//   }
2061//   }
2062//   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
2063// */
2064//     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}
2065
2066//     //FIXME
2067//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
2068//       {
2069//      e.n=n;
2070//      gw.first(e.i,n);
2071//      while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
2072//        gw.goNext(e.i);
2073//      if(!gw.valid(e.i)) {
2074//        gw.first(e.o,n);
2075//        while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
2076//          gw.goNext(e.o);
2077//      }
2078//      return e;
2079//       }
2080// /*
2081//   InEdgeIt &goNext(InEdgeIt &e)
2082//   {
2083//   if(gw.valid(e.i)) {
2084//   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
2085//   gw.goNext(e.i);
2086//   if(gw.valid(e.i)) return e;
2087//   else gw.first(e.o,e.n);
2088//   }
2089//   else {
2090//   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
2091//   gw.goNext(e.o);
2092//   return e;
2093//   }
2094//   }
2095//   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
2096// */
2097//     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}
2098
2099//     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }
2100//     //template<typename I> I next(const I i); { return gw.goNext(i); }
2101
2102//     template< typename It > It first() const {
2103//       It e; first(e); return e; }
2104
2105//     template< typename It > It first(Node v) const {
2106//       It e; first(e, v); return e; }
2107
2108//     Node head(const Edge& e) const { return gw.head(e); }
2109//     Node tail(const Edge& e) const { return gw.tail(e); }
2110 
2111//     template<typename I> Node aNode(const I& e) const {
2112//       return gw.aNode(e); }
2113//     template<typename I> Node bNode(const I& e) const {
2114//       return gw.bNode(e); }
2115 
2116//     //template<typename I> bool valid(const I i);
2117//     //{ return gw.valid(i); }
2118 
2119//     //template<typename I> void setInvalid(const I &i);
2120//     //{ return gw.setInvalid(i); }
2121 
2122//     Node addNode() { return gw.addNode(); }
2123//     Edge addEdge(const Node& tail, const Node& head) {
2124//       return gw.addEdge(tail, head); }
2125 
2126//     template<typename I> void erase(const I& i) { gw.erase(i); }
2127 
2128//     void clear() { gw.clear(); }
2129 
2130//     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
2131//     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
2132 
2133//     void setGraph(Graph& _graph) { graph = &_graph; }
2134//     Graph& getGraph() { return (*graph); }
2135
2136//     //ResGraphWrapper() : graph(0) { }
2137//     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
2138//   };
2139
2140} //namespace hugo
2141
2142#endif //HUGO_GRAPH_WRAPPER_H
2143
Note: See TracBrowser for help on using the repository browser.