# source:lemon-0.x/src/work/marci/graph_wrapper.h@338:e8725f30dd98

Last change on this file since 338:e8725f30dd98 was 338:e8725f30dd98, checked in by marci, 17 years ago

kicsit takaritottam, es szepitettem es, es maga a csuda, de azer nem
teljesen mer' meg kell csinalni vele dolgokat.

File size: 29.9 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 {
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
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} //namespace hugo
856
857#endif //HUGO_GRAPH_WRAPPER_H
858
Note: See TracBrowser for help on using the repository browser.