COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 357:5165a1c8633e

Last change on this file since 357:5165a1c8633e was 357:5165a1c8633e, checked in by Alpar Juttner, 17 years ago

Requests for docs.

File size: 36.3 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    ///\todo
388    ///Some doki, please.
389    void hide(const Node& n) const { node_filter_map->set(n, false); }
390    ///\todo
391    ///Some doki, please.
392    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
393
394    ///\todo
395    ///Some doki, please.
396    void unHide(const Node& n) const { node_filter_map->set(n, true); }
397    ///\todo
398    ///Some doki, please.
399    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
400
401    ///\todo
402    ///Some doki, please.
403    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
404    ///\todo
405    ///Some doki, please.
406    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
407  };
408
409  /// A wrapper for forgetting the orientation of a graph.
410
411  /// A wrapper for getting an undirected graph by forgetting
412  /// the orientation of a directed one.
413  template<typename Graph>
414  class UndirGraphWrapper : public GraphWrapper<Graph> {
415  public:
416    typedef typename GraphWrapper<Graph>::Node Node;
417    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
418    typedef typename GraphWrapper<Graph>::Edge Edge;
419    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
420
421    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
422
423    class OutEdgeIt {
424      friend class UndirGraphWrapper<Graph>;
425      bool out_or_in; //true iff out
426      typename Graph::OutEdgeIt out;
427      typename Graph::InEdgeIt in;
428    public:
429      OutEdgeIt() { }
430      OutEdgeIt(const Invalid& i) : Edge(i) { }
431      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
432        out_or_in=true; _G.graph->first(out, _n);
433        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
434      }
435      operator Edge() const {
436        if (out_or_in) return Edge(out); else return Edge(in);
437      }
438    };
439
440//FIXME InEdgeIt
441    typedef OutEdgeIt InEdgeIt;
442
443    using GraphWrapper<Graph>::first;
444//     NodeIt& first(NodeIt& i) const {
445//       i=NodeIt(*this); return i;
446//     }
447    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
448      i=OutEdgeIt(*this, p); return i;
449    }
450//FIXME
451//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
452//       i=InEdgeIt(*this, p); return i;
453//     }
454//     EdgeIt& first(EdgeIt& i) const {
455//       i=EdgeIt(*this); return i;
456//     }
457
458    using GraphWrapper<Graph>::next;
459//     NodeIt& next(NodeIt& n) const {
460//       GraphWrapper<Graph>::next(n);
461//       return n;
462//     }
463    OutEdgeIt& next(OutEdgeIt& e) const {
464      if (e.out_or_in) {
465        typename Graph::Node n=graph->tail(e.out);
466        graph->next(e.out);
467        if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
468      } else {
469        graph->next(e.in);
470      }
471      return e;
472    }
473    //FIXME InEdgeIt
474//     EdgeIt& next(EdgeIt& e) const {
475//       GraphWrapper<Graph>::next(n);
476// //      graph->next(e.e);
477//       return e;
478//     }
479
480    Node aNode(const OutEdgeIt& e) const {
481      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
482    Node bNode(const OutEdgeIt& e) const {
483      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
484  };
485 
486  /// A wrapper for composing the residual graph for directed flow and circulation problems.
487
488  /// A wrapper for composing the residual graph for directed flow and circulation problems.
489  template<typename Graph, typename Number,
490           typename CapacityMap, typename FlowMap>
491  class ResGraphWrapper : public GraphWrapper<Graph> {
492  protected:
493    const CapacityMap* capacity;
494    FlowMap* flow;
495  public:
496
497    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
498                    FlowMap& _flow) :
499      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
500
501    class Edge;
502    class OutEdgeIt;
503    friend class Edge;
504    friend class OutEdgeIt;
505
506    typedef typename GraphWrapper<Graph>::Node Node;
507    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
508    class Edge : public Graph::Edge {
509      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
510    protected:
511      bool forward; //true, iff forward
512//      typename Graph::Edge e;
513    public:
514      Edge() { }
515      Edge(const typename Graph::Edge& _e, bool _forward) :
516        Graph::Edge(_e), forward(_forward) { }
517      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
518//the unique invalid iterator
519      friend bool operator==(const Edge& u, const Edge& v) {
520        return (v.forward==u.forward &&
521                static_cast<typename Graph::Edge>(u)==
522                static_cast<typename Graph::Edge>(v));
523      }
524      friend bool operator!=(const Edge& u, const Edge& v) {
525        return (v.forward!=u.forward ||
526                static_cast<typename Graph::Edge>(u)!=
527                static_cast<typename Graph::Edge>(v));
528      }
529    };
530
531    class OutEdgeIt {
532      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
533    protected:
534      typename Graph::OutEdgeIt out;
535      typename Graph::InEdgeIt in;
536      bool forward;
537    public:
538      OutEdgeIt() { }
539      //FIXME
540//      OutEdgeIt(const Edge& e) : Edge(e) { }
541      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
542//the unique invalid iterator
543      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
544        forward=true;
545        resG.graph->first(out, v);
546        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
547        if (!resG.graph->valid(out)) {
548          forward=false;
549          resG.graph->first(in, v);
550          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
551        }
552      }
553      operator Edge() const {
554//      Edge e;
555//      e.forward=this->forward;
556//      if (this->forward) e=out; else e=in;
557//      return e;
558        if (this->forward)
559          return Edge(out, this->forward);
560        else
561          return Edge(in, this->forward);
562      }
563    };
564
565    class InEdgeIt {
566      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
567    protected:
568      typename Graph::OutEdgeIt out;
569      typename Graph::InEdgeIt in;
570      bool forward;
571    public:
572      InEdgeIt() { }
573      //FIXME
574//      OutEdgeIt(const Edge& e) : Edge(e) { }
575      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
576//the unique invalid iterator
577      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
578        forward=true;
579        resG.graph->first(in, v);
580        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
581        if (!resG.graph->valid(in)) {
582          forward=false;
583          resG.graph->first(out, v);
584          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
585        }
586      }
587      operator Edge() const {
588//      Edge e;
589//      e.forward=this->forward;
590//      if (this->forward) e=out; else e=in;
591//      return e;
592        if (this->forward)
593          return Edge(in, this->forward);
594        else
595          return Edge(out, this->forward);
596      }
597    };
598
599    class EdgeIt {
600      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
601    protected:
602      typename Graph::EdgeIt e;
603      bool forward;
604    public:
605      EdgeIt() { }
606      EdgeIt(const Invalid& i) : e(i), forward(false) { }
607      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
608        forward=true;
609        resG.graph->first(e);
610        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
611        if (!resG.graph->valid(e)) {
612          forward=false;
613          resG.graph->first(e);
614          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
615        }
616      }
617      operator Edge() const {
618        return Edge(e, this->forward);
619      }
620    };
621
622    using GraphWrapper<Graph>::first;
623//     NodeIt& first(NodeIt& i) const {
624//       i=NodeIt(*this); return i;
625//     }
626    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
627      i=OutEdgeIt(*this, p); return i;
628    }
629//    FIXME not tested
630    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
631      i=InEdgeIt(*this, p); return i;
632    }
633    EdgeIt& first(EdgeIt& i) const {
634      i=EdgeIt(*this); return i;
635    }
636 
637    using GraphWrapper<Graph>::next;
638//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
639    OutEdgeIt& next(OutEdgeIt& e) const {
640      if (e.forward) {
641        Node v=graph->aNode(e.out);
642        graph->next(e.out);
643        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
644        if (!graph->valid(e.out)) {
645          e.forward=false;
646          graph->first(e.in, v);
647          while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
648        }
649      } else {
650        graph->next(e.in);
651        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
652      }
653      return e;
654    }
655//     FIXME Not tested
656    InEdgeIt& next(InEdgeIt& e) const {
657      if (e.forward) {
658        Node v=graph->aNode(e.in);
659        graph->next(e.in);
660        while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
661        if (!graph->valid(e.in)) {
662          e.forward=false;
663          graph->first(e.out, v);
664          while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
665        }
666      } else {
667        graph->next(e.out);
668        while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
669      }
670      return e;
671    }
672    EdgeIt& next(EdgeIt& e) const {
673      if (e.forward) {
674        graph->next(e.e);
675        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
676        if (!graph->valid(e.e)) {
677          e.forward=false;
678          graph->first(e.e);
679          while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
680        }
681      } else {
682        graph->next(e.e);
683        while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
684      }
685      return e;
686    }
687
688    Node tail(Edge e) const {
689      return ((e.forward) ? graph->tail(e) : graph->head(e)); }
690    Node head(Edge e) const {
691      return ((e.forward) ? graph->head(e) : graph->tail(e)); }
692
693    Node aNode(OutEdgeIt e) const {
694      return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
695    Node bNode(OutEdgeIt e) const {
696      return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
697
698//    int nodeNum() const { return graph->nodeNum(); }
699    //FIXME
700    void edgeNum() const { }
701    //int edgeNum() const { return graph->edgeNum(); }
702
703
704//    int id(Node v) const { return graph->id(v); }
705
706    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
707    bool valid(Edge e) const {
708      return graph->valid(e);
709        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
710    }
711
712    void augment(const Edge& e, Number a) const {
713      if (e.forward) 
714//      flow->set(e.out, flow->get(e.out)+a);
715        flow->set(e, (*flow)[e]+a);
716      else 
717//      flow->set(e.in, flow->get(e.in)-a);
718        flow->set(e, (*flow)[e]-a);
719    }
720
721    Number resCap(const Edge& e) const {
722      if (e.forward)
723//      return (capacity->get(e.out)-flow->get(e.out));
724        return ((*capacity)[e]-(*flow)[e]);
725      else
726//      return (flow->get(e.in));
727        return ((*flow)[e]);
728    }
729
730//     Number resCap(typename Graph::OutEdgeIt out) const {
731// //      return (capacity->get(out)-flow->get(out));
732//       return ((*capacity)[out]-(*flow)[out]);
733//     }
734   
735//     Number resCap(typename Graph::InEdgeIt in) const {
736// //      return (flow->get(in));
737//       return ((*flow)[in]);
738//     }
739
740    template <typename T>
741    class EdgeMap {
742      typename Graph::EdgeMap<T> forward_map, backward_map;
743    public:
744      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
745      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
746      void set(Edge e, T a) {
747        if (e.forward)
748          forward_map.set(e.out, a);
749        else
750          backward_map.set(e.in, a);
751      }
752      T operator[](Edge e) const {
753        if (e.forward)
754          return forward_map[e.out];
755        else
756          return backward_map[e.in];
757      }
758//       T get(Edge e) const {
759//      if (e.out_or_in)
760//        return forward_map.get(e.out);
761//      else
762//        return backward_map.get(e.in);
763//       }
764    };
765  };
766
767  /// ErasingFirstGraphWrapper for blocking flows.
768
769  /// ErasingFirstGraphWrapper for blocking flows.
770  template<typename Graph, typename FirstOutEdgesMap>
771  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
772  protected:
773    FirstOutEdgesMap* first_out_edges;
774  public:
775    ErasingFirstGraphWrapper(Graph& _graph,
776                             FirstOutEdgesMap& _first_out_edges) :
777      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
778
779    typedef typename GraphWrapper<Graph>::Node Node;
780//     class NodeIt {
781//       friend class GraphWrapper<Graph>;
782//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
783//       typename Graph::NodeIt n;
784//      public:
785//       NodeIt() { }
786//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
787//       NodeIt(const Invalid& i) : n(i) { }
788//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
789//      n(*(_G.graph)) { }
790//       operator Node() const { return Node(typename Graph::Node(n)); }
791//     };
792    typedef typename GraphWrapper<Graph>::Edge Edge;
793    class OutEdgeIt {
794      friend class GraphWrapper<Graph>;
795      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
796//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
797      typename Graph::OutEdgeIt e;
798    public:
799      OutEdgeIt() { }
800      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
801      OutEdgeIt(const Invalid& i) : e(i) { }
802      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
803                const Node& _n) :
804        e((*_G.first_out_edges)[_n]) { }
805      operator Edge() const { return Edge(typename Graph::Edge(e)); }
806    };
807    class InEdgeIt {
808      friend class GraphWrapper<Graph>;
809      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
810//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
811      typename Graph::InEdgeIt e;
812    public:
813      InEdgeIt() { }
814      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
815      InEdgeIt(const Invalid& i) : e(i) { }
816      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
817               const Node& _n) :
818        e(*(_G.graph), typename Graph::Node(_n)) { }
819      operator Edge() const { return Edge(typename Graph::Edge(e)); }
820    };
821    //typedef typename Graph::SymEdgeIt SymEdgeIt;
822    class EdgeIt {
823      friend class GraphWrapper<Graph>;
824      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
825//      typedef typename Graph::EdgeIt GraphEdgeIt;
826      typename Graph::EdgeIt e;
827    public:
828      EdgeIt() { }
829      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
830      EdgeIt(const Invalid& i) : e(i) { }
831      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
832        e(*(_G.graph)) { }
833      operator Edge() const { return Edge(typename Graph::Edge(e)); }
834    };
835
836    using GraphWrapper<Graph>::first;
837//     NodeIt& first(NodeIt& i) const {
838//       i=NodeIt(*this); return i;
839//     }
840    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
841      i=OutEdgeIt(*this, p); return i;
842    }
843    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
844      i=InEdgeIt(*this, p); return i;
845    }
846    EdgeIt& first(EdgeIt& i) const {
847      i=EdgeIt(*this); return i;
848    }
849
850    using GraphWrapper<Graph>::next;
851//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
852    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
853    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
854    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
855   
856    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
857    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
858    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
859    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
860
861    void erase(const OutEdgeIt& e) const {
862      OutEdgeIt f=e;
863      this->next(f);
864      first_out_edges->set(this->tail(e), f.e);
865    }
866  };
867
868
869
870//   /// experimentral, do not try it.
871//   template<typename Graph>
872//   class stGraphWrapper : public GraphWrapper<Graph> {
873//   public:
874//     class Node;
875//     class NodeIt;
876//     class Edge;
877//     class OutEdgeIt;
878//     class InEdgeIt;
879//     class EdgeIt;
880
881//     const Node s;
882//     const Node t;
883
884//     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),
885//                                  s(INVALID, 1), t(INVALID, 2) { }
886
887//     class Node : public Graph::Node {
888//       friend class GraphWrapper<Graph>;
889//       friend class stGraphWrapper<Graph>;
890//     protected:
891//       int spec; //0 if real node, 1 iff s, 2 iff t
892//     public:
893//       Node() { }
894//       Node(const typename Graph::Node& _n, int _spec=0) :
895//      Graph::Node(_n), spec(_spec) { }
896//       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
897//       //invalid: (invalid, 2);
898//     };
899
900//     class NodeIt {
901//       friend class GraphWrapper<Graph>;
902//       friend class stGraphWrapper<Graph>;
903//       typename Graph::NodeIt n;
904//       int spec;
905//      public:
906//       NodeIt() { }
907//       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :
908//      n(_n), spec(_spec) { }
909//       NodeIt(const Invalid& i) : n(i), spec(2) { }
910//       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
911//      if (!_G->valid(n)) spec=1;
912//       }
913//       operator Node() const { return Node(n, spec); }
914//     };
915// //    typedef typename Graph::Edge Edge;
916//     class Edge : public Graph::Edge {
917//       friend class GraphWrapper<Graph>;
918//       friend class stGraphWrapper<Graph>;
919//       Node tail_spec;
920//       Node head_spec;
921//     public:
922//       Edge() { }
923//       Edge(const typename Graph::Edge& _e) :
924//      Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {
925//      //a tail-t es a head-et real node-ra csinaljuk
926//       }
927//       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
928//     };
929//     class OutEdgeIt {
930//       friend class GraphWrapper<Graph>;
931//       friend class stGraphWrapper<Graph>;
932//       typename Graph::OutEdgeIt e;
933//       Node tail_spec;
934//       Node head_spec;
935//     public:
936//       OutEdgeIt() { }
937//       OutEdgeIt(const typename Graph::OutEdgeIt& _e) :
938//      e(_e), tail_spec(i, 0), head_spec(i, 0) {
939//      //a tail-t es a head-et real node-ra csinaljuk
940//       }
941//       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
942//       //invalid: (barmi, 0, 2)
943//       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
944//      switch (_n.spec) {
945//      case 0 :
946//        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
947//        _tail.spec=0;
948//        _head.spec=0;
949//        if (!_G.graph->valid(e)) spec=1;
950//        break;
951//      case 1:
952//        e=INVALID;
953//        _tail.spec=1;
954//        _head(_G.graph->first(typename Graph::NodeIt()));
955//        if _head.spec==1
956//        break;
957//      };
958       
959//        }
960//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
961//     };
962//     class InEdgeIt {
963//       friend class GraphWrapper<Graph>;
964//       typename Graph::InEdgeIt e;
965//     public:
966//       InEdgeIt() { }
967//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
968//       InEdgeIt(const Invalid& i) : e(i) { }
969//       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
970//      e(*(_G.graph), typename Graph::Node(_n)) { }
971//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
972//     };
973//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
974//     class EdgeIt {
975//       friend class GraphWrapper<Graph>;
976//       typename Graph::EdgeIt e;
977//     public:
978//       EdgeIt() { }
979//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
980//       EdgeIt(const Invalid& i) : e(i) { }
981//       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
982//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
983//     };
984   
985//     NodeIt& first(NodeIt& i) const {
986//       i=NodeIt(*this); return i;
987//     }
988//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
989//       i=OutEdgeIt(*this, p); return i;
990//     }
991//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
992//       i=InEdgeIt(*this, p); return i;
993//     }
994//     EdgeIt& first(EdgeIt& i) const {
995//       i=EdgeIt(*this); return i;
996//     }
997
998//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
999//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
1000//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1001//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
1002
1003//     Node head(const Edge& e) const {
1004//       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1005//     Node tail(const Edge& e) const {
1006//       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
1007
1008//     bool valid(const Node& n) const {
1009//       return graph->valid(static_cast<typename Graph::Node>(n)); }
1010//     bool valid(const Edge& e) const {
1011//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
1012
1013//     int nodeNum() const { return graph->nodeNum(); }
1014//     int edgeNum() const { return graph->edgeNum(); }
1015 
1016//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1017//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
1018//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1019//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
1020 
1021//     Node addNode() const { return Node(graph->addNode()); }
1022//     Edge addEdge(const Node& tail, const Node& head) const {
1023//       return Edge(graph->addEdge(tail, head)); }
1024
1025//     void erase(const Node& i) const { graph->erase(i); }
1026//     void erase(const Edge& i) const { graph->erase(i); }
1027 
1028//     void clear() const { graph->clear(); }
1029   
1030//     template<typename T> class NodeMap : public Graph::NodeMap<T> {
1031//     public:
1032//       NodeMap(const GraphWrapper<Graph>& _G) : 
1033//      Graph::NodeMap<T>(*(_G.graph)) { }
1034//       NodeMap(const GraphWrapper<Graph>& _G, T a) :
1035//      Graph::NodeMap<T>(*(_G.graph), a) { }
1036//     };
1037
1038//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1039//     public:
1040//       EdgeMap(const GraphWrapper<Graph>& _G) : 
1041//      Graph::EdgeMap<T>(*(_G.graph)) { }
1042//       EdgeMap(const GraphWrapper<Graph>& _G, T a) :
1043//      Graph::EdgeMap<T>(*(_G.graph), a) { }
1044//     };
1045//   };
1046
1047} //namespace hugo
1048
1049#endif //HUGO_GRAPH_WRAPPER_H
1050
Note: See TracBrowser for help on using the repository browser.