COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 356:b4dcbe3e3b8f

Last change on this file since 356:b4dcbe3e3b8f was 356:b4dcbe3e3b8f, checked in by Alpar Juttner, 17 years ago

.

File size: 36.1 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
4
5#include <invalid.h>
6
7namespace hugo {
8
9  /// Graph wrappers
10
11  /// A main parts of HUGOlib are the different graph structures,
12  /// generic graph algorithms, graph concepts which couple these, and
13  /// graph wrappers. While the previous ones are more or less clear, the
14  /// latter notion needs further explanation.
15  /// Graph wrappers are graph classes which serve for considering graph
16  /// structures in different ways. A short example makes the notion much
17  /// clearer.
18  /// Suppose that we have an instance \c g of a directed graph
19  /// type say \c ListGraph and an algorithm
20  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
21  /// is needed to run on the reversely oriented graph.
22  /// It may be expensive (in time or in memory usage) to copy
23  /// \c g with the reverse orientation.
24  /// Thus, a wrapper class
25  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
26  /// The code looks as follows
27  /// \code
28  /// ListGraph g;
29  /// RevGraphWrapper<ListGraph> rgw(g);
30  /// int result=algorithm(rgw);
31  /// \endcode
32  /// After running the algorithm, the original graph \c g
33  /// remains untouched. Thus the graph wrapper used above is to consider the
34  /// original graph with reverse orientation.
35  /// This techniques gives rise to an elegant code, and
36  /// based on stable graph wrappers, complex algorithms can be
37  /// implemented easily.
38  /// In flow, circulation and bipartite matching problems, the residual
39  /// graph is of particular importance. Combining a wrapper implementing
40  /// this, shortest path algorithms and minimum mean cycle algorithms,
41  /// a range of weighted and cardinality optimization algorithms can be
42  /// obtained. For lack of space, for other examples,
43  /// the interested user is referred to the detailed documentation of graph
44  /// wrappers.
45  /// The behavior of graph wrappers can be very different. Some of them keep
46  /// capabilities of the original graph while in other cases this would be
47  /// meaningless. This means that the concepts that they are a model of depend
48  /// on the graph wrapper, and the wrapped graph(s).
49  /// If an edge of \c rgw is deleted, this is carried out by
50  /// deleting the corresponding edge of \c g. But for a residual
51  /// graph, this operation has no sense.
52  /// Let we stand one more example here to simplify your work.
53  /// wrapper class
54  /// \code template<typename Graph> class RevGraphWrapper; \endcode
55  /// has constructor
56  /// <tt> RevGraphWrapper(Graph& _g)</tt>.
57  /// This means that in a situation,
58  /// when a <tt> const ListGraph& </tt> reference to a graph is given,
59  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
60  /// \code
61  /// int algorithm1(const ListGraph& g) {
62  ///   RevGraphWrapper<const ListGraph> rgw(g);
63  ///   return algorithm2(rgw);
64  /// }
65  /// \endcode
66  template<typename Graph>
67  class GraphWrapper {
68  protected:
69    Graph* graph;
70 
71  public:
72    typedef Graph BaseGraph;
73    typedef Graph ParentGraph;
74
75//     GraphWrapper() : graph(0) { }
76    GraphWrapper(Graph& _graph) : graph(&_graph) { }
77//     void setGraph(Graph& _graph) { graph=&_graph; }
78//     Graph& getGraph() const { return *graph; }
79 
80//    typedef typename Graph::Node Node;
81    class Node : public Graph::Node {
82      friend class GraphWrapper<Graph>;
83    public:
84      Node() { }
85      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
86      Node(const Invalid& i) : Graph::Node(i) { }
87    };
88    class NodeIt {
89      friend class GraphWrapper<Graph>;
90      typename Graph::NodeIt n;
91     public:
92      NodeIt() { }
93      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
94      NodeIt(const Invalid& i) : n(i) { }
95      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
96      operator Node() const { return Node(typename Graph::Node(n)); }
97    };
98//    typedef typename Graph::Edge Edge;
99    class Edge : public Graph::Edge {
100      friend class GraphWrapper<Graph>;
101    public:
102      Edge() { }
103      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
104      Edge(const Invalid& i) : Graph::Edge(i) { }
105    };
106    class OutEdgeIt {
107      friend class GraphWrapper<Graph>;
108      typename Graph::OutEdgeIt e;
109    public:
110      OutEdgeIt() { }
111      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
112      OutEdgeIt(const Invalid& i) : e(i) { }
113      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
114        e(*(_G.graph), typename Graph::Node(_n)) { }
115      operator Edge() const { return Edge(typename Graph::Edge(e)); }
116    };
117    class InEdgeIt {
118      friend class GraphWrapper<Graph>;
119      typename Graph::InEdgeIt e;
120    public:
121      InEdgeIt() { }
122      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
123      InEdgeIt(const Invalid& i) : e(i) { }
124      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
125        e(*(_G.graph), typename Graph::Node(_n)) { }
126      operator Edge() const { return Edge(typename Graph::Edge(e)); }
127    };
128    //typedef typename Graph::SymEdgeIt SymEdgeIt;
129    class EdgeIt {
130      friend class GraphWrapper<Graph>;
131      typename Graph::EdgeIt e;
132    public:
133      EdgeIt() { }
134      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
135      EdgeIt(const Invalid& i) : e(i) { }
136      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
137      operator Edge() const { return Edge(typename Graph::Edge(e)); }
138    };
139   
140    NodeIt& first(NodeIt& i) const {
141      i=NodeIt(*this); return i;
142    }
143    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
144      i=OutEdgeIt(*this, p); return i;
145    }
146    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
147      i=InEdgeIt(*this, p); return i;
148    }
149    EdgeIt& first(EdgeIt& i) const {
150      i=EdgeIt(*this); return i;
151    }
152
153    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
154    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
155    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
156    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
157
158    Node head(const Edge& e) const {
159      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
160    Node tail(const Edge& e) const {
161      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
162
163    bool valid(const Node& n) const {
164      return graph->valid(static_cast<typename Graph::Node>(n)); }
165    bool valid(const Edge& e) const {
166      return graph->valid(static_cast<typename Graph::Edge>(e)); }
167
168    int nodeNum() const { return graph->nodeNum(); }
169    int edgeNum() const { return graph->edgeNum(); }
170 
171    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
172    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
173    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
174    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
175 
176    Node addNode() const { return Node(graph->addNode()); }
177    Edge addEdge(const Node& tail, const Node& head) const {
178      return Edge(graph->addEdge(tail, head)); }
179
180    void erase(const Node& i) const { graph->erase(i); }
181    void erase(const Edge& i) const { graph->erase(i); }
182 
183    void clear() const { graph->clear(); }
184   
185    template<typename T> class NodeMap : public Graph::NodeMap<T> {
186    public:
187      NodeMap(const GraphWrapper<Graph>& _G) : 
188        Graph::NodeMap<T>(*(_G.graph)) { }
189      NodeMap(const GraphWrapper<Graph>& _G, T a) :
190        Graph::NodeMap<T>(*(_G.graph), a) { }
191    };
192
193    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
194    public:
195      EdgeMap(const GraphWrapper<Graph>& _G) : 
196        Graph::EdgeMap<T>(*(_G.graph)) { }
197      EdgeMap(const GraphWrapper<Graph>& _G, T a) :
198        Graph::EdgeMap<T>(*(_G.graph), a) { }
199    };
200  };
201
202  /// A graph wrapper which reverses the orientation of the edges.
203
204  /// A graph wrapper which reverses the orientation of the edges.
205  template<typename Graph>
206  class RevGraphWrapper : public GraphWrapper<Graph> {
207  public:
208
209    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
210
211    typedef typename GraphWrapper<Graph>::Node Node;
212    typedef typename GraphWrapper<Graph>::Edge Edge;
213    //If Graph::OutEdgeIt is not defined
214    //and we do not want to use RevGraphWrapper::InEdgeIt,
215    //the typdef techinque does not work.
216    //Unfortunately all the typedefs are instantiated in templates.
217    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
218    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
219
220    class OutEdgeIt {
221      friend class GraphWrapper<Graph>;
222      friend class RevGraphWrapper<Graph>;
223      typename Graph::OutEdgeIt e;
224    public:
225      OutEdgeIt() { }
226      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
227      OutEdgeIt(const Invalid& i) : e(i) { }
228      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
229        e(*(_G.graph), typename Graph::Node(_n)) { }
230      operator Edge() const { return Edge(typename Graph::Edge(e)); }
231    };
232    class InEdgeIt {
233      friend class GraphWrapper<Graph>;
234      friend class RevGraphWrapper<Graph>;
235      typename Graph::InEdgeIt e;
236    public:
237      InEdgeIt() { }
238      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
239      InEdgeIt(const Invalid& i) : e(i) { }
240      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
241        e(*(_G.graph), typename Graph::Node(_n)) { }
242      operator Edge() const { return Edge(typename Graph::Edge(e)); }
243    };
244
245    using GraphWrapper<Graph>::first;
246    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
247      i=OutEdgeIt(*this, p); return i;
248    }
249    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
250      i=InEdgeIt(*this, p); return i;
251    }
252
253    using GraphWrapper<Graph>::next;
254    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
255    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
256
257    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
258    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
259    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
260    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
261  };
262
263  /// Wrapper for hiding nodes and edges from a graph.
264 
265  /// This wrapper shows a graph with filtered node-set and
266  /// edge-set. The quick brown fox iterators jumps over
267  /// the lazy dog nodes or edges if the values for them are false
268  /// in the bool maps.
269  template<typename Graph, typename NodeFilterMap,
270           typename EdgeFilterMap>
271  class SubGraphWrapper : public GraphWrapper<Graph> {
272  protected:
273    NodeFilterMap* node_filter_map;
274    EdgeFilterMap* edge_filter_map;
275  public:
276
277    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
278                    EdgeFilterMap& _edge_filter_map) :
279      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
280      edge_filter_map(&_edge_filter_map) { } 
281
282    typedef typename GraphWrapper<Graph>::Node Node;
283    class NodeIt {
284      friend class GraphWrapper<Graph>;
285      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
286      typename Graph::NodeIt n;
287     public:
288      NodeIt() { }
289      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
290      NodeIt(const Invalid& i) : n(i) { }
291      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
292        n(*(_G.graph)) {
293        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
294          _G.graph->next(n);
295      }
296      operator Node() const { return Node(typename Graph::Node(n)); }
297    };
298    typedef typename GraphWrapper<Graph>::Edge Edge;
299    class OutEdgeIt {
300      friend class GraphWrapper<Graph>;
301      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
302      typename Graph::OutEdgeIt e;
303    public:
304      OutEdgeIt() { }
305      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
306      OutEdgeIt(const Invalid& i) : e(i) { }
307      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
308                const Node& _n) :
309        e(*(_G.graph), typename Graph::Node(_n)) {
310        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
311          _G.graph->next(e);
312      }
313      operator Edge() const { return Edge(typename Graph::Edge(e)); }
314    };
315    class InEdgeIt {
316      friend class GraphWrapper<Graph>;
317      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
318      typename Graph::InEdgeIt e;
319    public:
320      InEdgeIt() { }
321      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
322      InEdgeIt(const Invalid& i) : e(i) { }
323      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
324               const Node& _n) :
325        e(*(_G.graph), typename Graph::Node(_n)) {
326        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
327          _G.graph->next(e);
328      }
329      operator Edge() const { return Edge(typename Graph::Edge(e)); }
330    };
331    //typedef typename Graph::SymEdgeIt SymEdgeIt;
332    class EdgeIt {
333      friend class GraphWrapper<Graph>;
334      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
335      typename Graph::EdgeIt e;
336    public:
337      EdgeIt() { }
338      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
339      EdgeIt(const Invalid& i) : e(i) { }
340      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
341        e(*(_G.graph)) {
342        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
343          _G.graph->next(e);
344      }
345      operator Edge() const { return Edge(typename Graph::Edge(e)); }
346    };
347
348    NodeIt& first(NodeIt& i) const {
349      i=NodeIt(*this); return i;
350    }
351    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
352      i=OutEdgeIt(*this, p); return i;
353    }
354    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
355      i=InEdgeIt(*this, p); return i;
356    }
357    EdgeIt& first(EdgeIt& i) const {
358      i=EdgeIt(*this); return i;
359    }
360   
361    NodeIt& next(NodeIt& i) const {
362      graph->next(i.n);
363      while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
364      return i;
365    }
366    OutEdgeIt& next(OutEdgeIt& i) const {
367      graph->next(i.e);
368      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
369      return i;
370    }
371    InEdgeIt& next(InEdgeIt& i) const {
372      graph->next(i.e);
373      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
374      return i;
375    }
376    EdgeIt& next(EdgeIt& i) const {
377      graph->next(i.e);
378      while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
379      return i;
380    }
381
382    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
383    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
384    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
385    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
386
387    void hide(const Node& n) const { node_filter_map->set(n, false); }
388    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
389
390    void unHide(const Node& n) const { node_filter_map->set(n, true); }
391    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
392
393    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
394    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
395  };
396
397  /// A wrapper for forgetting the orientation of a graph.
398
399  /// A wrapper for getting an undirected graph by forgetting
400  /// the orientation of a directed one.
401  template<typename Graph>
402  class UndirGraphWrapper : public GraphWrapper<Graph> {
403  public:
404    typedef typename GraphWrapper<Graph>::Node Node;
405    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
406    typedef typename GraphWrapper<Graph>::Edge Edge;
407    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
408
409    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
410
411    class OutEdgeIt {
412      friend class UndirGraphWrapper<Graph>;
413      bool out_or_in; //true iff out
414      typename Graph::OutEdgeIt out;
415      typename Graph::InEdgeIt in;
416    public:
417      OutEdgeIt() { }
418      OutEdgeIt(const Invalid& i) : Edge(i) { }
419      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
420        out_or_in=true; _G.graph->first(out, _n);
421        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
422      }
423      operator Edge() const {
424        if (out_or_in) return Edge(out); else return Edge(in);
425      }
426    };
427
428//FIXME InEdgeIt
429    typedef OutEdgeIt InEdgeIt;
430
431    using GraphWrapper<Graph>::first;
432//     NodeIt& first(NodeIt& i) const {
433//       i=NodeIt(*this); return i;
434//     }
435    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
436      i=OutEdgeIt(*this, p); return i;
437    }
438//FIXME
439//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
440//       i=InEdgeIt(*this, p); return i;
441//     }
442//     EdgeIt& first(EdgeIt& i) const {
443//       i=EdgeIt(*this); return i;
444//     }
445
446    using GraphWrapper<Graph>::next;
447//     NodeIt& next(NodeIt& n) const {
448//       GraphWrapper<Graph>::next(n);
449//       return n;
450//     }
451    OutEdgeIt& next(OutEdgeIt& e) const {
452      if (e.out_or_in) {
453        typename Graph::Node n=graph->tail(e.out);
454        graph->next(e.out);
455        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
456      } else {
457        graph->next(e.in);
458      }
459      return e;
460    }
461    //FIXME InEdgeIt
462//     EdgeIt& next(EdgeIt& e) const {
463//       GraphWrapper<Graph>::next(n);
464// //      graph->next(e.e);
465//       return e;
466//     }
467
468    Node aNode(const OutEdgeIt& e) const {
469      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
470    Node bNode(const OutEdgeIt& e) const {
471      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
472  };
473 
474  /// A wrapper for composing the residual graph for directed flow and circulation problems.
475
476  /// A wrapper for composing the residual graph for directed flow and circulation problems.
477  template<typename Graph, typename Number,
478           typename CapacityMap, typename FlowMap>
479  class ResGraphWrapper : public GraphWrapper<Graph> {
480  protected:
481    const CapacityMap* capacity;
482    FlowMap* flow;
483  public:
484
485    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
486                    FlowMap& _flow) :
487      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
488
489    class Edge;
490    class OutEdgeIt;
491    friend class Edge;
492    friend class OutEdgeIt;
493
494    typedef typename GraphWrapper<Graph>::Node Node;
495    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
496    class Edge : public Graph::Edge {
497      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
498    protected:
499      bool forward; //true, iff forward
500//      typename Graph::Edge e;
501    public:
502      Edge() { }
503      Edge(const typename Graph::Edge& _e, bool _forward) :
504        Graph::Edge(_e), forward(_forward) { }
505      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
506//the unique invalid iterator
507      friend bool operator==(const Edge& u, const Edge& v) {
508        return (v.forward==u.forward &&
509                static_cast<typename Graph::Edge>(u)==
510                static_cast<typename Graph::Edge>(v));
511      }
512      friend bool operator!=(const Edge& u, const Edge& v) {
513        return (v.forward!=u.forward ||
514                static_cast<typename Graph::Edge>(u)!=
515                static_cast<typename Graph::Edge>(v));
516      }
517    };
518
519    class OutEdgeIt {
520      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
521    protected:
522      typename Graph::OutEdgeIt out;
523      typename Graph::InEdgeIt in;
524      bool forward;
525    public:
526      OutEdgeIt() { }
527      //FIXME
528//      OutEdgeIt(const Edge& e) : Edge(e) { }
529      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
530//the unique invalid iterator
531      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
532        forward=true;
533        resG.graph->first(out, v);
534        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
535        if (!resG.graph->valid(out)) {
536          forward=false;
537          resG.graph->first(in, v);
538          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
539        }
540      }
541      operator Edge() const {
542//      Edge e;
543//      e.forward=this->forward;
544//      if (this->forward) e=out; else e=in;
545//      return e;
546        if (this->forward)
547          return Edge(out, this->forward);
548        else
549          return Edge(in, this->forward);
550      }
551    };
552
553    class InEdgeIt {
554      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
555    protected:
556      typename Graph::OutEdgeIt out;
557      typename Graph::InEdgeIt in;
558      bool forward;
559    public:
560      InEdgeIt() { }
561      //FIXME
562//      OutEdgeIt(const Edge& e) : Edge(e) { }
563      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
564//the unique invalid iterator
565      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
566        forward=true;
567        resG.graph->first(in, v);
568        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
569        if (!resG.graph->valid(in)) {
570          forward=false;
571          resG.graph->first(out, v);
572          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
573        }
574      }
575      operator Edge() const {
576//      Edge e;
577//      e.forward=this->forward;
578//      if (this->forward) e=out; else e=in;
579//      return e;
580        if (this->forward)
581          return Edge(in, this->forward);
582        else
583          return Edge(out, this->forward);
584      }
585    };
586
587    class EdgeIt {
588      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
589    protected:
590      typename Graph::EdgeIt e;
591      bool forward;
592    public:
593      EdgeIt() { }
594      EdgeIt(const Invalid& i) : e(i), forward(false) { }
595      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
596        forward=true;
597        resG.graph->first(e);
598        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
599        if (!resG.graph->valid(e)) {
600          forward=false;
601          resG.graph->first(e);
602          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
603        }
604      }
605      operator Edge() const {
606        return Edge(e, this->forward);
607      }
608    };
609
610    using GraphWrapper<Graph>::first;
611//     NodeIt& first(NodeIt& i) const {
612//       i=NodeIt(*this); return i;
613//     }
614    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
615      i=OutEdgeIt(*this, p); return i;
616    }
617//    FIXME not tested
618    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
619      i=InEdgeIt(*this, p); return i;
620    }
621    EdgeIt& first(EdgeIt& i) const {
622      i=EdgeIt(*this); return i;
623    }
624 
625    using GraphWrapper<Graph>::next;
626//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
627    OutEdgeIt& next(OutEdgeIt& e) const {
628      if (e.forward) {
629        Node v=graph->aNode(e.out);
630        graph->next(e.out);
631        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
632        if (!graph->valid(e.out)) {
633          e.forward=false;
634          graph->first(e.in, v);
635          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
636        }
637      } else {
638        graph->next(e.in);
639        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
640      }
641      return e;
642    }
643//     FIXME Not tested
644    InEdgeIt& next(InEdgeIt& e) const {
645      if (e.forward) {
646        Node v=graph->aNode(e.in);
647        graph->next(e.in);
648        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
649        if (!graph->valid(e.in)) {
650          e.forward=false;
651          graph->first(e.out, v);
652          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
653        }
654      } else {
655        graph->next(e.out);
656        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
657      }
658      return e;
659    }
660    EdgeIt& next(EdgeIt& e) const {
661      if (e.forward) {
662        graph->next(e.e);
663        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
664        if (!graph->valid(e.e)) {
665          e.forward=false;
666          graph->first(e.e);
667          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
668        }
669      } else {
670        graph->next(e.e);
671        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
672      }
673      return e;
674    }
675
676    Node tail(Edge e) const {
677      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
678    Node head(Edge e) const {
679      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
680
681    Node aNode(OutEdgeIt e) const {
682      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
683    Node bNode(OutEdgeIt e) const {
684      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
685
686//    int nodeNum() const { return graph->nodeNum(); }
687    //FIXME
688    void edgeNum() const { }
689    //int edgeNum() const { return graph->edgeNum(); }
690
691
692//    int id(Node v) const { return graph->id(v); }
693
694    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
695    bool valid(Edge e) const {
696      return graph->valid(e);
697        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
698    }
699
700    void augment(const Edge& e, Number a) const {
701      if (e.forward) 
702//      flow->set(e.out, flow->get(e.out)+a);
703        flow->set(e, (*flow)[e]+a);
704      else 
705//      flow->set(e.in, flow->get(e.in)-a);
706        flow->set(e, (*flow)[e]-a);
707    }
708
709    Number resCap(const Edge& e) const {
710      if (e.forward)
711//      return (capacity->get(e.out)-flow->get(e.out));
712        return ((*capacity)[e]-(*flow)[e]);
713      else
714//      return (flow->get(e.in));
715        return ((*flow)[e]);
716    }
717
718//     Number resCap(typename Graph::OutEdgeIt out) const {
719// //      return (capacity->get(out)-flow->get(out));
720//       return ((*capacity)[out]-(*flow)[out]);
721//     }
722   
723//     Number resCap(typename Graph::InEdgeIt in) const {
724// //      return (flow->get(in));
725//       return ((*flow)[in]);
726//     }
727
728    template <typename T>
729    class EdgeMap {
730      typename Graph::EdgeMap<T> forward_map, backward_map;
731    public:
732      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
733      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
734      void set(Edge e, T a) {
735        if (e.forward)
736          forward_map.set(e.out, a);
737        else
738          backward_map.set(e.in, a);
739      }
740      T operator[](Edge e) const {
741        if (e.forward)
742          return forward_map[e.out];
743        else
744          return backward_map[e.in];
745      }
746//       T get(Edge e) const {
747//      if (e.out_or_in)
748//        return forward_map.get(e.out);
749//      else
750//        return backward_map.get(e.in);
751//       }
752    };
753  };
754
755  /// ErasingFirstGraphWrapper for blocking flows.
756
757  /// ErasingFirstGraphWrapper for blocking flows.
758  template<typename Graph, typename FirstOutEdgesMap>
759  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
760  protected:
761    FirstOutEdgesMap* first_out_edges;
762  public:
763    ErasingFirstGraphWrapper(Graph& _graph,
764                             FirstOutEdgesMap& _first_out_edges) :
765      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
766
767    typedef typename GraphWrapper<Graph>::Node Node;
768//     class NodeIt {
769//       friend class GraphWrapper<Graph>;
770//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
771//       typename Graph::NodeIt n;
772//      public:
773//       NodeIt() { }
774//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
775//       NodeIt(const Invalid& i) : n(i) { }
776//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
777//      n(*(_G.graph)) { }
778//       operator Node() const { return Node(typename Graph::Node(n)); }
779//     };
780    typedef typename GraphWrapper<Graph>::Edge Edge;
781    class OutEdgeIt {
782      friend class GraphWrapper<Graph>;
783      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
784//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
785      typename Graph::OutEdgeIt e;
786    public:
787      OutEdgeIt() { }
788      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
789      OutEdgeIt(const Invalid& i) : e(i) { }
790      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
791                const Node& _n) :
792        e((*_G.first_out_edges)[_n]) { }
793      operator Edge() const { return Edge(typename Graph::Edge(e)); }
794    };
795    class InEdgeIt {
796      friend class GraphWrapper<Graph>;
797      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
798//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
799      typename Graph::InEdgeIt e;
800    public:
801      InEdgeIt() { }
802      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
803      InEdgeIt(const Invalid& i) : e(i) { }
804      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
805               const Node& _n) :
806        e(*(_G.graph), typename Graph::Node(_n)) { }
807      operator Edge() const { return Edge(typename Graph::Edge(e)); }
808    };
809    //typedef typename Graph::SymEdgeIt SymEdgeIt;
810    class EdgeIt {
811      friend class GraphWrapper<Graph>;
812      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
813//      typedef typename Graph::EdgeIt GraphEdgeIt;
814      typename Graph::EdgeIt e;
815    public:
816      EdgeIt() { }
817      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
818      EdgeIt(const Invalid& i) : e(i) { }
819      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
820        e(*(_G.graph)) { }
821      operator Edge() const { return Edge(typename Graph::Edge(e)); }
822    };
823
824    using GraphWrapper<Graph>::first;
825//     NodeIt& first(NodeIt& i) const {
826//       i=NodeIt(*this); return i;
827//     }
828    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
829      i=OutEdgeIt(*this, p); return i;
830    }
831    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
832      i=InEdgeIt(*this, p); return i;
833    }
834    EdgeIt& first(EdgeIt& i) const {
835      i=EdgeIt(*this); return i;
836    }
837
838    using GraphWrapper<Graph>::next;
839//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
840    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
841    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
842    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
843   
844    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
845    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
846    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
847    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
848
849    void erase(const OutEdgeIt& e) const {
850      OutEdgeIt f=e;
851      this->next(f);
852      first_out_edges->set(this->tail(e), f.e);
853    }
854  };
855
856
857
858//   /// experimentral, do not try it.
859//   template<typename Graph>
860//   class stGraphWrapper : public GraphWrapper<Graph> {
861//   public:
862//     class Node;
863//     class NodeIt;
864//     class Edge;
865//     class OutEdgeIt;
866//     class InEdgeIt;
867//     class EdgeIt;
868
869//     const Node s;
870//     const Node t;
871
872//     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),
873//                                  s(INVALID, 1), t(INVALID, 2) { }
874
875//     class Node : public Graph::Node {
876//       friend class GraphWrapper<Graph>;
877//       friend class stGraphWrapper<Graph>;
878//     protected:
879//       int spec; //0 if real node, 1 iff s, 2 iff t
880//     public:
881//       Node() { }
882//       Node(const typename Graph::Node& _n, int _spec=0) :
883//      Graph::Node(_n), spec(_spec) { }
884//       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
885//       //invalid: (invalid, 2);
886//     };
887
888//     class NodeIt {
889//       friend class GraphWrapper<Graph>;
890//       friend class stGraphWrapper<Graph>;
891//       typename Graph::NodeIt n;
892//       int spec;
893//      public:
894//       NodeIt() { }
895//       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :
896//      n(_n), spec(_spec) { }
897//       NodeIt(const Invalid& i) : n(i), spec(2) { }
898//       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
899//      if (!_G->valid(n)) spec=1;
900//       }
901//       operator Node() const { return Node(n, spec); }
902//     };
903// //    typedef typename Graph::Edge Edge;
904//     class Edge : public Graph::Edge {
905//       friend class GraphWrapper<Graph>;
906//       friend class stGraphWrapper<Graph>;
907//       Node tail_spec;
908//       Node head_spec;
909//     public:
910//       Edge() { }
911//       Edge(const typename Graph::Edge& _e) :
912//      Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {
913//      //a tail-t es a head-et real node-ra csinaljuk
914//       }
915//       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
916//     };
917//     class OutEdgeIt {
918//       friend class GraphWrapper<Graph>;
919//       friend class stGraphWrapper<Graph>;
920//       typename Graph::OutEdgeIt e;
921//       Node tail_spec;
922//       Node head_spec;
923//     public:
924//       OutEdgeIt() { }
925//       OutEdgeIt(const typename Graph::OutEdgeIt& _e) :
926//      e(_e), tail_spec(i, 0), head_spec(i, 0) {
927//      //a tail-t es a head-et real node-ra csinaljuk
928//       }
929//       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
930//       //invalid: (barmi, 0, 2)
931//       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
932//      switch (_n.spec) {
933//      case 0 :
934//        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
935//        _tail.spec=0;
936//        _head.spec=0;
937//        if (!_G.graph->valid(e)) spec=1;
938//        break;
939//      case 1:
940//        e=INVALID;
941//        _tail.spec=1;
942//        _head(_G.graph->first(typename Graph::NodeIt()));
943//        if _head.spec==1
944//        break;
945//      };
946       
947//        }
948//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
949//     };
950//     class InEdgeIt {
951//       friend class GraphWrapper<Graph>;
952//       typename Graph::InEdgeIt e;
953//     public:
954//       InEdgeIt() { }
955//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
956//       InEdgeIt(const Invalid& i) : e(i) { }
957//       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
958//      e(*(_G.graph), typename Graph::Node(_n)) { }
959//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
960//     };
961//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
962//     class EdgeIt {
963//       friend class GraphWrapper<Graph>;
964//       typename Graph::EdgeIt e;
965//     public:
966//       EdgeIt() { }
967//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
968//       EdgeIt(const Invalid& i) : e(i) { }
969//       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
970//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
971//     };
972   
973//     NodeIt& first(NodeIt& i) const {
974//       i=NodeIt(*this); return i;
975//     }
976//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
977//       i=OutEdgeIt(*this, p); return i;
978//     }
979//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
980//       i=InEdgeIt(*this, p); return i;
981//     }
982//     EdgeIt& first(EdgeIt& i) const {
983//       i=EdgeIt(*this); return i;
984//     }
985
986//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
987//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
988//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
989//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
990
991//     Node head(const Edge& e) const {
992//       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
993//     Node tail(const Edge& e) const {
994//       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
995
996//     bool valid(const Node& n) const {
997//       return graph->valid(static_cast<typename Graph::Node>(n)); }
998//     bool valid(const Edge& e) const {
999//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
1000
1001//     int nodeNum() const { return graph->nodeNum(); }
1002//     int edgeNum() const { return graph->edgeNum(); }
1003 
1004//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1005//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1006//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1007//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1008 
1009//     Node addNode() const { return Node(graph->addNode()); }
1010//     Edge addEdge(const Node& tail, const Node& head) const {
1011//       return Edge(graph->addEdge(tail, head)); }
1012
1013//     void erase(const Node& i) const { graph->erase(i); }
1014//     void erase(const Edge& i) const { graph->erase(i); }
1015 
1016//     void clear() const { graph->clear(); }
1017   
1018//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1019//     public:
1020//       NodeMap(const GraphWrapper<Graph>& _G) : 
1021//      Graph::NodeMap<T>(*(_G.graph)) { }
1022//       NodeMap(const GraphWrapper<Graph>& _G, T a) :
1023//      Graph::NodeMap<T>(*(_G.graph), a) { }
1024//     };
1025
1026//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1027//     public:
1028//       EdgeMap(const GraphWrapper<Graph>& _G) : 
1029//      Graph::EdgeMap<T>(*(_G.graph)) { }
1030//       EdgeMap(const GraphWrapper<Graph>& _G, T a) :
1031//      Graph::EdgeMap<T>(*(_G.graph), a) { }
1032//     };
1033//   };
1034
1035} //namespace hugo
1036
1037#endif //HUGO_GRAPH_WRAPPER_H
1038
Note: See TracBrowser for help on using the repository browser.