COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 573:0f6f4eb7abe9

Last change on this file since 573:0f6f4eb7abe9 was 572:e9ed28955421, checked in by marci, 17 years ago

Edge opposite(const Edge&) in BidirGaphWrapper?<Graph>

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