COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 341:6046b1d0f267

Last change on this file since 341:6046b1d0f267 was 341:6046b1d0f267, checked in by marci, 20 years ago

semmi

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