# source:lemon-0.x/src/work/marci/graph_wrapper.h@368:0beed7a49063

Last change on this file since 368:0beed7a49063 was 368:0beed7a49063, checked in by marci, 17 years ago

experimental bipartite graph wrapper

File size: 39.7 KB
Line
1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
4
5#include <invalid.h>
6#include <iter_map.h>
7
8namespace hugo {
9
10  /// Graph wrappers
11
12  /// A main parts of HUGOlib are the different graph structures,
13  /// generic graph algorithms, graph concepts which couple these, and
14  /// graph wrappers. While the previous ones are more or less clear, the
15  /// latter notion needs further explanation.
16  /// Graph wrappers are graph classes which serve for considering graph
17  /// structures in different ways. A short example makes the notion much
18  /// clearer.
19  /// Suppose that we have an instance \c g of a directed graph
20  /// type say \c ListGraph and an algorithm
21  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
22  /// is needed to run on the reversely oriented graph.
23  /// It may be expensive (in time or in memory usage) to copy
24  /// \c g with the reverse orientation.
25  /// Thus, a wrapper class
26  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
27  /// The code looks as follows
28  /// \code
29  /// ListGraph g;
30  /// RevGraphWrapper<ListGraph> rgw(g);
31  /// int result=algorithm(rgw);
32  /// \endcode
33  /// After running the algorithm, the original graph \c g
34  /// remains untouched. Thus the graph wrapper used above is to consider the
35  /// original graph with reverse orientation.
36  /// This techniques gives rise to an elegant code, and
37  /// based on stable graph wrappers, complex algorithms can be
38  /// implemented easily.
39  /// In flow, circulation and bipartite matching problems, the residual
40  /// graph is of particular importance. Combining a wrapper implementing
41  /// this, shortest path algorithms and minimum mean cycle algorithms,
42  /// a range of weighted and cardinality optimization algorithms can be
43  /// obtained. For lack of space, for other examples,
44  /// the interested user is referred to the detailed documentation of graph
45  /// wrappers.
46  /// The behavior of graph wrappers can be very different. Some of them keep
47  /// capabilities of the original graph while in other cases this would be
48  /// meaningless. This means that the concepts that they are a model of depend
49  /// on the graph wrapper, and the wrapped graph(s).
50  /// If an edge of \c rgw is deleted, this is carried out by
51  /// deleting the corresponding edge of \c g. But for a residual
52  /// graph, this operation has no sense.
53  /// Let we stand one more example here to simplify your work.
54  /// wrapper class
55  /// \code template<typename Graph> class RevGraphWrapper; \endcode
56  /// has constructor
57  /// <tt> RevGraphWrapper(Graph& _g)</tt>.
58  /// This means that in a situation,
59  /// when a <tt> const ListGraph& </tt> reference to a graph is given,
60  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
61  /// \code
62  /// int algorithm1(const ListGraph& g) {
63  ///   RevGraphWrapper<const ListGraph> rgw(g);
64  ///   return algorithm2(rgw);
65  /// }
66  /// \endcode
67  template<typename Graph>
68  class GraphWrapper {
69  protected:
70    Graph* graph;
71
72  public:
73    typedef Graph BaseGraph;
74    typedef Graph ParentGraph;
75
76//     GraphWrapper() : graph(0) { }
77    GraphWrapper(Graph& _graph) : graph(&_graph) { }
78//     void setGraph(Graph& _graph) { graph=&_graph; }
79//     Graph& getGraph() const { return *graph; }
80
81//    typedef typename Graph::Node Node;
82    class Node : public Graph::Node {
83      friend class GraphWrapper<Graph>;
84    public:
85      Node() { }
86      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
87      Node(const Invalid& i) : Graph::Node(i) { }
88    };
89    class NodeIt {
90      friend class GraphWrapper<Graph>;
91      typename Graph::NodeIt n;
92     public:
93      NodeIt() { }
94      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
95      NodeIt(const Invalid& i) : n(i) { }
96      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
97      operator Node() const { return Node(typename Graph::Node(n)); }
98    };
99//    typedef typename Graph::Edge Edge;
100    class Edge : public Graph::Edge {
101      friend class GraphWrapper<Graph>;
102    public:
103      Edge() { }
104      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
105      Edge(const Invalid& i) : Graph::Edge(i) { }
106    };
107    class OutEdgeIt {
108      friend class GraphWrapper<Graph>;
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      typename Graph::InEdgeIt e;
121    public:
122      InEdgeIt() { }
123      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
124      InEdgeIt(const Invalid& i) : e(i) { }
125      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
126        e(*(_G.graph), typename Graph::Node(_n)) { }
127      operator Edge() const { return Edge(typename Graph::Edge(e)); }
128    };
129    //typedef typename Graph::SymEdgeIt SymEdgeIt;
130    class EdgeIt {
131      friend class GraphWrapper<Graph>;
132      typename Graph::EdgeIt e;
133    public:
134      EdgeIt() { }
135      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
136      EdgeIt(const Invalid& i) : e(i) { }
137      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
138      operator Edge() const { return Edge(typename Graph::Edge(e)); }
139    };
140
141    NodeIt& first(NodeIt& i) const {
142      i=NodeIt(*this); return i;
143    }
144    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
145      i=OutEdgeIt(*this, p); return i;
146    }
147    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
148      i=InEdgeIt(*this, p); return i;
149    }
150    EdgeIt& first(EdgeIt& i) const {
151      i=EdgeIt(*this); return i;
152    }
153
154    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
155    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
156    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
157    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
158
159    Node head(const Edge& e) const {
161    Node tail(const Edge& e) const {
162      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
163
164    bool valid(const Node& n) const {
165      return graph->valid(static_cast<typename Graph::Node>(n)); }
166    bool valid(const Edge& e) const {
167      return graph->valid(static_cast<typename Graph::Edge>(e)); }
168
169    int nodeNum() const { return graph->nodeNum(); }
170    int edgeNum() const { return graph->edgeNum(); }
171
172    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
173    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
174    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
175    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
176
180
181    void erase(const Node& i) const { graph->erase(i); }
182    void erase(const Edge& i) const { graph->erase(i); }
183
184    void clear() const { graph->clear(); }
185
186    template<typename T> class NodeMap : public Graph::NodeMap<T> {
187    public:
188      NodeMap(const GraphWrapper<Graph>& _G) :
189        Graph::NodeMap<T>(*(_G.graph)) { }
190      NodeMap(const GraphWrapper<Graph>& _G, T a) :
191        Graph::NodeMap<T>(*(_G.graph), a) { }
192    };
193
194    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
195    public:
196      EdgeMap(const GraphWrapper<Graph>& _G) :
197        Graph::EdgeMap<T>(*(_G.graph)) { }
198      EdgeMap(const GraphWrapper<Graph>& _G, T a) :
199        Graph::EdgeMap<T>(*(_G.graph), a) { }
200    };
201  };
202
203  /// A graph wrapper which reverses the orientation of the edges.
204
205  /// A graph wrapper which reverses the orientation of the edges.
206  template<typename Graph>
207  class RevGraphWrapper : public GraphWrapper<Graph> {
208  public:
209
210    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
211
212    typedef typename GraphWrapper<Graph>::Node Node;
213    typedef typename GraphWrapper<Graph>::Edge Edge;
214    //If Graph::OutEdgeIt is not defined
215    //and we do not want to use RevGraphWrapper::InEdgeIt,
216    //the typdef techinque does not work.
217    //Unfortunately all the typedefs are instantiated in templates.
218    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
219    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
220
221    class OutEdgeIt {
222      friend class GraphWrapper<Graph>;
223      friend class RevGraphWrapper<Graph>;
224      typename Graph::OutEdgeIt e;
225    public:
226      OutEdgeIt() { }
227      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
228      OutEdgeIt(const Invalid& i) : e(i) { }
229      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
230        e(*(_G.graph), typename Graph::Node(_n)) { }
231      operator Edge() const { return Edge(typename Graph::Edge(e)); }
232    };
233    class InEdgeIt {
234      friend class GraphWrapper<Graph>;
235      friend class RevGraphWrapper<Graph>;
236      typename Graph::InEdgeIt e;
237    public:
238      InEdgeIt() { }
239      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
240      InEdgeIt(const Invalid& i) : e(i) { }
241      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
242        e(*(_G.graph), typename Graph::Node(_n)) { }
243      operator Edge() const { return Edge(typename Graph::Edge(e)); }
244    };
245
246    using GraphWrapper<Graph>::first;
247    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
248      i=OutEdgeIt(*this, p); return i;
249    }
250    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
251      i=InEdgeIt(*this, p); return i;
252    }
253
254    using GraphWrapper<Graph>::next;
255    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
256    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
257
258    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
259    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
260    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
261    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
262  };
263
264  /// Wrapper for hiding nodes and edges from a graph.
265
266  /// This wrapper shows a graph with filtered node-set and
267  /// edge-set. The quick brown fox iterator jumps over
268  /// the lazy dog nodes or edges if the values for them are false
269  /// in the bool maps.
270  template<typename Graph, typename NodeFilterMap,
271           typename EdgeFilterMap>
272  class SubGraphWrapper : public GraphWrapper<Graph> {
273  protected:
274    NodeFilterMap* node_filter_map;
275    EdgeFilterMap* edge_filter_map;
276  public:
277
278    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
279                    EdgeFilterMap& _edge_filter_map) :
280      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
281      edge_filter_map(&_edge_filter_map) { }
282
283    typedef typename GraphWrapper<Graph>::Node Node;
284    class NodeIt {
285      friend class GraphWrapper<Graph>;
286      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
287      typename Graph::NodeIt n;
288     public:
289      NodeIt() { }
290      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
291      NodeIt(const Invalid& i) : n(i) { }
292      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
293        n(*(_G.graph)) {
294        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
295          _G.graph->next(n);
296      }
297      operator Node() const { return Node(typename Graph::Node(n)); }
298    };
299    typedef typename GraphWrapper<Graph>::Edge Edge;
300    class OutEdgeIt {
301      friend class GraphWrapper<Graph>;
302      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
303      typename Graph::OutEdgeIt e;
304    public:
305      OutEdgeIt() { }
306      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
307      OutEdgeIt(const Invalid& i) : e(i) { }
308      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
309                const Node& _n) :
310        e(*(_G.graph), typename Graph::Node(_n)) {
311        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
312          _G.graph->next(e);
313      }
314      operator Edge() const { return Edge(typename Graph::Edge(e)); }
315    };
316    class InEdgeIt {
317      friend class GraphWrapper<Graph>;
318      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
319      typename Graph::InEdgeIt e;
320    public:
321      InEdgeIt() { }
322      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
323      InEdgeIt(const Invalid& i) : e(i) { }
324      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
325               const Node& _n) :
326        e(*(_G.graph), typename Graph::Node(_n)) {
327        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
328          _G.graph->next(e);
329      }
330      operator Edge() const { return Edge(typename Graph::Edge(e)); }
331    };
332    //typedef typename Graph::SymEdgeIt SymEdgeIt;
333    class EdgeIt {
334      friend class GraphWrapper<Graph>;
335      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
336      typename Graph::EdgeIt e;
337    public:
338      EdgeIt() { }
339      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
340      EdgeIt(const Invalid& i) : e(i) { }
341      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
342        e(*(_G.graph)) {
343        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
344          _G.graph->next(e);
345      }
346      operator Edge() const { return Edge(typename Graph::Edge(e)); }
347    };
348
349    NodeIt& first(NodeIt& i) const {
350      i=NodeIt(*this); return i;
351    }
352    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
353      i=OutEdgeIt(*this, p); return i;
354    }
355    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
356      i=InEdgeIt(*this, p); return i;
357    }
358    EdgeIt& first(EdgeIt& i) const {
359      i=EdgeIt(*this); return i;
360    }
361
362    NodeIt& next(NodeIt& i) const {
363      graph->next(i.n);
364      while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
365      return i;
366    }
367    OutEdgeIt& next(OutEdgeIt& i) const {
368      graph->next(i.e);
369      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
370      return i;
371    }
372    InEdgeIt& next(InEdgeIt& i) const {
373      graph->next(i.e);
374      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
375      return i;
376    }
377    EdgeIt& next(EdgeIt& i) const {
378      graph->next(i.e);
379      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
380      return i;
381    }
382
383    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
384    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
385    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
386    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
387
388    ///\todo
390    void hide(const Node& n) const { node_filter_map->set(n, false); }
391    ///\todo
393    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
394
395    ///\todo
397    void unHide(const Node& n) const { node_filter_map->set(n, true); }
398    ///\todo
400    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
401
402    ///\todo
404    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
405    ///\todo
407    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
408  };
409
410  /// A wrapper for forgetting the orientation of a graph.
411
412  /// A wrapper for getting an undirected graph by forgetting
413  /// the orientation of a directed one.
414  template<typename Graph>
415  class UndirGraphWrapper : public GraphWrapper<Graph> {
416  public:
417    typedef typename GraphWrapper<Graph>::Node Node;
418    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
419    typedef typename GraphWrapper<Graph>::Edge Edge;
420    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
421
422    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
423
424    class OutEdgeIt {
425      friend class UndirGraphWrapper<Graph>;
426      bool out_or_in; //true iff out
427      typename Graph::OutEdgeIt out;
428      typename Graph::InEdgeIt in;
429    public:
430      OutEdgeIt() { }
431      OutEdgeIt(const Invalid& i) : Edge(i) { }
432      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
433        out_or_in=true; _G.graph->first(out, _n);
434        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
435      }
436      operator Edge() const {
437        if (out_or_in) return Edge(out); else return Edge(in);
438      }
439    };
440
441//FIXME InEdgeIt
442    typedef OutEdgeIt InEdgeIt;
443
444    using GraphWrapper<Graph>::first;
445//     NodeIt& first(NodeIt& i) const {
446//       i=NodeIt(*this); return i;
447//     }
448    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
449      i=OutEdgeIt(*this, p); return i;
450    }
451//FIXME
452//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
453//       i=InEdgeIt(*this, p); return i;
454//     }
455//     EdgeIt& first(EdgeIt& i) const {
456//       i=EdgeIt(*this); return i;
457//     }
458
459    using GraphWrapper<Graph>::next;
460//     NodeIt& next(NodeIt& n) const {
461//       GraphWrapper<Graph>::next(n);
462//       return n;
463//     }
464    OutEdgeIt& next(OutEdgeIt& e) const {
465      if (e.out_or_in) {
466        typename Graph::Node n=graph->tail(e.out);
467        graph->next(e.out);
468        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
469      } else {
470        graph->next(e.in);
471      }
472      return e;
473    }
474    //FIXME InEdgeIt
475//     EdgeIt& next(EdgeIt& e) const {
476//       GraphWrapper<Graph>::next(n);
477// //      graph->next(e.e);
478//       return e;
479//     }
480
481    Node aNode(const OutEdgeIt& e) const {
482      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
483    Node bNode(const OutEdgeIt& e) const {
484      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
485  };
486
487  /// A wrapper for composing the residual graph for directed flow and circulation problems.
488
489  /// A wrapper for composing the residual graph for directed flow and circulation problems.
490  template<typename Graph, typename Number,
491           typename CapacityMap, typename FlowMap>
492  class ResGraphWrapper : public GraphWrapper<Graph> {
493  protected:
494    const CapacityMap* capacity;
495    FlowMap* flow;
496  public:
497
498    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
499                    FlowMap& _flow) :
500      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
501
502    class Edge;
503    class OutEdgeIt;
504    friend class Edge;
505    friend class OutEdgeIt;
506
507    typedef typename GraphWrapper<Graph>::Node Node;
508    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
509    class Edge : public Graph::Edge {
510      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
511    protected:
512      bool forward; //true, iff forward
513//      typename Graph::Edge e;
514    public:
515      Edge() { }
516      Edge(const typename Graph::Edge& _e, bool _forward) :
517        Graph::Edge(_e), forward(_forward) { }
518      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
519//the unique invalid iterator
520      friend bool operator==(const Edge& u, const Edge& v) {
521        return (v.forward==u.forward &&
522                static_cast<typename Graph::Edge>(u)==
523                static_cast<typename Graph::Edge>(v));
524      }
525      friend bool operator!=(const Edge& u, const Edge& v) {
526        return (v.forward!=u.forward ||
527                static_cast<typename Graph::Edge>(u)!=
528                static_cast<typename Graph::Edge>(v));
529      }
530    };
531
532    class OutEdgeIt {
533      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
534    protected:
535      typename Graph::OutEdgeIt out;
536      typename Graph::InEdgeIt in;
537      bool forward;
538    public:
539      OutEdgeIt() { }
540      //FIXME
541//      OutEdgeIt(const Edge& e) : Edge(e) { }
542      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
543//the unique invalid iterator
544      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
545        forward=true;
546        resG.graph->first(out, v);
547        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
548        if (!resG.graph->valid(out)) {
549          forward=false;
550          resG.graph->first(in, v);
551          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
552        }
553      }
554      operator Edge() const {
555//      Edge e;
556//      e.forward=this->forward;
557//      if (this->forward) e=out; else e=in;
558//      return e;
559        if (this->forward)
560          return Edge(out, this->forward);
561        else
562          return Edge(in, this->forward);
563      }
564    };
565
566    class InEdgeIt {
567      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
568    protected:
569      typename Graph::OutEdgeIt out;
570      typename Graph::InEdgeIt in;
571      bool forward;
572    public:
573      InEdgeIt() { }
574      //FIXME
575//      OutEdgeIt(const Edge& e) : Edge(e) { }
576      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
577//the unique invalid iterator
578      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
579        forward=true;
580        resG.graph->first(in, v);
581        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
582        if (!resG.graph->valid(in)) {
583          forward=false;
584          resG.graph->first(out, v);
585          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
586        }
587      }
588      operator Edge() const {
589//      Edge e;
590//      e.forward=this->forward;
591//      if (this->forward) e=out; else e=in;
592//      return e;
593        if (this->forward)
594          return Edge(in, this->forward);
595        else
596          return Edge(out, this->forward);
597      }
598    };
599
600    class EdgeIt {
601      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
602    protected:
603      typename Graph::EdgeIt e;
604      bool forward;
605    public:
606      EdgeIt() { }
607      EdgeIt(const Invalid& i) : e(i), forward(false) { }
608      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
609        forward=true;
610        resG.graph->first(e);
611        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
612        if (!resG.graph->valid(e)) {
613          forward=false;
614          resG.graph->first(e);
615          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
616        }
617      }
618      operator Edge() const {
619        return Edge(e, this->forward);
620      }
621    };
622
623    using GraphWrapper<Graph>::first;
624//     NodeIt& first(NodeIt& i) const {
625//       i=NodeIt(*this); return i;
626//     }
627    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
628      i=OutEdgeIt(*this, p); return i;
629    }
630//    FIXME not tested
631    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
632      i=InEdgeIt(*this, p); return i;
633    }
634    EdgeIt& first(EdgeIt& i) const {
635      i=EdgeIt(*this); return i;
636    }
637
638    using GraphWrapper<Graph>::next;
639//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
640    OutEdgeIt& next(OutEdgeIt& e) const {
641      if (e.forward) {
642        Node v=graph->aNode(e.out);
643        graph->next(e.out);
644        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
645        if (!graph->valid(e.out)) {
646          e.forward=false;
647          graph->first(e.in, v);
648          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
649        }
650      } else {
651        graph->next(e.in);
652        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
653      }
654      return e;
655    }
656//     FIXME Not tested
657    InEdgeIt& next(InEdgeIt& e) const {
658      if (e.forward) {
659        Node v=graph->aNode(e.in);
660        graph->next(e.in);
661        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
662        if (!graph->valid(e.in)) {
663          e.forward=false;
664          graph->first(e.out, v);
665          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
666        }
667      } else {
668        graph->next(e.out);
669        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
670      }
671      return e;
672    }
673    EdgeIt& next(EdgeIt& e) const {
674      if (e.forward) {
675        graph->next(e.e);
676        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
677        if (!graph->valid(e.e)) {
678          e.forward=false;
679          graph->first(e.e);
680          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
681        }
682      } else {
683        graph->next(e.e);
684        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
685      }
686      return e;
687    }
688
689    Node tail(Edge e) const {
690      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
691    Node head(Edge e) const {
692      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
693
694    Node aNode(OutEdgeIt e) const {
695      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
696    Node bNode(OutEdgeIt e) const {
697      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
698
699//    int nodeNum() const { return graph->nodeNum(); }
700    //FIXME
701    void edgeNum() const { }
702    //int edgeNum() const { return graph->edgeNum(); }
703
704
705//    int id(Node v) const { return graph->id(v); }
706
707    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
708    bool valid(Edge e) const {
709      return graph->valid(e);
710        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
711    }
712
713    void augment(const Edge& e, Number a) const {
714      if (e.forward)
715//      flow->set(e.out, flow->get(e.out)+a);
716        flow->set(e, (*flow)[e]+a);
717      else
718//      flow->set(e.in, flow->get(e.in)-a);
719        flow->set(e, (*flow)[e]-a);
720    }
721
722    Number resCap(const Edge& e) const {
723      if (e.forward)
724//      return (capacity->get(e.out)-flow->get(e.out));
725        return ((*capacity)[e]-(*flow)[e]);
726      else
727//      return (flow->get(e.in));
728        return ((*flow)[e]);
729    }
730
731//     Number resCap(typename Graph::OutEdgeIt out) const {
732// //      return (capacity->get(out)-flow->get(out));
733//       return ((*capacity)[out]-(*flow)[out]);
734//     }
735
736//     Number resCap(typename Graph::InEdgeIt in) const {
737// //      return (flow->get(in));
738//       return ((*flow)[in]);
739//     }
740
741    template <typename T>
742    class EdgeMap {
743      typename Graph::EdgeMap<T> forward_map, backward_map;
744    public:
745      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
746      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
747      void set(Edge e, T a) {
748        if (e.forward)
749          forward_map.set(e.out, a);
750        else
751          backward_map.set(e.in, a);
752      }
753      T operator[](Edge e) const {
754        if (e.forward)
755          return forward_map[e.out];
756        else
757          return backward_map[e.in];
758      }
759//       T get(Edge e) const {
760//      if (e.out_or_in)
761//        return forward_map.get(e.out);
762//      else
763//        return backward_map.get(e.in);
764//       }
765    };
766  };
767
768  /// ErasingFirstGraphWrapper for blocking flows.
769
770  /// ErasingFirstGraphWrapper for blocking flows.
771  template<typename Graph, typename FirstOutEdgesMap>
772  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
773  protected:
774    FirstOutEdgesMap* first_out_edges;
775  public:
776    ErasingFirstGraphWrapper(Graph& _graph,
777                             FirstOutEdgesMap& _first_out_edges) :
778      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
779
780    typedef typename GraphWrapper<Graph>::Node Node;
781//     class NodeIt {
782//       friend class GraphWrapper<Graph>;
783//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
784//       typename Graph::NodeIt n;
785//      public:
786//       NodeIt() { }
787//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
788//       NodeIt(const Invalid& i) : n(i) { }
789//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
790//      n(*(_G.graph)) { }
791//       operator Node() const { return Node(typename Graph::Node(n)); }
792//     };
793    typedef typename GraphWrapper<Graph>::Edge Edge;
794    class OutEdgeIt {
795      friend class GraphWrapper<Graph>;
796      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
797//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
798      typename Graph::OutEdgeIt e;
799    public:
800      OutEdgeIt() { }
801      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
802      OutEdgeIt(const Invalid& i) : e(i) { }
803      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
804                const Node& _n) :
805        e((*_G.first_out_edges)[_n]) { }
806      operator Edge() const { return Edge(typename Graph::Edge(e)); }
807    };
808    class InEdgeIt {
809      friend class GraphWrapper<Graph>;
810      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
811//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
812      typename Graph::InEdgeIt e;
813    public:
814      InEdgeIt() { }
815      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
816      InEdgeIt(const Invalid& i) : e(i) { }
817      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
818               const Node& _n) :
819        e(*(_G.graph), typename Graph::Node(_n)) { }
820      operator Edge() const { return Edge(typename Graph::Edge(e)); }
821    };
822    //typedef typename Graph::SymEdgeIt SymEdgeIt;
823    class EdgeIt {
824      friend class GraphWrapper<Graph>;
825      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
826//      typedef typename Graph::EdgeIt GraphEdgeIt;
827      typename Graph::EdgeIt e;
828    public:
829      EdgeIt() { }
830      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
831      EdgeIt(const Invalid& i) : e(i) { }
832      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
833        e(*(_G.graph)) { }
834      operator Edge() const { return Edge(typename Graph::Edge(e)); }
835    };
836
837    using GraphWrapper<Graph>::first;
838//     NodeIt& first(NodeIt& i) const {
839//       i=NodeIt(*this); return i;
840//     }
841    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
842      i=OutEdgeIt(*this, p); return i;
843    }
844    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
845      i=InEdgeIt(*this, p); return i;
846    }
847    EdgeIt& first(EdgeIt& i) const {
848      i=EdgeIt(*this); return i;
849    }
850
851    using GraphWrapper<Graph>::next;
852//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
853    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
854    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
855    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
856
857    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
858    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
859    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
860    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
861
862    void erase(const OutEdgeIt& e) const {
863      OutEdgeIt f=e;
864      this->next(f);
865      first_out_edges->set(this->tail(e), f.e);
866    }
867  };
868
869  /// A wrapper for composing a bipartite graph.
870  /// \c _graph have to be a reference to an undirected graph \c Graph
871  /// and
872  /// \c _s_false_t_true_map is an \c IterableBoolMap
873  /// reference containing the elements for the
874  /// color classes S and T.
875  /// It results in a directed graph such that the edges are oriented from
876  /// S to T.
877  template<typename Graph>
878  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
879    typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
880    SFalseTTrueMap* s_false_t_true_map;
881
882  public:
883    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
884      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
885    }
886    typedef typename GraphWrapper<Graph>::Node Node;
887    //using GraphWrapper<Graph>::NodeIt;
888    typedef typename GraphWrapper<Graph>::Edge Edge;
889    //using GraphWrapper<Graph>::EdgeIt;
890    class SNodeIt {
891      Node n;
892    public:
893      SNodeIt() { }
894      SNodeIt(const Invalid& i) : n(i) { }
895      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
896        _G.s_false_t_true_map->first(n, false);
897      }
898      operator Node() const { return n; }
899    };
900    class TNodeIt {
901      Node n;
902    public:
903      TNodeIt() { }
904      TNodeIt(const Invalid& i) : n(i) { }
905      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
906        _G.s_false_t_true_map->first(n, true);
907      }
908      operator Node() const { return n; }
909    };
910    class OutEdgeIt {
911    public:
912      typename Graph::OutEdgeIt e;
913    public:
914      OutEdgeIt() { }
915      OutEdgeIt(const Invalid& i) : e(i) { }
916      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
917        if (!(*(_G.s_false_t_true_map))[_n])
918          e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
919        else
920          e=INVALID;
921      }
922      operator Edge() const { return Edge(typename Graph::Edge(e)); }
923    };
924    class InEdgeIt {
925    public:
926      typename Graph::InEdgeIt e;
927    public:
928      InEdgeIt() { }
929      InEdgeIt(const Invalid& i) : e(i) { }
930      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
931        if ((*(_G.s_false_t_true_map))[_n])
932          e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
933        else
934          e=INVALID;
935      }
936      operator Edge() const { return Edge(typename Graph::Edge(e)); }
937    };
938
939    using GraphWrapper<Graph>::first;
940    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
941    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
942
943    using GraphWrapper<Graph>::next;
944    SNodeIt& next(SNodeIt& n) const {
945      this->s_false_t_true_map->next(n); return n;
946    }
947    TNodeIt& next(TNodeIt& n) const {
948      this->s_false_t_true_map->next(n); return n;
949    }
950
951    Node tail(const Edge& e) {
952      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
953        return Node(this->graph->tail(e));
954      else
956    }
957    Node head(const Edge& e) {
958      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
960      else
961        return Node(this->graph->tail(e));
962    }
963
964    Node aNode(const OutEdgeIt& e) const {
965      return Node(this->graph->aNode(e.e));
966    }
967    Node aNode(const InEdgeIt& e) const {
968      return Node(this->graph->aNode(e.e));
969    }
970    Node bNode(const OutEdgeIt& e) const {
971      return Node(this->graph->bNode(e.e));
972    }
973    Node bNode(const InEdgeIt& e) const {
974      return Node(this->graph->bNode(e.e));
975    }
976  };
977
978
979
980//   /// experimentral, do not try it.
981//   template<typename Graph>
982//   class stGraphWrapper : public GraphWrapper<Graph> {
983//   public:
984//     class Node;
985//     class NodeIt;
986//     class Edge;
987//     class OutEdgeIt;
988//     class InEdgeIt;
989//     class EdgeIt;
990
991//     const Node s;
992//     const Node t;
993
994//     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),
995//                                  s(INVALID, 1), t(INVALID, 2) { }
996
997//     class Node : public Graph::Node {
998//       friend class GraphWrapper<Graph>;
999//       friend class stGraphWrapper<Graph>;
1000//     protected:
1001//       int spec; //0 if real node, 1 iff s, 2 iff t
1002//     public:
1003//       Node() { }
1004//       Node(const typename Graph::Node& _n, int _spec=0) :
1005//      Graph::Node(_n), spec(_spec) { }
1006//       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
1007//       //invalid: (invalid, 2);
1008//     };
1009
1010//     class NodeIt {
1011//       friend class GraphWrapper<Graph>;
1012//       friend class stGraphWrapper<Graph>;
1013//       typename Graph::NodeIt n;
1014//       int spec;
1015//      public:
1016//       NodeIt() { }
1017//       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :
1018//      n(_n), spec(_spec) { }
1019//       NodeIt(const Invalid& i) : n(i), spec(2) { }
1020//       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1021//      if (!_G->valid(n)) spec=1;
1022//       }
1023//       operator Node() const { return Node(n, spec); }
1024//     };
1025// //    typedef typename Graph::Edge Edge;
1026//     class Edge : public Graph::Edge {
1027//       friend class GraphWrapper<Graph>;
1028//       friend class stGraphWrapper<Graph>;
1029//       Node tail_spec;
1031//     public:
1032//       Edge() { }
1033//       Edge(const typename Graph::Edge& _e) :
1034//      Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {
1035//      //a tail-t es a head-et real node-ra csinaljuk
1036//       }
1037//       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
1038//     };
1039//     class OutEdgeIt {
1040//       friend class GraphWrapper<Graph>;
1041//       friend class stGraphWrapper<Graph>;
1042//       typename Graph::OutEdgeIt e;
1043//       Node tail_spec;
1045//     public:
1046//       OutEdgeIt() { }
1047//       OutEdgeIt(const typename Graph::OutEdgeIt& _e) :
1048//      e(_e), tail_spec(i, 0), head_spec(i, 0) {
1049//      //a tail-t es a head-et real node-ra csinaljuk
1050//       }
1051//       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
1052//       //invalid: (barmi, 0, 2)
1053//       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
1054//      switch (_n.spec) {
1055//      case 0 :
1056//        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
1057//        _tail.spec=0;
1059//        if (!_G.graph->valid(e)) spec=1;
1060//        break;
1061//      case 1:
1062//        e=INVALID;
1063//        _tail.spec=1;
1066//        break;
1067//      };
1068
1069//        }
1070//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1071//     };
1072//     class InEdgeIt {
1073//       friend class GraphWrapper<Graph>;
1074//       typename Graph::InEdgeIt e;
1075//     public:
1076//       InEdgeIt() { }
1077//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1078//       InEdgeIt(const Invalid& i) : e(i) { }
1079//       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
1080//      e(*(_G.graph), typename Graph::Node(_n)) { }
1081//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1082//     };
1083//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
1084//     class EdgeIt {
1085//       friend class GraphWrapper<Graph>;
1086//       typename Graph::EdgeIt e;
1087//     public:
1088//       EdgeIt() { }
1089//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1090//       EdgeIt(const Invalid& i) : e(i) { }
1091//       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
1092//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1093//     };
1094
1095//     NodeIt& first(NodeIt& i) const {
1096//       i=NodeIt(*this); return i;
1097//     }
1098//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1099//       i=OutEdgeIt(*this, p); return i;
1100//     }
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//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1109//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1110//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1111//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
1112
1113//     Node head(const Edge& e) const {
1115//     Node tail(const Edge& e) const {
1116//       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1117
1118//     bool valid(const Node& n) const {
1119//       return graph->valid(static_cast<typename Graph::Node>(n)); }
1120//     bool valid(const Edge& e) const {
1121//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
1122
1123//     int nodeNum() const { return graph->nodeNum(); }
1124//     int edgeNum() const { return graph->edgeNum(); }
1125
1126//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1127//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1128//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1129//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1130
1134
1135//     void erase(const Node& i) const { graph->erase(i); }
1136//     void erase(const Edge& i) const { graph->erase(i); }
1137
1138//     void clear() const { graph->clear(); }
1139
1140//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1141//     public:
1142//       NodeMap(const GraphWrapper<Graph>& _G) :
1143//      Graph::NodeMap<T>(*(_G.graph)) { }
1144//       NodeMap(const GraphWrapper<Graph>& _G, T a) :
1145//      Graph::NodeMap<T>(*(_G.graph), a) { }
1146//     };
1147
1148//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1149//     public:
1150//       EdgeMap(const GraphWrapper<Graph>& _G) :
1151//      Graph::EdgeMap<T>(*(_G.graph)) { }
1152//       EdgeMap(const GraphWrapper<Graph>& _G, T a) :
1153//      Graph::EdgeMap<T>(*(_G.graph), a) { }
1154//     };
1155//   };
1156
1157} //namespace hugo
1158
1159#endif //HUGO_GRAPH_WRAPPER_H
1160
Note: See TracBrowser for help on using the repository browser.