COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 553:8e5102790d4d

Last change on this file since 553:8e5102790d4d was 553:8e5102790d4d, checked in by marci, 20 years ago

SubGraphWrapper? bug ok

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