COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 496:7c463a7635d4

Last change on this file since 496:7c463a7635d4 was 496:7c463a7635d4, checked in by marci, 17 years ago

gw

File size: 31.7 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 <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 
92  public:
93    typedef Graph BaseGraph;
94    typedef Graph ParentGraph;
95
96//     GraphWrapper() : graph(0) { }
97    GraphWrapper(Graph& _graph) : graph(&_graph) { }
98//     void setGraph(Graph& _graph) { graph=&_graph; }
99//     Graph& getGraph() const { return *graph; }
100 
101//    typedef typename Graph::Node Node;
102    class Node : public Graph::Node {
103      friend class GraphWrapper<Graph>;
104    public:
105      Node() { }
106      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
107      Node(const Invalid& i) : Graph::Node(i) { }
108    };
109    class NodeIt {
110      friend class GraphWrapper<Graph>;
111      typename Graph::NodeIt n;
112     public:
113      NodeIt() { }
114      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
115      NodeIt(const Invalid& i) : n(i) { }
116      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
117      operator Node() const { return Node(typename Graph::Node(n)); }
118    };
119//    typedef typename Graph::Edge Edge;
120    class Edge : public Graph::Edge {
121      friend class GraphWrapper<Graph>;
122    public:
123      Edge() { }
124      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
125      Edge(const Invalid& i) : Graph::Edge(i) { }
126    };
127    class OutEdgeIt {
128      friend class GraphWrapper<Graph>;
129      typename Graph::OutEdgeIt e;
130    public:
131      OutEdgeIt() { }
132      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
133      OutEdgeIt(const Invalid& i) : e(i) { }
134      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
135        e(*(_G.graph), typename Graph::Node(_n)) { }
136      operator Edge() const { return Edge(typename Graph::Edge(e)); }
137    };
138    class InEdgeIt {
139      friend class GraphWrapper<Graph>;
140      typename Graph::InEdgeIt e;
141    public:
142      InEdgeIt() { }
143      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
144      InEdgeIt(const Invalid& i) : e(i) { }
145      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
146        e(*(_G.graph), typename Graph::Node(_n)) { }
147      operator Edge() const { return Edge(typename Graph::Edge(e)); }
148    };
149    //typedef typename Graph::SymEdgeIt SymEdgeIt;
150    class EdgeIt {
151      friend class GraphWrapper<Graph>;
152      typename Graph::EdgeIt e;
153    public:
154      EdgeIt() { }
155      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
156      EdgeIt(const Invalid& i) : e(i) { }
157      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
158      operator Edge() const { return Edge(typename Graph::Edge(e)); }
159    };
160   
161    NodeIt& first(NodeIt& i) const {
162      i=NodeIt(*this); return i;
163    }
164    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
165      i=OutEdgeIt(*this, p); return i;
166    }
167    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
168      i=InEdgeIt(*this, p); return i;
169    }
170    EdgeIt& first(EdgeIt& i) const {
171      i=EdgeIt(*this); return i;
172    }
173
174    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
175    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
176    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
177    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
178
179    Node tail(const Edge& e) const {
180      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
181    Node head(const Edge& e) const {
182      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
183
184    bool valid(const Node& n) const {
185      return graph->valid(static_cast<typename Graph::Node>(n)); }
186    bool valid(const Edge& e) const {
187      return graph->valid(static_cast<typename Graph::Edge>(e)); }
188
189    int nodeNum() const { return graph->nodeNum(); }
190    int edgeNum() const { return graph->edgeNum(); }
191 
192    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
193    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
194    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
195    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
196 
197    Node addNode() const { return Node(graph->addNode()); }
198    Edge addEdge(const Node& tail, const Node& head) const {
199      return Edge(graph->addEdge(tail, head)); }
200
201    void erase(const Node& i) const { graph->erase(i); }
202    void erase(const Edge& i) const { graph->erase(i); }
203 
204    void clear() const { graph->clear(); }
205   
206    template<typename T> class NodeMap : public Graph::template NodeMap<T> {
207      typedef typename Graph::template NodeMap<T> Parent;
208    public:
209      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
210      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
211    };
212
213    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
214      typedef typename Graph::template EdgeMap<T> Parent;
215    public:
216      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
217      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
218    };
219  };
220
221  /// A graph wrapper which reverses the orientation of the edges.
222
223  /// A graph wrapper which reverses the orientation of the edges.
224  ///
225  ///\author Marton Makai
226  template<typename Graph>
227  class RevGraphWrapper : public GraphWrapper<Graph> {
228  public:
229
230    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
231
232    typedef typename GraphWrapper<Graph>::Node Node;
233    typedef typename GraphWrapper<Graph>::Edge Edge;
234    //If Graph::OutEdgeIt is not defined
235    //and we do not want to use RevGraphWrapper::InEdgeIt,
236    //the typdef techinque does not work.
237    //Unfortunately all the typedefs are instantiated in templates.
238    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
239    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
240
241    class OutEdgeIt {
242      friend class GraphWrapper<Graph>;
243      friend class RevGraphWrapper<Graph>;
244      typename Graph::InEdgeIt e;
245    public:
246      OutEdgeIt() { }
247      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
248      OutEdgeIt(const Invalid& i) : e(i) { }
249      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
250        e(*(_G.graph), typename Graph::Node(_n)) { }
251      operator Edge() const { return Edge(typename Graph::Edge(e)); }
252    };
253    class InEdgeIt {
254      friend class GraphWrapper<Graph>;
255      friend class RevGraphWrapper<Graph>;
256      typename Graph::OutEdgeIt e;
257    public:
258      InEdgeIt() { }
259      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
260      InEdgeIt(const Invalid& i) : e(i) { }
261      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
262        e(*(_G.graph), typename Graph::Node(_n)) { }
263      operator Edge() const { return Edge(typename Graph::Edge(e)); }
264    };
265
266    using GraphWrapper<Graph>::first;
267    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
268      i=OutEdgeIt(*this, p); return i;
269    }
270    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
271      i=InEdgeIt(*this, p); return i;
272    }
273
274    using GraphWrapper<Graph>::next;
275    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
276    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
277
278    Node aNode(const OutEdgeIt& e) const {
279      return Node(this->graph->aNode(e.e)); }
280    Node aNode(const InEdgeIt& e) const {
281      return Node(this->graph->aNode(e.e)); }
282    Node bNode(const OutEdgeIt& e) const {
283      return Node(this->graph->bNode(e.e)); }
284    Node bNode(const InEdgeIt& e) const {
285      return Node(this->graph->bNode(e.e)); }
286
287    Node tail(const Edge& e) const {
288      return GraphWrapper<Graph>::head(e); }
289    Node head(const Edge& e) const {
290      return GraphWrapper<Graph>::tail(e); }
291
292  };
293
294  /// Wrapper for hiding nodes and edges from a graph.
295 
296  /// This wrapper shows a graph with filtered node-set and
297  /// edge-set. The quick brown fox iterator jumps over
298  /// the lazy dog nodes or edges if the values for them are false
299  /// in the bool maps.
300  ///
301  ///\author Marton Makai
302  template<typename Graph, typename NodeFilterMap,
303           typename EdgeFilterMap>
304  class SubGraphWrapper : public GraphWrapper<Graph> {
305  protected:
306    NodeFilterMap* node_filter_map;
307    EdgeFilterMap* edge_filter_map;
308  public:
309
310    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
311                    EdgeFilterMap& _edge_filter_map) :
312      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
313      edge_filter_map(&_edge_filter_map) { } 
314
315    typedef typename GraphWrapper<Graph>::Node Node;
316    class NodeIt {
317      friend class GraphWrapper<Graph>;
318      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
319      typename Graph::NodeIt n;
320     public:
321      NodeIt() { }
322      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
323      NodeIt(const Invalid& i) : n(i) { }
324      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
325        n(*(_G.graph)) {
326        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
327          _G.graph->next(n);
328      }
329      operator Node() const { return Node(typename Graph::Node(n)); }
330    };
331    typedef typename GraphWrapper<Graph>::Edge Edge;
332    class OutEdgeIt {
333      friend class GraphWrapper<Graph>;
334      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
335      typename Graph::OutEdgeIt e;
336    public:
337      OutEdgeIt() { }
338      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
339      OutEdgeIt(const Invalid& i) : e(i) { }
340      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
341                const Node& _n) :
342        e(*(_G.graph), typename Graph::Node(_n)) {
343        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
344          _G.graph->next(e);
345      }
346      operator Edge() const { return Edge(typename Graph::Edge(e)); }
347    };
348    class InEdgeIt {
349      friend class GraphWrapper<Graph>;
350      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
351      typename Graph::InEdgeIt e;
352    public:
353      InEdgeIt() { }
354      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
355      InEdgeIt(const Invalid& i) : e(i) { }
356      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
357               const Node& _n) :
358        e(*(_G.graph), typename Graph::Node(_n)) {
359        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
360          _G.graph->next(e);
361      }
362      operator Edge() const { return Edge(typename Graph::Edge(e)); }
363    };
364    //typedef typename Graph::SymEdgeIt SymEdgeIt;
365    class EdgeIt {
366      friend class GraphWrapper<Graph>;
367      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
368      typename Graph::EdgeIt e;
369    public:
370      EdgeIt() { }
371      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
372      EdgeIt(const Invalid& i) : e(i) { }
373      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
374        e(*(_G.graph)) {
375        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
376          _G.graph->next(e);
377      }
378      operator Edge() const { return Edge(typename Graph::Edge(e)); }
379    };
380
381    NodeIt& first(NodeIt& i) const {
382      i=NodeIt(*this); return i;
383    }
384    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
385      i=OutEdgeIt(*this, p); return i;
386    }
387    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
388      i=InEdgeIt(*this, p); return i;
389    }
390    EdgeIt& first(EdgeIt& i) const {
391      i=EdgeIt(*this); return i;
392    }
393   
394    NodeIt& next(NodeIt& i) const {
395      this->graph->next(i.n);
396      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
397        this->graph->next(i.n); }
398      return i;
399    }
400    OutEdgeIt& next(OutEdgeIt& i) const {
401      this->graph->next(i.e);
402      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
403        this->graph->next(i.e); }
404      return i;
405    }
406    InEdgeIt& next(InEdgeIt& i) const {
407      this->graph->next(i.e);
408      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
409        this->graph->next(i.e); }
410      return i;
411    }
412    EdgeIt& next(EdgeIt& i) const {
413      this->graph->next(i.e);
414      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
415        this->graph->next(i.e); }
416      return i;
417    }
418
419    Node aNode(const OutEdgeIt& e) const {
420      return Node(this->graph->aNode(e.e)); }
421    Node aNode(const InEdgeIt& e) const {
422      return Node(this->graph->aNode(e.e)); }
423    Node bNode(const OutEdgeIt& e) const {
424      return Node(this->graph->bNode(e.e)); }
425    Node bNode(const InEdgeIt& e) const {
426      return Node(this->graph->bNode(e.e)); }
427
428    ///\todo
429    ///Some doki, please.
430    void hide(const Node& n) const { node_filter_map->set(n, false); }
431    ///\todo
432    ///Some doki, please.
433    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
434
435    ///\todo
436    ///Some doki, please.
437    void unHide(const Node& n) const { node_filter_map->set(n, true); }
438    ///\todo
439    ///Some doki, please.
440    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
441
442    ///\todo
443    ///Some doki, please.
444    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
445    ///\todo
446    ///Some doki, please.
447    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
448  };
449
450  /// A wrapper for forgetting the orientation of a graph.
451
452  /// A wrapper for getting an undirected graph by forgetting
453  /// the orientation of a directed one.
454  template<typename Graph>
455  class UndirGraphWrapper : public GraphWrapper<Graph> {
456  public:
457    typedef typename GraphWrapper<Graph>::Node Node;
458    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
459    typedef typename GraphWrapper<Graph>::Edge Edge;
460    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
461
462    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
463
464    class OutEdgeIt {
465      friend class UndirGraphWrapper<Graph>;
466      bool out_or_in; //true iff out
467      typename Graph::OutEdgeIt out;
468      typename Graph::InEdgeIt in;
469    public:
470      OutEdgeIt() { }
471      OutEdgeIt(const Invalid& i) : Edge(i) { }
472      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
473        out_or_in=true; _G.graph->first(out, _n);
474        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
475      }
476      operator Edge() const {
477        if (out_or_in) return Edge(out); else return Edge(in);
478      }
479    };
480
481//FIXME InEdgeIt
482    typedef OutEdgeIt InEdgeIt;
483
484    using GraphWrapper<Graph>::first;
485//     NodeIt& first(NodeIt& i) const {
486//       i=NodeIt(*this); return i;
487//     }
488    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
489      i=OutEdgeIt(*this, p); return i;
490    }
491//FIXME
492//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
493//       i=InEdgeIt(*this, p); return i;
494//     }
495//     EdgeIt& first(EdgeIt& i) const {
496//       i=EdgeIt(*this); return i;
497//     }
498
499    using GraphWrapper<Graph>::next;
500//     NodeIt& next(NodeIt& n) const {
501//       GraphWrapper<Graph>::next(n);
502//       return n;
503//     }
504    OutEdgeIt& next(OutEdgeIt& e) const {
505      if (e.out_or_in) {
506        typename Graph::Node n=this->graph->tail(e.out);
507        this->graph->next(e.out);
508        if (!this->graph->valid(e.out)) {
509          e.out_or_in=false; this->graph->first(e.in, n); }
510      } else {
511        this->graph->next(e.in);
512      }
513      return e;
514    }
515    //FIXME InEdgeIt
516//     EdgeIt& next(EdgeIt& e) const {
517//       GraphWrapper<Graph>::next(n);
518// //      graph->next(e.e);
519//       return e;
520//     }
521
522    Node aNode(const OutEdgeIt& e) const {
523      if (e.out_or_in) return this->graph->tail(e); else
524        return this->graph->head(e); }
525    Node bNode(const OutEdgeIt& e) const {
526      if (e.out_or_in) return this->graph->head(e); else
527        return this->graph->tail(e); }
528  };
529 
530  /// A wrapper for composing the residual graph for directed flow and circulation problems.
531
532  /// A wrapper for composing the residual graph for directed flow and circulation problems.
533  template<typename Graph, typename Number,
534           typename CapacityMap, typename FlowMap>
535  class ResGraphWrapper : public GraphWrapper<Graph> {
536  protected:
537    const CapacityMap* capacity;
538    FlowMap* flow;
539  public:
540
541    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
542                    FlowMap& _flow) :
543      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
544
545    class Edge;
546    class OutEdgeIt;
547    friend class Edge;
548    friend class OutEdgeIt;
549
550    typedef typename GraphWrapper<Graph>::Node Node;
551    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
552    class Edge : public Graph::Edge {
553      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
554    protected:
555      bool forward; //true, iff forward
556//      typename Graph::Edge e;
557    public:
558      Edge() { }
559      Edge(const typename Graph::Edge& _e, bool _forward) :
560        Graph::Edge(_e), forward(_forward) { }
561      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
562//the unique invalid iterator
563      friend bool operator==(const Edge& u, const Edge& v) {
564        return (v.forward==u.forward &&
565                static_cast<typename Graph::Edge>(u)==
566                static_cast<typename Graph::Edge>(v));
567      }
568      friend bool operator!=(const Edge& u, const Edge& v) {
569        return (v.forward!=u.forward ||
570                static_cast<typename Graph::Edge>(u)!=
571                static_cast<typename Graph::Edge>(v));
572      }
573    };
574
575    class OutEdgeIt {
576      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
577    protected:
578      typename Graph::OutEdgeIt out;
579      typename Graph::InEdgeIt in;
580      bool forward;
581    public:
582      OutEdgeIt() { }
583      //FIXME
584//      OutEdgeIt(const Edge& e) : Edge(e) { }
585      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
586//the unique invalid iterator
587      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
588        forward=true;
589        resG.graph->first(out, v);
590        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
591        if (!resG.graph->valid(out)) {
592          forward=false;
593          resG.graph->first(in, v);
594          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
595        }
596      }
597      operator Edge() const {
598//      Edge e;
599//      e.forward=this->forward;
600//      if (this->forward) e=out; else e=in;
601//      return e;
602        if (this->forward)
603          return Edge(out, this->forward);
604        else
605          return Edge(in, this->forward);
606      }
607    };
608
609    class InEdgeIt {
610      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
611    protected:
612      typename Graph::OutEdgeIt out;
613      typename Graph::InEdgeIt in;
614      bool forward;
615    public:
616      InEdgeIt() { }
617      //FIXME
618//      OutEdgeIt(const Edge& e) : Edge(e) { }
619      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
620//the unique invalid iterator
621      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
622        forward=true;
623        resG.graph->first(in, v);
624        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
625        if (!resG.graph->valid(in)) {
626          forward=false;
627          resG.graph->first(out, v);
628          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
629        }
630      }
631      operator Edge() const {
632//      Edge e;
633//      e.forward=this->forward;
634//      if (this->forward) e=out; else e=in;
635//      return e;
636        if (this->forward)
637          return Edge(in, this->forward);
638        else
639          return Edge(out, this->forward);
640      }
641    };
642
643    class EdgeIt {
644      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
645    protected:
646      typename Graph::EdgeIt e;
647      bool forward;
648    public:
649      EdgeIt() { }
650      EdgeIt(const Invalid& i) : e(i), forward(false) { }
651      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
652        forward=true;
653        resG.graph->first(e);
654        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
655        if (!resG.graph->valid(e)) {
656          forward=false;
657          resG.graph->first(e);
658          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
659        }
660      }
661      operator Edge() const {
662        return Edge(e, this->forward);
663      }
664    };
665
666    using GraphWrapper<Graph>::first;
667//     NodeIt& first(NodeIt& i) const {
668//       i=NodeIt(*this); return i;
669//     }
670    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
671      i=OutEdgeIt(*this, p); return i;
672    }
673//    FIXME not tested
674    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
675      i=InEdgeIt(*this, p); return i;
676    }
677    EdgeIt& first(EdgeIt& i) const {
678      i=EdgeIt(*this); return i;
679    }
680 
681    using GraphWrapper<Graph>::next;
682//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
683    OutEdgeIt& next(OutEdgeIt& e) const {
684      if (e.forward) {
685        Node v=this->graph->aNode(e.out);
686        this->graph->next(e.out);
687        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
688          this->graph->next(e.out); }
689        if (!this->graph->valid(e.out)) {
690          e.forward=false;
691          this->graph->first(e.in, v);
692          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
693            this->graph->next(e.in); }
694        }
695      } else {
696        this->graph->next(e.in);
697        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
698          this->graph->next(e.in); }
699      }
700      return e;
701    }
702//     FIXME Not tested
703    InEdgeIt& next(InEdgeIt& e) const {
704      if (e.forward) {
705        Node v=this->graph->aNode(e.in);
706        this->graph->next(e.in);
707        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
708          this->graph->next(e.in); }
709        if (!this->graph->valid(e.in)) {
710          e.forward=false;
711          this->graph->first(e.out, v);
712          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
713            this->graph->next(e.out); }
714        }
715      } else {
716        this->graph->next(e.out);
717        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
718          this->graph->next(e.out); }
719      }
720      return e;
721    }
722    EdgeIt& next(EdgeIt& e) const {
723      if (e.forward) {
724        this->graph->next(e.e);
725        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
726          this->graph->next(e.e); }
727        if (!this->graph->valid(e.e)) {
728          e.forward=false;
729          this->graph->first(e.e);
730          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
731            this->graph->next(e.e); }
732        }
733      } else {
734        this->graph->next(e.e);
735        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
736          this->graph->next(e.e); }
737      }
738      return e;
739    }
740
741    Node tail(Edge e) const {
742      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
743    Node head(Edge e) const {
744      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
745
746    Node aNode(OutEdgeIt e) const {
747      return ((e.forward) ? this->graph->aNode(e.out) :
748              this->graph->aNode(e.in)); }
749    Node bNode(OutEdgeIt e) const {
750      return ((e.forward) ? this->graph->bNode(e.out) :
751              this->graph->bNode(e.in)); }
752
753    Node aNode(InEdgeIt e) const {
754      return ((e.forward) ? this->graph->aNode(e.in) :
755              this->graph->aNode(e.out)); }
756    Node bNode(InEdgeIt e) const {
757      return ((e.forward) ? this->graph->bNode(e.in) :
758              this->graph->bNode(e.out)); }
759
760//    int nodeNum() const { return graph->nodeNum(); }
761    //FIXME
762    void edgeNum() const { }
763    //int edgeNum() const { return graph->edgeNum(); }
764
765
766//    int id(Node v) const { return graph->id(v); }
767
768    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
769    bool valid(Edge e) const {
770      return this->graph->valid(e);
771        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
772    }
773
774    void augment(const Edge& e, Number a) const {
775      if (e.forward) 
776//      flow->set(e.out, flow->get(e.out)+a);
777        flow->set(e, (*flow)[e]+a);
778      else 
779//      flow->set(e.in, flow->get(e.in)-a);
780        flow->set(e, (*flow)[e]-a);
781    }
782
783    Number resCap(const Edge& e) const {
784      if (e.forward)
785//      return (capacity->get(e.out)-flow->get(e.out));
786        return ((*capacity)[e]-(*flow)[e]);
787      else
788//      return (flow->get(e.in));
789        return ((*flow)[e]);
790    }
791
792//     Number resCap(typename Graph::OutEdgeIt out) const {
793// //      return (capacity->get(out)-flow->get(out));
794//       return ((*capacity)[out]-(*flow)[out]);
795//     }
796   
797//     Number resCap(typename Graph::InEdgeIt in) const {
798// //      return (flow->get(in));
799//       return ((*flow)[in]);
800//     }
801
802    template <typename T>
803    class EdgeMap {
804      typename Graph::template EdgeMap<T> forward_map, backward_map;
805    public:
806      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
807      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
808      void set(Edge e, T a) {
809        if (e.forward)
810          forward_map.set(e.out, a);
811        else
812          backward_map.set(e.in, a);
813      }
814      T operator[](Edge e) const {
815        if (e.forward)
816          return forward_map[e.out];
817        else
818          return backward_map[e.in];
819      }
820//       T get(Edge e) const {
821//      if (e.out_or_in)
822//        return forward_map.get(e.out);
823//      else
824//        return backward_map.get(e.in);
825//       }
826    };
827  };
828
829  /// ErasingFirstGraphWrapper for blocking flows.
830
831  /// ErasingFirstGraphWrapper for blocking flows.
832  ///
833  ///\author Marton Makai
834  template<typename Graph, typename FirstOutEdgesMap>
835  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
836  protected:
837    FirstOutEdgesMap* first_out_edges;
838  public:
839    ErasingFirstGraphWrapper(Graph& _graph,
840                             FirstOutEdgesMap& _first_out_edges) :
841      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
842
843    typedef typename GraphWrapper<Graph>::Node Node;
844//     class NodeIt {
845//       friend class GraphWrapper<Graph>;
846//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
847//       typename Graph::NodeIt n;
848//      public:
849//       NodeIt() { }
850//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
851//       NodeIt(const Invalid& i) : n(i) { }
852//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
853//      n(*(_G.graph)) { }
854//       operator Node() const { return Node(typename Graph::Node(n)); }
855//     };
856    typedef typename GraphWrapper<Graph>::Edge Edge;
857    class OutEdgeIt {
858      friend class GraphWrapper<Graph>;
859      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
860//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
861      typename Graph::OutEdgeIt e;
862    public:
863      OutEdgeIt() { }
864      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
865      OutEdgeIt(const Invalid& i) : e(i) { }
866      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
867                const Node& _n) :
868        e((*_G.first_out_edges)[_n]) { }
869      operator Edge() const { return Edge(typename Graph::Edge(e)); }
870    };
871    class InEdgeIt {
872      friend class GraphWrapper<Graph>;
873      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
874//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
875      typename Graph::InEdgeIt e;
876    public:
877      InEdgeIt() { }
878      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
879      InEdgeIt(const Invalid& i) : e(i) { }
880      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
881               const Node& _n) :
882        e(*(_G.graph), typename Graph::Node(_n)) { }
883      operator Edge() const { return Edge(typename Graph::Edge(e)); }
884    };
885    //typedef typename Graph::SymEdgeIt SymEdgeIt;
886    class EdgeIt {
887      friend class GraphWrapper<Graph>;
888      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
889//      typedef typename Graph::EdgeIt GraphEdgeIt;
890      typename Graph::EdgeIt e;
891    public:
892      EdgeIt() { }
893      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
894      EdgeIt(const Invalid& i) : e(i) { }
895      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
896        e(*(_G.graph)) { }
897      operator Edge() const { return Edge(typename Graph::Edge(e)); }
898    };
899
900    using GraphWrapper<Graph>::first;
901//     NodeIt& first(NodeIt& i) const {
902//       i=NodeIt(*this); return i;
903//     }
904    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
905      i=OutEdgeIt(*this, p); return i;
906    }
907    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
908      i=InEdgeIt(*this, p); return i;
909    }
910    EdgeIt& first(EdgeIt& i) const {
911      i=EdgeIt(*this); return i;
912    }
913
914    using GraphWrapper<Graph>::next;
915//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
916    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
917    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
918    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
919   
920    Node aNode(const OutEdgeIt& e) const {
921      return Node(this->graph->aNode(e.e)); }
922    Node aNode(const InEdgeIt& e) const {
923      return Node(this->graph->aNode(e.e)); }
924    Node bNode(const OutEdgeIt& e) const {
925      return Node(this->graph->bNode(e.e)); }
926    Node bNode(const InEdgeIt& e) const {
927      return Node(this->graph->bNode(e.e)); }
928
929    void erase(const OutEdgeIt& e) const {
930      OutEdgeIt f=e;
931      this->next(f);
932      first_out_edges->set(this->tail(e), f.e);
933    }
934  };
935
936  ///@}
937
938} //namespace hugo
939
940
941#endif //HUGO_GRAPH_WRAPPER_H
942
Note: See TracBrowser for help on using the repository browser.