COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 499:767f3da8ce0e

Last change on this file since 499:767f3da8ce0e was 499:767f3da8ce0e, checked in by marci, 20 years ago

A bipartite graph template can be used as BipartiteGraph?<ListGraph?>.

File size: 32.3 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 <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_filte_map;
314    }
315    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
316      edge_filter_map=&_edge_filte_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>(0) { }
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  /// A wrapper for composing the residual graph for directed flow and circulation problems.
545
546  /// A wrapper for composing the residual graph for directed flow and circulation problems.
547  template<typename Graph, typename Number,
548           typename CapacityMap, typename FlowMap>
549  class ResGraphWrapper : public GraphWrapper<Graph> {
550  protected:
551    const CapacityMap* capacity;
552    FlowMap* flow;
553
554    ResGraphWrapper() : GraphWrapper<Graph>(0),
555                        capacity(0), flow(0) { }
556    void setCapacityMap(const CapacityMap& _capacity_map) {
557      capacity_map=&_capacity_map;
558    }
559    void setFlowMap(FlowMap& _flow) {
560      flow=&_flow;
561    }
562
563  public:
564
565    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
566                    FlowMap& _flow) :
567      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
568
569    class Edge;
570    class OutEdgeIt;
571    friend class Edge;
572    friend class OutEdgeIt;
573
574    typedef typename GraphWrapper<Graph>::Node Node;
575    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
576    class Edge : public Graph::Edge {
577      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
578    protected:
579      bool forward; //true, iff forward
580//      typename Graph::Edge e;
581    public:
582      Edge() { }
583      Edge(const typename Graph::Edge& _e, bool _forward) :
584        Graph::Edge(_e), forward(_forward) { }
585      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
586//the unique invalid iterator
587      friend bool operator==(const Edge& u, const Edge& v) {
588        return (v.forward==u.forward &&
589                static_cast<typename Graph::Edge>(u)==
590                static_cast<typename Graph::Edge>(v));
591      }
592      friend bool operator!=(const Edge& u, const Edge& v) {
593        return (v.forward!=u.forward ||
594                static_cast<typename Graph::Edge>(u)!=
595                static_cast<typename Graph::Edge>(v));
596      }
597    };
598
599    class OutEdgeIt {
600      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
601    protected:
602      typename Graph::OutEdgeIt out;
603      typename Graph::InEdgeIt in;
604      bool forward;
605    public:
606      OutEdgeIt() { }
607      //FIXME
608//      OutEdgeIt(const Edge& e) : Edge(e) { }
609      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
610//the unique invalid iterator
611      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
612        forward=true;
613        resG.graph->first(out, v);
614        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
615        if (!resG.graph->valid(out)) {
616          forward=false;
617          resG.graph->first(in, v);
618          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
619        }
620      }
621      operator Edge() const {
622//      Edge e;
623//      e.forward=this->forward;
624//      if (this->forward) e=out; else e=in;
625//      return e;
626        if (this->forward)
627          return Edge(out, this->forward);
628        else
629          return Edge(in, this->forward);
630      }
631    };
632
633    class InEdgeIt {
634      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
635    protected:
636      typename Graph::OutEdgeIt out;
637      typename Graph::InEdgeIt in;
638      bool forward;
639    public:
640      InEdgeIt() { }
641      //FIXME
642//      OutEdgeIt(const Edge& e) : Edge(e) { }
643      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
644//the unique invalid iterator
645      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
646        forward=true;
647        resG.graph->first(in, v);
648        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
649        if (!resG.graph->valid(in)) {
650          forward=false;
651          resG.graph->first(out, v);
652          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
653        }
654      }
655      operator Edge() const {
656//      Edge e;
657//      e.forward=this->forward;
658//      if (this->forward) e=out; else e=in;
659//      return e;
660        if (this->forward)
661          return Edge(in, this->forward);
662        else
663          return Edge(out, this->forward);
664      }
665    };
666
667    class EdgeIt {
668      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
669    protected:
670      typename Graph::EdgeIt e;
671      bool forward;
672    public:
673      EdgeIt() { }
674      EdgeIt(const Invalid& i) : e(i), forward(false) { }
675      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
676        forward=true;
677        resG.graph->first(e);
678        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
679        if (!resG.graph->valid(e)) {
680          forward=false;
681          resG.graph->first(e);
682          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
683        }
684      }
685      operator Edge() const {
686        return Edge(e, this->forward);
687      }
688    };
689
690    using GraphWrapper<Graph>::first;
691//     NodeIt& first(NodeIt& i) const {
692//       i=NodeIt(*this); return i;
693//     }
694    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
695      i=OutEdgeIt(*this, p); return i;
696    }
697//    FIXME not tested
698    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
699      i=InEdgeIt(*this, p); return i;
700    }
701    EdgeIt& first(EdgeIt& i) const {
702      i=EdgeIt(*this); return i;
703    }
704 
705    using GraphWrapper<Graph>::next;
706//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
707    OutEdgeIt& next(OutEdgeIt& e) const {
708      if (e.forward) {
709        Node v=this->graph->aNode(e.out);
710        this->graph->next(e.out);
711        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
712          this->graph->next(e.out); }
713        if (!this->graph->valid(e.out)) {
714          e.forward=false;
715          this->graph->first(e.in, v);
716          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
717            this->graph->next(e.in); }
718        }
719      } else {
720        this->graph->next(e.in);
721        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
722          this->graph->next(e.in); }
723      }
724      return e;
725    }
726//     FIXME Not tested
727    InEdgeIt& next(InEdgeIt& e) const {
728      if (e.forward) {
729        Node v=this->graph->aNode(e.in);
730        this->graph->next(e.in);
731        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
732          this->graph->next(e.in); }
733        if (!this->graph->valid(e.in)) {
734          e.forward=false;
735          this->graph->first(e.out, v);
736          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
737            this->graph->next(e.out); }
738        }
739      } else {
740        this->graph->next(e.out);
741        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
742          this->graph->next(e.out); }
743      }
744      return e;
745    }
746    EdgeIt& next(EdgeIt& e) const {
747      if (e.forward) {
748        this->graph->next(e.e);
749        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
750          this->graph->next(e.e); }
751        if (!this->graph->valid(e.e)) {
752          e.forward=false;
753          this->graph->first(e.e);
754          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
755            this->graph->next(e.e); }
756        }
757      } else {
758        this->graph->next(e.e);
759        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
760          this->graph->next(e.e); }
761      }
762      return e;
763    }
764
765    Node tail(Edge e) const {
766      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
767    Node head(Edge e) const {
768      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
769
770    Node aNode(OutEdgeIt e) const {
771      return ((e.forward) ? this->graph->aNode(e.out) :
772              this->graph->aNode(e.in)); }
773    Node bNode(OutEdgeIt e) const {
774      return ((e.forward) ? this->graph->bNode(e.out) :
775              this->graph->bNode(e.in)); }
776
777    Node aNode(InEdgeIt e) const {
778      return ((e.forward) ? this->graph->aNode(e.in) :
779              this->graph->aNode(e.out)); }
780    Node bNode(InEdgeIt e) const {
781      return ((e.forward) ? this->graph->bNode(e.in) :
782              this->graph->bNode(e.out)); }
783
784//    int nodeNum() const { return graph->nodeNum(); }
785    //FIXME
786    void edgeNum() const { }
787    //int edgeNum() const { return graph->edgeNum(); }
788
789
790//    int id(Node v) const { return graph->id(v); }
791
792    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
793    bool valid(Edge e) const {
794      return this->graph->valid(e);
795        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
796    }
797
798    void augment(const Edge& e, Number a) const {
799      if (e.forward) 
800//      flow->set(e.out, flow->get(e.out)+a);
801        flow->set(e, (*flow)[e]+a);
802      else 
803//      flow->set(e.in, flow->get(e.in)-a);
804        flow->set(e, (*flow)[e]-a);
805    }
806
807    Number resCap(const Edge& e) const {
808      if (e.forward)
809//      return (capacity->get(e.out)-flow->get(e.out));
810        return ((*capacity)[e]-(*flow)[e]);
811      else
812//      return (flow->get(e.in));
813        return ((*flow)[e]);
814    }
815
816//     Number resCap(typename Graph::OutEdgeIt out) const {
817// //      return (capacity->get(out)-flow->get(out));
818//       return ((*capacity)[out]-(*flow)[out]);
819//     }
820   
821//     Number resCap(typename Graph::InEdgeIt in) const {
822// //      return (flow->get(in));
823//       return ((*flow)[in]);
824//     }
825
826    template <typename T>
827    class EdgeMap {
828      typename Graph::template EdgeMap<T> forward_map, backward_map;
829    public:
830      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
831      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
832      void set(Edge e, T a) {
833        if (e.forward)
834          forward_map.set(e.out, a);
835        else
836          backward_map.set(e.in, a);
837      }
838      T operator[](Edge e) const {
839        if (e.forward)
840          return forward_map[e.out];
841        else
842          return backward_map[e.in];
843      }
844//       T get(Edge e) const {
845//      if (e.out_or_in)
846//        return forward_map.get(e.out);
847//      else
848//        return backward_map.get(e.in);
849//       }
850    };
851  };
852
853  /// ErasingFirstGraphWrapper for blocking flows.
854
855  /// ErasingFirstGraphWrapper for blocking flows.
856  ///
857  ///\author Marton Makai
858  template<typename Graph, typename FirstOutEdgesMap>
859  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
860  protected:
861    FirstOutEdgesMap* first_out_edges;
862  public:
863    ErasingFirstGraphWrapper(Graph& _graph,
864                             FirstOutEdgesMap& _first_out_edges) :
865      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
866
867    typedef typename GraphWrapper<Graph>::Node Node;
868//     class NodeIt {
869//       friend class GraphWrapper<Graph>;
870//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
871//       typename Graph::NodeIt n;
872//      public:
873//       NodeIt() { }
874//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
875//       NodeIt(const Invalid& i) : n(i) { }
876//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
877//      n(*(_G.graph)) { }
878//       operator Node() const { return Node(typename Graph::Node(n)); }
879//     };
880    typedef typename GraphWrapper<Graph>::Edge Edge;
881    class OutEdgeIt {
882      friend class GraphWrapper<Graph>;
883      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
884//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
885      typename Graph::OutEdgeIt e;
886    public:
887      OutEdgeIt() { }
888      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
889      OutEdgeIt(const Invalid& i) : e(i) { }
890      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
891                const Node& _n) :
892        e((*_G.first_out_edges)[_n]) { }
893      operator Edge() const { return Edge(typename Graph::Edge(e)); }
894    };
895    class InEdgeIt {
896      friend class GraphWrapper<Graph>;
897      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
898//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
899      typename Graph::InEdgeIt e;
900    public:
901      InEdgeIt() { }
902      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
903      InEdgeIt(const Invalid& i) : e(i) { }
904      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
905               const Node& _n) :
906        e(*(_G.graph), typename Graph::Node(_n)) { }
907      operator Edge() const { return Edge(typename Graph::Edge(e)); }
908    };
909    //typedef typename Graph::SymEdgeIt SymEdgeIt;
910    class EdgeIt {
911      friend class GraphWrapper<Graph>;
912      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
913//      typedef typename Graph::EdgeIt GraphEdgeIt;
914      typename Graph::EdgeIt e;
915    public:
916      EdgeIt() { }
917      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
918      EdgeIt(const Invalid& i) : e(i) { }
919      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
920        e(*(_G.graph)) { }
921      operator Edge() const { return Edge(typename Graph::Edge(e)); }
922    };
923
924    using GraphWrapper<Graph>::first;
925//     NodeIt& first(NodeIt& i) const {
926//       i=NodeIt(*this); return i;
927//     }
928    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
929      i=OutEdgeIt(*this, p); return i;
930    }
931    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
932      i=InEdgeIt(*this, p); return i;
933    }
934    EdgeIt& first(EdgeIt& i) const {
935      i=EdgeIt(*this); return i;
936    }
937
938    using GraphWrapper<Graph>::next;
939//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
940    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
941    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
942    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
943   
944    Node aNode(const OutEdgeIt& e) const {
945      return Node(this->graph->aNode(e.e)); }
946    Node aNode(const InEdgeIt& e) const {
947      return Node(this->graph->aNode(e.e)); }
948    Node bNode(const OutEdgeIt& e) const {
949      return Node(this->graph->bNode(e.e)); }
950    Node bNode(const InEdgeIt& e) const {
951      return Node(this->graph->bNode(e.e)); }
952
953    void erase(const OutEdgeIt& e) const {
954      OutEdgeIt f=e;
955      this->next(f);
956      first_out_edges->set(this->tail(e), f.e);
957    }
958  };
959
960  ///@}
961
962} //namespace hugo
963
964
965#endif //HUGO_GRAPH_WRAPPER_H
966
Note: See TracBrowser for help on using the repository browser.