# source:lemon-0.x/src/hugo/graph_wrapper.h@590:5c1465127b79

Last change on this file since 590:5c1465127b79 was 589:d89575370bcb, checked in by Alpar Juttner, 17 years ago

doc

File size: 42.6 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 {
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  ///
477  ///\author Marton Makai
478  template<typename Graph>
479  class UndirGraphWrapper : public GraphWrapper<Graph> {
480  protected:
481    UndirGraphWrapper() : GraphWrapper<Graph>() { }
482
483  public:
484    typedef typename GraphWrapper<Graph>::Node Node;
485    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
486    typedef typename GraphWrapper<Graph>::Edge Edge;
487    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
488
489    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
490
491    class OutEdgeIt {
492      friend class UndirGraphWrapper<Graph>;
493      bool out_or_in; //true iff out
494      typename Graph::OutEdgeIt out;
495      typename Graph::InEdgeIt in;
496    public:
497      OutEdgeIt() { }
498      OutEdgeIt(const Invalid& i) : Edge(i) { }
499      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
500        out_or_in=true; _G.graph->first(out, _n);
501        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
502      }
503      operator Edge() const {
504        if (out_or_in) return Edge(out); else return Edge(in);
505      }
506    };
507
508//FIXME InEdgeIt
509    typedef OutEdgeIt InEdgeIt;
510
511    using GraphWrapper<Graph>::first;
512//     NodeIt& first(NodeIt& i) const {
513//       i=NodeIt(*this); return i;
514//     }
515    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
516      i=OutEdgeIt(*this, p); return i;
517    }
518//FIXME
519//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
520//       i=InEdgeIt(*this, p); return i;
521//     }
522//     EdgeIt& first(EdgeIt& i) const {
523//       i=EdgeIt(*this); return i;
524//     }
525
526    using GraphWrapper<Graph>::next;
527//     NodeIt& next(NodeIt& n) const {
528//       GraphWrapper<Graph>::next(n);
529//       return n;
530//     }
531    OutEdgeIt& next(OutEdgeIt& e) const {
532      if (e.out_or_in) {
533        typename Graph::Node n=this->graph->tail(e.out);
534        this->graph->next(e.out);
535        if (!this->graph->valid(e.out)) {
536          e.out_or_in=false; this->graph->first(e.in, n); }
537      } else {
538        this->graph->next(e.in);
539      }
540      return e;
541    }
542    //FIXME InEdgeIt
543//     EdgeIt& next(EdgeIt& e) const {
544//       GraphWrapper<Graph>::next(n);
545// //      graph->next(e.e);
546//       return e;
547//     }
548
549    Node aNode(const OutEdgeIt& e) const {
550      if (e.out_or_in) return this->graph->tail(e); else
551        return this->graph->head(e); }
552    Node bNode(const OutEdgeIt& e) const {
553      if (e.out_or_in) return this->graph->head(e); else
554        return this->graph->tail(e); }
555  };
556
557
558
559  /// An undirected graph template
560  template<typename Graph>
561  class UndirGraph : public UndirGraphWrapper<Graph> {
562    typedef UndirGraphWrapper<Graph> Parent;
563  protected:
564    Graph gr;
565  public:
566    UndirGraph() : UndirGraphWrapper<Graph>() {
567      Parent::setGraph(gr);
568    }
569  };
570
571
572  /// A wrapper for composing bidirected graph from a directed one.
573  /// experimental, for fezso's sake.
574
575  /// A wrapper for composing bidirected graph from a directed one.
576  /// experimental, for fezso's sake.
577  template<typename Graph>
578  class BidirGraphWrapper : public GraphWrapper<Graph> {
579  protected:
580    //const CapacityMap* capacity;
581    //FlowMap* flow;
582
583    BidirGraphWrapper() : GraphWrapper<Graph>()/*,
584                                                 capacity(0), flow(0)*/ { }
585//     void setCapacityMap(const CapacityMap& _capacity) {
586//       capacity=&_capacity;
587//     }
588//     void setFlowMap(FlowMap& _flow) {
589//       flow=&_flow;
590//     }
591
592  public:
593
594    BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
595                                     FlowMap& _flow*/) :
596      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
597
598    class Edge;
599    class OutEdgeIt;
600    friend class Edge;
601    friend class OutEdgeIt;
602
603    typedef typename GraphWrapper<Graph>::Node Node;
604    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
605    class Edge : public Graph::Edge {
606      friend class BidirGraphWrapper<Graph>;
607    protected:
608      bool backward; //true, iff backward
609//      typename Graph::Edge e;
610    public:
611      Edge() { }
612      Edge(const typename Graph::Edge& _e, bool _backward) :
613        Graph::Edge(_e), backward(_backward) { }
614      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
615//the unique invalid iterator
616      friend bool operator==(const Edge& u, const Edge& v) {
617        return (v.backward==u.backward &&
618                static_cast<typename Graph::Edge>(u)==
619                static_cast<typename Graph::Edge>(v));
620      }
621      friend bool operator!=(const Edge& u, const Edge& v) {
622        return (v.backward!=u.backward ||
623                static_cast<typename Graph::Edge>(u)!=
624                static_cast<typename Graph::Edge>(v));
625      }
626    };
627
628    class OutEdgeIt {
629      friend class BidirGraphWrapper<Graph>;
630    protected:
631      typename Graph::OutEdgeIt out;
632      typename Graph::InEdgeIt in;
633      bool backward;
634    public:
635      OutEdgeIt() { }
636      //FIXME
637//      OutEdgeIt(const Edge& e) : Edge(e) { }
638      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
639//the unique invalid iterator
640      OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
641        backward=false;
642        _G.graph->first(out, v);
643        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
644        if (!_G.graph->valid(out)) {
645          backward=true;
646          _G.graph->first(in, v);
647          while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
648        }
649      }
650      operator Edge() const {
651//      Edge e;
652//      e.forward=this->forward;
653//      if (this->forward) e=out; else e=in;
654//      return e;
655        if (this->backward)
656          return Edge(in, this->backward);
657        else
658          return Edge(out, this->backward);
659      }
660    };
661
662    class InEdgeIt {
663      friend class BidirGraphWrapper<Graph>;
664    protected:
665      typename Graph::OutEdgeIt out;
666      typename Graph::InEdgeIt in;
667      bool backward;
668    public:
669      InEdgeIt() { }
670      //FIXME
671//      OutEdgeIt(const Edge& e) : Edge(e) { }
672      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
673//the unique invalid iterator
674      InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
675        backward=false;
676        _G.graph->first(in, v);
677        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
678        if (!_G.graph->valid(in)) {
679          backward=true;
680          _G.graph->first(out, v);
681          while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
682        }
683      }
684      operator Edge() const {
685//      Edge e;
686//      e.forward=this->forward;
687//      if (this->forward) e=out; else e=in;
688//      return e;
689        if (this->backward)
690          return Edge(out, this->backward);
691        else
692          return Edge(in, this->backward);
693      }
694    };
695
696    class EdgeIt {
697      friend class BidirGraphWrapper<Graph>;
698    protected:
699      typename Graph::EdgeIt e;
700      bool backward;
701    public:
702      EdgeIt() { }
703      EdgeIt(const Invalid& i) : e(i), backward(true) { }
704      EdgeIt(const BidirGraphWrapper<Graph>& _G) {
705        backward=false;
706        _G.graph->first(e);
707        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
708        if (!_G.graph->valid(e)) {
709          backward=true;
710          _G.graph->first(e);
711          while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
712        }
713      }
714      operator Edge() const {
715        return Edge(e, this->backward);
716      }
717    };
718
719    using GraphWrapper<Graph>::first;
720//     NodeIt& first(NodeIt& i) const {
721//       i=NodeIt(*this); return i;
722//     }
723    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
724      i=OutEdgeIt(*this, p); return i;
725    }
726//    FIXME not tested
727    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
728      i=InEdgeIt(*this, p); return i;
729    }
730    EdgeIt& first(EdgeIt& i) const {
731      i=EdgeIt(*this); return i;
732    }
733
734    using GraphWrapper<Graph>::next;
735//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
736    OutEdgeIt& next(OutEdgeIt& e) const {
737      if (!e.backward) {
738        Node v=this->graph->aNode(e.out);
739        this->graph->next(e.out);
740        while(this->graph->valid(e.out) && !enabled(e)) {
741          this->graph->next(e.out); }
742        if (!this->graph->valid(e.out)) {
743          e.backward=true;
744          this->graph->first(e.in, v);
745          while(this->graph->valid(e.in) && !enabled(e)) {
746            this->graph->next(e.in); }
747        }
748      } else {
749        this->graph->next(e.in);
750        while(this->graph->valid(e.in) && !enabled(e)) {
751          this->graph->next(e.in); }
752      }
753      return e;
754    }
755//     FIXME Not tested
756    InEdgeIt& next(InEdgeIt& e) const {
757      if (!e.backward) {
758        Node v=this->graph->aNode(e.in);
759        this->graph->next(e.in);
760        while(this->graph->valid(e.in) && !enabled(e)) {
761          this->graph->next(e.in); }
762        if (!this->graph->valid(e.in)) {
763          e.backward=true;
764          this->graph->first(e.out, v);
765          while(this->graph->valid(e.out) && !enabled(e)) {
766            this->graph->next(e.out); }
767        }
768      } else {
769        this->graph->next(e.out);
770        while(this->graph->valid(e.out) && !enabled(e)) {
771          this->graph->next(e.out); }
772      }
773      return e;
774    }
775    EdgeIt& next(EdgeIt& e) const {
776      if (!e.backward) {
777        this->graph->next(e.e);
778        while(this->graph->valid(e.e) && !enabled(e)) {
779          this->graph->next(e.e); }
780        if (!this->graph->valid(e.e)) {
781          e.backward=true;
782          this->graph->first(e.e);
783          while(this->graph->valid(e.e) && !enabled(e)) {
784            this->graph->next(e.e); }
785        }
786      } else {
787        this->graph->next(e.e);
788        while(this->graph->valid(e.e) && !enabled(e)) {
789          this->graph->next(e.e); }
790      }
791      return e;
792    }
793
794    Node tail(Edge e) const {
795      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
796    Node head(Edge e) const {
797      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
798
799    Node aNode(OutEdgeIt e) const {
800      return ((!e.backward) ? this->graph->aNode(e.out) :
801              this->graph->aNode(e.in)); }
802    Node bNode(OutEdgeIt e) const {
803      return ((!e.backward) ? this->graph->bNode(e.out) :
804              this->graph->bNode(e.in)); }
805
806    Node aNode(InEdgeIt e) const {
807      return ((!e.backward) ? this->graph->aNode(e.in) :
808              this->graph->aNode(e.out)); }
809    Node bNode(InEdgeIt e) const {
810      return ((!e.backward) ? this->graph->bNode(e.in) :
811              this->graph->bNode(e.out)); }
812
813    /// Gives back the opposite edge.
814    Edge opposite(const Edge& e) const {
815      Edge f=e;
816      f.backward=!f.backward;
817      return f;
818    }
819
820//    int nodeNum() const { return graph->nodeNum(); }
821    //FIXME
822    void edgeNum() const { }
823    //int edgeNum() const { return graph->edgeNum(); }
824
825
826//    int id(Node v) const { return graph->id(v); }
827
828    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
829    bool valid(Edge e) const {
830      return this->graph->valid(e);
831        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
832    }
833
834    bool forward(const Edge& e) const { return !e.backward; }
835    bool backward(const Edge& e) const { return e.backward; }
836
837//     void augment(const Edge& e, Number a) const {
838//       if (!e.backward)
839// //   flow->set(e.out, flow->get(e.out)+a);
840//      flow->set(e, (*flow)[e]+a);
841//       else
842// //   flow->set(e.in, flow->get(e.in)-a);
843//      flow->set(e, (*flow)[e]-a);
844//     }
845
846    bool enabled(const Edge& e) const {
847      if (!e.backward)
848//      return (capacity->get(e.out)-flow->get(e.out));
849        //return ((*capacity)[e]-(*flow)[e]);
850        return true;
851      else
852//      return (flow->get(e.in));
853        //return ((*flow)[e]);
854        return true;
855    }
856
857//     Number enabled(typename Graph::OutEdgeIt out) const {
858// //      return (capacity->get(out)-flow->get(out));
859//       return ((*capacity)[out]-(*flow)[out]);
860//     }
861
862//     Number enabled(typename Graph::InEdgeIt in) const {
863// //      return (flow->get(in));
864//       return ((*flow)[in]);
865//     }
866
867    template <typename T>
868    class EdgeMap {
869      typename Graph::template EdgeMap<T> forward_map, backward_map;
870    public:
871      EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
872      EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
873      void set(Edge e, T a) {
874        if (!e.backward)
875          forward_map.set(e.out, a);
876        else
877          backward_map.set(e.in, a);
878      }
879      T operator[](Edge e) const {
880        if (!e.backward)
881          return forward_map[e.out];
882        else
883          return backward_map[e.in];
884      }
885//       T get(Edge e) const {
886//      if (e.out_or_in)
887//        return forward_map.get(e.out);
888//      else
889//        return backward_map.get(e.in);
890//       }
891    };
892  };
893
894
895
896  /// A wrapper for composing the residual graph for directed flow and circulation problems.
897
898  /// A wrapper for composing the residual graph for directed flow and circulation problems.
899  template<typename Graph, typename Number,
900           typename CapacityMap, typename FlowMap>
901  class ResGraphWrapper : public GraphWrapper<Graph> {
902  protected:
903    const CapacityMap* capacity;
904    FlowMap* flow;
905
906    ResGraphWrapper() : GraphWrapper<Graph>(0),
907                        capacity(0), flow(0) { }
908    void setCapacityMap(const CapacityMap& _capacity) {
909      capacity=&_capacity;
910    }
911    void setFlowMap(FlowMap& _flow) {
912      flow=&_flow;
913    }
914
915  public:
916
917    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
918                    FlowMap& _flow) :
919      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
920
921    class Edge;
922    class OutEdgeIt;
923    friend class Edge;
924    friend class OutEdgeIt;
925
926    typedef typename GraphWrapper<Graph>::Node Node;
927    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
928    class Edge : public Graph::Edge {
929      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
930    protected:
931      bool backward; //true, iff backward
932//      typename Graph::Edge e;
933    public:
934      Edge() { }
935      Edge(const typename Graph::Edge& _e, bool _backward) :
936        Graph::Edge(_e), backward(_backward) { }
937      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
938//the unique invalid iterator
939      friend bool operator==(const Edge& u, const Edge& v) {
940        return (v.backward==u.backward &&
941                static_cast<typename Graph::Edge>(u)==
942                static_cast<typename Graph::Edge>(v));
943      }
944      friend bool operator!=(const Edge& u, const Edge& v) {
945        return (v.backward!=u.backward ||
946                static_cast<typename Graph::Edge>(u)!=
947                static_cast<typename Graph::Edge>(v));
948      }
949    };
950
951    class OutEdgeIt {
952      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
953    protected:
954      typename Graph::OutEdgeIt out;
955      typename Graph::InEdgeIt in;
956      bool backward;
957    public:
958      OutEdgeIt() { }
959      //FIXME
960//      OutEdgeIt(const Edge& e) : Edge(e) { }
961      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
962//the unique invalid iterator
963      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
964        backward=false;
965        _G.graph->first(out, v);
966        while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
967        if (!_G.graph->valid(out)) {
968          backward=true;
969          _G.graph->first(in, v);
970          while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
971        }
972      }
973      operator Edge() const {
974//      Edge e;
975//      e.forward=this->forward;
976//      if (this->forward) e=out; else e=in;
977//      return e;
978        if (this->backward)
979          return Edge(in, this->backward);
980        else
981          return Edge(out, this->backward);
982      }
983    };
984
985    class InEdgeIt {
986      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
987    protected:
988      typename Graph::OutEdgeIt out;
989      typename Graph::InEdgeIt in;
990      bool backward;
991    public:
992      InEdgeIt() { }
993      //FIXME
994//      OutEdgeIt(const Edge& e) : Edge(e) { }
995      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
996//the unique invalid iterator
997      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
998        backward=false;
999        _G.graph->first(in, v);
1000        while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1001        if (!_G.graph->valid(in)) {
1002          backward=true;
1003          _G.graph->first(out, v);
1004          while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1005        }
1006      }
1007      operator Edge() const {
1008//      Edge e;
1009//      e.forward=this->forward;
1010//      if (this->forward) e=out; else e=in;
1011//      return e;
1012        if (this->backward)
1013          return Edge(out, this->backward);
1014        else
1015          return Edge(in, this->backward);
1016      }
1017    };
1018
1019    class EdgeIt {
1020      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1021    protected:
1022      typename Graph::EdgeIt e;
1023      bool backward;
1024    public:
1025      EdgeIt() { }
1026      EdgeIt(const Invalid& i) : e(i), backward(true) { }
1027      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1028        backward=false;
1029        _G.graph->first(e);
1030        while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1031        if (!_G.graph->valid(e)) {
1032          backward=true;
1033          _G.graph->first(e);
1034          while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1035        }
1036      }
1037      operator Edge() const {
1038        return Edge(e, this->backward);
1039      }
1040    };
1041
1042    using GraphWrapper<Graph>::first;
1043//     NodeIt& first(NodeIt& i) const {
1044//       i=NodeIt(*this); return i;
1045//     }
1046    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1047      i=OutEdgeIt(*this, p); return i;
1048    }
1049//    FIXME not tested
1050    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1051      i=InEdgeIt(*this, p); return i;
1052    }
1053    EdgeIt& first(EdgeIt& i) const {
1054      i=EdgeIt(*this); return i;
1055    }
1056
1057    using GraphWrapper<Graph>::next;
1058//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1059    OutEdgeIt& next(OutEdgeIt& e) const {
1060      if (!e.backward) {
1061        Node v=this->graph->aNode(e.out);
1062        this->graph->next(e.out);
1063        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1064          this->graph->next(e.out); }
1065        if (!this->graph->valid(e.out)) {
1066          e.backward=true;
1067          this->graph->first(e.in, v);
1068          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1069            this->graph->next(e.in); }
1070        }
1071      } else {
1072        this->graph->next(e.in);
1073        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1074          this->graph->next(e.in); }
1075      }
1076      return e;
1077    }
1078//     FIXME Not tested
1079    InEdgeIt& next(InEdgeIt& e) const {
1080      if (!e.backward) {
1081        Node v=this->graph->aNode(e.in);
1082        this->graph->next(e.in);
1083        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1084          this->graph->next(e.in); }
1085        if (!this->graph->valid(e.in)) {
1086          e.backward=true;
1087          this->graph->first(e.out, v);
1088          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1089            this->graph->next(e.out); }
1090        }
1091      } else {
1092        this->graph->next(e.out);
1093        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1094          this->graph->next(e.out); }
1095      }
1096      return e;
1097    }
1098    EdgeIt& next(EdgeIt& e) const {
1099      if (!e.backward) {
1100        this->graph->next(e.e);
1101        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1102          this->graph->next(e.e); }
1103        if (!this->graph->valid(e.e)) {
1104          e.backward=true;
1105          this->graph->first(e.e);
1106          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1107            this->graph->next(e.e); }
1108        }
1109      } else {
1110        this->graph->next(e.e);
1111        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1112          this->graph->next(e.e); }
1113      }
1114      return e;
1115    }
1116
1117    Node tail(Edge e) const {
1118      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1119    Node head(Edge e) const {
1120      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1121
1122    Node aNode(OutEdgeIt e) const {
1123      return ((!e.backward) ? this->graph->aNode(e.out) :
1124              this->graph->aNode(e.in)); }
1125    Node bNode(OutEdgeIt e) const {
1126      return ((!e.backward) ? this->graph->bNode(e.out) :
1127              this->graph->bNode(e.in)); }
1128
1129    Node aNode(InEdgeIt e) const {
1130      return ((!e.backward) ? this->graph->aNode(e.in) :
1131              this->graph->aNode(e.out)); }
1132    Node bNode(InEdgeIt e) const {
1133      return ((!e.backward) ? this->graph->bNode(e.in) :
1134              this->graph->bNode(e.out)); }
1135
1136//    int nodeNum() const { return graph->nodeNum(); }
1137    //FIXME
1138    void edgeNum() const { }
1139    //int edgeNum() const { return graph->edgeNum(); }
1140
1141
1142//    int id(Node v) const { return graph->id(v); }
1143
1144    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1145    bool valid(Edge e) const {
1146      return this->graph->valid(e);
1147        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1148    }
1149
1150    bool forward(const Edge& e) const { return !e.backward; }
1151    bool backward(const Edge& e) const { return e.backward; }
1152
1153    void augment(const Edge& e, Number a) const {
1154      if (!e.backward)
1155//      flow->set(e.out, flow->get(e.out)+a);
1156        flow->set(e, (*flow)[e]+a);
1157      else
1158//      flow->set(e.in, flow->get(e.in)-a);
1159        flow->set(e, (*flow)[e]-a);
1160    }
1161
1162    Number resCap(const Edge& e) const {
1163      if (!e.backward)
1164//      return (capacity->get(e.out)-flow->get(e.out));
1165        return ((*capacity)[e]-(*flow)[e]);
1166      else
1167//      return (flow->get(e.in));
1168        return ((*flow)[e]);
1169    }
1170
1171//     Number resCap(typename Graph::OutEdgeIt out) const {
1172// //      return (capacity->get(out)-flow->get(out));
1173//       return ((*capacity)[out]-(*flow)[out]);
1174//     }
1175
1176//     Number resCap(typename Graph::InEdgeIt in) const {
1177// //      return (flow->get(in));
1178//       return ((*flow)[in]);
1179//     }
1180
1181    template <typename T>
1182    class EdgeMap {
1183      typename Graph::template EdgeMap<T> forward_map, backward_map;
1184    public:
1185      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1186      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1187      void set(Edge e, T a) {
1188        if (!e.backward)
1189          forward_map.set(e.out, a);
1190        else
1191          backward_map.set(e.in, a);
1192      }
1193      T operator[](Edge e) const {
1194        if (!e.backward)
1195          return forward_map[e.out];
1196        else
1197          return backward_map[e.in];
1198      }
1199//       T get(Edge e) const {
1200//      if (e.out_or_in)
1201//        return forward_map.get(e.out);
1202//      else
1203//        return backward_map.get(e.in);
1204//       }
1205    };
1206  };
1207
1208
1209
1210  /// ErasingFirstGraphWrapper for blocking flows.
1211
1212  /// ErasingFirstGraphWrapper for blocking flows.
1213  ///
1214  ///\author Marton Makai
1215  template<typename Graph, typename FirstOutEdgesMap>
1216  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1217  protected:
1218    FirstOutEdgesMap* first_out_edges;
1219  public:
1220    ErasingFirstGraphWrapper(Graph& _graph,
1221                             FirstOutEdgesMap& _first_out_edges) :
1222      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
1223
1224    typedef typename GraphWrapper<Graph>::Node Node;
1225//     class NodeIt {
1226//       friend class GraphWrapper<Graph>;
1227//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1228//       typename Graph::NodeIt n;
1229//      public:
1230//       NodeIt() { }
1231//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
1232//       NodeIt(const Invalid& i) : n(i) { }
1233//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1234//      n(*(_G.graph)) { }
1235//       operator Node() const { return Node(typename Graph::Node(n)); }
1236//     };
1237    typedef typename GraphWrapper<Graph>::Edge Edge;
1238    class OutEdgeIt {
1239      friend class GraphWrapper<Graph>;
1240      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1241//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
1242      typename Graph::OutEdgeIt e;
1243    public:
1244      OutEdgeIt() { }
1245      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
1246      OutEdgeIt(const Invalid& i) : e(i) { }
1247      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1248                const Node& _n) :
1249        e((*_G.first_out_edges)[_n]) { }
1250      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1251    };
1252    class InEdgeIt {
1253      friend class GraphWrapper<Graph>;
1254      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1255//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
1256      typename Graph::InEdgeIt e;
1257    public:
1258      InEdgeIt() { }
1259      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1260      InEdgeIt(const Invalid& i) : e(i) { }
1261      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1262               const Node& _n) :
1263        e(*(_G.graph), typename Graph::Node(_n)) { }
1264      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1265    };
1266    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1267    class EdgeIt {
1268      friend class GraphWrapper<Graph>;
1269      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1270//      typedef typename Graph::EdgeIt GraphEdgeIt;
1271      typename Graph::EdgeIt e;
1272    public:
1273      EdgeIt() { }
1274      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1275      EdgeIt(const Invalid& i) : e(i) { }
1276      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1277        e(*(_G.graph)) { }
1278      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1279    };
1280
1281    using GraphWrapper<Graph>::first;
1282//     NodeIt& first(NodeIt& i) const {
1283//       i=NodeIt(*this); return i;
1284//     }
1285    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1286      i=OutEdgeIt(*this, p); return i;
1287    }
1288    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1289      i=InEdgeIt(*this, p); return i;
1290    }
1291    EdgeIt& first(EdgeIt& i) const {
1292      i=EdgeIt(*this); return i;
1293    }
1294
1295    using GraphWrapper<Graph>::next;
1296//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1297    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1298    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1299    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
1300
1301    Node aNode(const OutEdgeIt& e) const {
1302      return Node(this->graph->aNode(e.e)); }
1303    Node aNode(const InEdgeIt& e) const {
1304      return Node(this->graph->aNode(e.e)); }
1305    Node bNode(const OutEdgeIt& e) const {
1306      return Node(this->graph->bNode(e.e)); }
1307    Node bNode(const InEdgeIt& e) const {
1308      return Node(this->graph->bNode(e.e)); }
1309
1310    void erase(const OutEdgeIt& e) const {
1311      OutEdgeIt f=e;
1312      this->next(f);
1313      first_out_edges->set(this->tail(e), f.e);
1314    }
1315  };
1316
1317  ///@}
1318
1319} //namespace hugo
1320
1321
1322#endif //HUGO_GRAPH_WRAPPER_H
1323
Note: See TracBrowser for help on using the repository browser.