Last change on this file since 611:83530dad618a was 594:23a608ba40ab, checked in by Alpar Juttner, 17 years ago

Spell check.

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