COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 650:588ff2ca55bd

Last change on this file since 650:588ff2ca55bd was 650:588ff2ca55bd, checked in by marci, 17 years ago

a

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