COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 561:a10e6f1769e2

Last change on this file since 561:a10e6f1769e2 was 561:a10e6f1769e2, checked in by marci, 20 years ago
File size: 33.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 <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    /// This function hides \c n in the graph, i.e. the iteration
440    /// jumps over it. This is done by simply setting the value of \c n 
441    /// to be false in the corresponding node-map.
442    void hide(const Node& n) const { node_filter_map->set(n, false); }
443
444    /// This function hides \c e in the graph, i.e. the iteration
445    /// jumps over it. This is done by simply setting the value of \c e 
446    /// to be false in the corresponding edge-map.
447    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
448
449    /// The value of \c n is set to be true in the node-map which stores
450    /// hide information. If \c n was hidden previuosly, then it is shown
451    /// again
452     void unHide(const Node& n) const { node_filter_map->set(n, true); }
453
454    /// The value of \c e is set to be true in the edge-map which stores
455    /// hide information. If \c e was hidden previuosly, then it is shown
456    /// again
457    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
458
459    /// Returns true if \c n is hidden.
460    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
461
462    /// Returns true if \c n is hidden.
463    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
464  };
465
466  /// A wrapper for forgetting the orientation of a graph.
467
468  /// A wrapper for getting an undirected graph by forgetting
469  /// the orientation of a directed one.
470  template<typename Graph>
471  class UndirGraphWrapper : public GraphWrapper<Graph> {
472  protected:
473    UndirGraphWrapper() : GraphWrapper<Graph>() { }
474   
475  public:
476    typedef typename GraphWrapper<Graph>::Node Node;
477    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
478    typedef typename GraphWrapper<Graph>::Edge Edge;
479    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
480
481    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
482
483    class OutEdgeIt {
484      friend class UndirGraphWrapper<Graph>;
485      bool out_or_in; //true iff out
486      typename Graph::OutEdgeIt out;
487      typename Graph::InEdgeIt in;
488    public:
489      OutEdgeIt() { }
490      OutEdgeIt(const Invalid& i) : Edge(i) { }
491      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
492        out_or_in=true; _G.graph->first(out, _n);
493        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
494      }
495      operator Edge() const {
496        if (out_or_in) return Edge(out); else return Edge(in);
497      }
498    };
499
500//FIXME InEdgeIt
501    typedef OutEdgeIt InEdgeIt;
502
503    using GraphWrapper<Graph>::first;
504//     NodeIt& first(NodeIt& i) const {
505//       i=NodeIt(*this); return i;
506//     }
507    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
508      i=OutEdgeIt(*this, p); return i;
509    }
510//FIXME
511//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
512//       i=InEdgeIt(*this, p); return i;
513//     }
514//     EdgeIt& first(EdgeIt& i) const {
515//       i=EdgeIt(*this); return i;
516//     }
517
518    using GraphWrapper<Graph>::next;
519//     NodeIt& next(NodeIt& n) const {
520//       GraphWrapper<Graph>::next(n);
521//       return n;
522//     }
523    OutEdgeIt& next(OutEdgeIt& e) const {
524      if (e.out_or_in) {
525        typename Graph::Node n=this->graph->tail(e.out);
526        this->graph->next(e.out);
527        if (!this->graph->valid(e.out)) {
528          e.out_or_in=false; this->graph->first(e.in, n); }
529      } else {
530        this->graph->next(e.in);
531      }
532      return e;
533    }
534    //FIXME InEdgeIt
535//     EdgeIt& next(EdgeIt& e) const {
536//       GraphWrapper<Graph>::next(n);
537// //      graph->next(e.e);
538//       return e;
539//     }
540
541    Node aNode(const OutEdgeIt& e) const {
542      if (e.out_or_in) return this->graph->tail(e); else
543        return this->graph->head(e); }
544    Node bNode(const OutEdgeIt& e) const {
545      if (e.out_or_in) return this->graph->head(e); else
546        return this->graph->tail(e); }
547  };
548 
549
550
551  /// An undirected graph template
552  template<typename Graph>
553  class UndirGraph : public UndirGraphWrapper<Graph> {
554    typedef UndirGraphWrapper<Graph> Parent;
555  protected:
556    Graph gr;
557  public:
558    UndirGraph() : UndirGraphWrapper<Graph>() {
559      Parent::setGraph(gr);
560    }
561  };
562
563 
564
565  /// A wrapper for composing the residual graph for directed flow and circulation problems.
566
567  /// A wrapper for composing the residual graph for directed flow and circulation problems.
568  template<typename Graph, typename Number,
569           typename CapacityMap, typename FlowMap>
570  class ResGraphWrapper : public GraphWrapper<Graph> {
571  protected:
572    const CapacityMap* capacity;
573    FlowMap* flow;
574
575    ResGraphWrapper() : GraphWrapper<Graph>(0),
576                        capacity(0), flow(0) { }
577    void setCapacityMap(const CapacityMap& _capacity) {
578      capacity=&_capacity;
579    }
580    void setFlowMap(FlowMap& _flow) {
581      flow=&_flow;
582    }
583
584  public:
585
586    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
587                    FlowMap& _flow) :
588      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
589
590    class Edge;
591    class OutEdgeIt;
592    friend class Edge;
593    friend class OutEdgeIt;
594
595    typedef typename GraphWrapper<Graph>::Node Node;
596    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
597    class Edge : public Graph::Edge {
598      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
599    protected:
600      bool forward; //true, iff forward
601//      typename Graph::Edge e;
602    public:
603      Edge() { }
604      Edge(const typename Graph::Edge& _e, bool _forward) :
605        Graph::Edge(_e), forward(_forward) { }
606      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
607//the unique invalid iterator
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      friend bool operator!=(const Edge& u, const Edge& v) {
614        return (v.forward!=u.forward ||
615                static_cast<typename Graph::Edge>(u)!=
616                static_cast<typename Graph::Edge>(v));
617      }
618    };
619
620    class OutEdgeIt {
621      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
622    protected:
623      typename Graph::OutEdgeIt out;
624      typename Graph::InEdgeIt in;
625      bool forward;
626    public:
627      OutEdgeIt() { }
628      //FIXME
629//      OutEdgeIt(const Edge& e) : Edge(e) { }
630      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
631//the unique invalid iterator
632      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
633        forward=true;
634        resG.graph->first(out, v);
635        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
636        if (!resG.graph->valid(out)) {
637          forward=false;
638          resG.graph->first(in, v);
639          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
640        }
641      }
642      operator Edge() const {
643//      Edge e;
644//      e.forward=this->forward;
645//      if (this->forward) e=out; else e=in;
646//      return e;
647        if (this->forward)
648          return Edge(out, this->forward);
649        else
650          return Edge(in, this->forward);
651      }
652    };
653
654    class InEdgeIt {
655      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
656    protected:
657      typename Graph::OutEdgeIt out;
658      typename Graph::InEdgeIt in;
659      bool forward;
660    public:
661      InEdgeIt() { }
662      //FIXME
663//      OutEdgeIt(const Edge& e) : Edge(e) { }
664      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
665//the unique invalid iterator
666      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
667        forward=true;
668        resG.graph->first(in, v);
669        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
670        if (!resG.graph->valid(in)) {
671          forward=false;
672          resG.graph->first(out, v);
673          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
674        }
675      }
676      operator Edge() const {
677//      Edge e;
678//      e.forward=this->forward;
679//      if (this->forward) e=out; else e=in;
680//      return e;
681        if (this->forward)
682          return Edge(in, this->forward);
683        else
684          return Edge(out, this->forward);
685      }
686    };
687
688    class EdgeIt {
689      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
690    protected:
691      typename Graph::EdgeIt e;
692      bool forward;
693    public:
694      EdgeIt() { }
695      EdgeIt(const Invalid& i) : e(i), forward(false) { }
696      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
697        forward=true;
698        resG.graph->first(e);
699        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
700        if (!resG.graph->valid(e)) {
701          forward=false;
702          resG.graph->first(e);
703          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
704        }
705      }
706      operator Edge() const {
707        return Edge(e, this->forward);
708      }
709    };
710
711    using GraphWrapper<Graph>::first;
712//     NodeIt& first(NodeIt& i) const {
713//       i=NodeIt(*this); return i;
714//     }
715    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
716      i=OutEdgeIt(*this, p); return i;
717    }
718//    FIXME not tested
719    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
720      i=InEdgeIt(*this, p); return i;
721    }
722    EdgeIt& first(EdgeIt& i) const {
723      i=EdgeIt(*this); return i;
724    }
725 
726    using GraphWrapper<Graph>::next;
727//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
728    OutEdgeIt& next(OutEdgeIt& e) const {
729      if (e.forward) {
730        Node v=this->graph->aNode(e.out);
731        this->graph->next(e.out);
732        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
733          this->graph->next(e.out); }
734        if (!this->graph->valid(e.out)) {
735          e.forward=false;
736          this->graph->first(e.in, v);
737          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
738            this->graph->next(e.in); }
739        }
740      } else {
741        this->graph->next(e.in);
742        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
743          this->graph->next(e.in); }
744      }
745      return e;
746    }
747//     FIXME Not tested
748    InEdgeIt& next(InEdgeIt& e) const {
749      if (e.forward) {
750        Node v=this->graph->aNode(e.in);
751        this->graph->next(e.in);
752        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
753          this->graph->next(e.in); }
754        if (!this->graph->valid(e.in)) {
755          e.forward=false;
756          this->graph->first(e.out, v);
757          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
758            this->graph->next(e.out); }
759        }
760      } else {
761        this->graph->next(e.out);
762        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
763          this->graph->next(e.out); }
764      }
765      return e;
766    }
767    EdgeIt& next(EdgeIt& e) const {
768      if (e.forward) {
769        this->graph->next(e.e);
770        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
771          this->graph->next(e.e); }
772        if (!this->graph->valid(e.e)) {
773          e.forward=false;
774          this->graph->first(e.e);
775          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
776            this->graph->next(e.e); }
777        }
778      } else {
779        this->graph->next(e.e);
780        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
781          this->graph->next(e.e); }
782      }
783      return e;
784    }
785
786    Node tail(Edge e) const {
787      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
788    Node head(Edge e) const {
789      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
790
791    Node aNode(OutEdgeIt e) const {
792      return ((e.forward) ? this->graph->aNode(e.out) :
793              this->graph->aNode(e.in)); }
794    Node bNode(OutEdgeIt e) const {
795      return ((e.forward) ? this->graph->bNode(e.out) :
796              this->graph->bNode(e.in)); }
797
798    Node aNode(InEdgeIt e) const {
799      return ((e.forward) ? this->graph->aNode(e.in) :
800              this->graph->aNode(e.out)); }
801    Node bNode(InEdgeIt e) const {
802      return ((e.forward) ? this->graph->bNode(e.in) :
803              this->graph->bNode(e.out)); }
804
805//    int nodeNum() const { return graph->nodeNum(); }
806    //FIXME
807    void edgeNum() const { }
808    //int edgeNum() const { return graph->edgeNum(); }
809
810
811//    int id(Node v) const { return graph->id(v); }
812
813    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
814    bool valid(Edge e) const {
815      return this->graph->valid(e);
816        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
817    }
818
819    bool forward(const Edge& e) const { return e.forward; }
820    bool backward(const Edge& e) const { return !e.forward; }
821
822    void augment(const Edge& e, Number a) const {
823      if (e.forward) 
824//      flow->set(e.out, flow->get(e.out)+a);
825        flow->set(e, (*flow)[e]+a);
826      else 
827//      flow->set(e.in, flow->get(e.in)-a);
828        flow->set(e, (*flow)[e]-a);
829    }
830
831    Number resCap(const Edge& e) const {
832      if (e.forward)
833//      return (capacity->get(e.out)-flow->get(e.out));
834        return ((*capacity)[e]-(*flow)[e]);
835      else
836//      return (flow->get(e.in));
837        return ((*flow)[e]);
838    }
839
840//     Number resCap(typename Graph::OutEdgeIt out) const {
841// //      return (capacity->get(out)-flow->get(out));
842//       return ((*capacity)[out]-(*flow)[out]);
843//     }
844   
845//     Number resCap(typename Graph::InEdgeIt in) const {
846// //      return (flow->get(in));
847//       return ((*flow)[in]);
848//     }
849
850    template <typename T>
851    class EdgeMap {
852      typename Graph::template EdgeMap<T> forward_map, backward_map;
853    public:
854      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
855      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
856      void set(Edge e, T a) {
857        if (e.forward)
858          forward_map.set(e.out, a);
859        else
860          backward_map.set(e.in, a);
861      }
862      T operator[](Edge e) const {
863        if (e.forward)
864          return forward_map[e.out];
865        else
866          return backward_map[e.in];
867      }
868//       T get(Edge e) const {
869//      if (e.out_or_in)
870//        return forward_map.get(e.out);
871//      else
872//        return backward_map.get(e.in);
873//       }
874    };
875  };
876
877  /// ErasingFirstGraphWrapper for blocking flows.
878
879  /// ErasingFirstGraphWrapper for blocking flows.
880  ///
881  ///\author Marton Makai
882  template<typename Graph, typename FirstOutEdgesMap>
883  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
884  protected:
885    FirstOutEdgesMap* first_out_edges;
886  public:
887    ErasingFirstGraphWrapper(Graph& _graph,
888                             FirstOutEdgesMap& _first_out_edges) :
889      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
890
891    typedef typename GraphWrapper<Graph>::Node Node;
892//     class NodeIt {
893//       friend class GraphWrapper<Graph>;
894//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
895//       typename Graph::NodeIt n;
896//      public:
897//       NodeIt() { }
898//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
899//       NodeIt(const Invalid& i) : n(i) { }
900//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
901//      n(*(_G.graph)) { }
902//       operator Node() const { return Node(typename Graph::Node(n)); }
903//     };
904    typedef typename GraphWrapper<Graph>::Edge Edge;
905    class OutEdgeIt {
906      friend class GraphWrapper<Graph>;
907      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
908//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
909      typename Graph::OutEdgeIt e;
910    public:
911      OutEdgeIt() { }
912      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
913      OutEdgeIt(const Invalid& i) : e(i) { }
914      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
915                const Node& _n) :
916        e((*_G.first_out_edges)[_n]) { }
917      operator Edge() const { return Edge(typename Graph::Edge(e)); }
918    };
919    class InEdgeIt {
920      friend class GraphWrapper<Graph>;
921      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
922//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
923      typename Graph::InEdgeIt e;
924    public:
925      InEdgeIt() { }
926      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
927      InEdgeIt(const Invalid& i) : e(i) { }
928      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
929               const Node& _n) :
930        e(*(_G.graph), typename Graph::Node(_n)) { }
931      operator Edge() const { return Edge(typename Graph::Edge(e)); }
932    };
933    //typedef typename Graph::SymEdgeIt SymEdgeIt;
934    class EdgeIt {
935      friend class GraphWrapper<Graph>;
936      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
937//      typedef typename Graph::EdgeIt GraphEdgeIt;
938      typename Graph::EdgeIt e;
939    public:
940      EdgeIt() { }
941      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
942      EdgeIt(const Invalid& i) : e(i) { }
943      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
944        e(*(_G.graph)) { }
945      operator Edge() const { return Edge(typename Graph::Edge(e)); }
946    };
947
948    using GraphWrapper<Graph>::first;
949//     NodeIt& first(NodeIt& i) const {
950//       i=NodeIt(*this); return i;
951//     }
952    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
953      i=OutEdgeIt(*this, p); return i;
954    }
955    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
956      i=InEdgeIt(*this, p); return i;
957    }
958    EdgeIt& first(EdgeIt& i) const {
959      i=EdgeIt(*this); return i;
960    }
961
962    using GraphWrapper<Graph>::next;
963//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
964    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
965    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
966    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
967   
968    Node aNode(const OutEdgeIt& e) const {
969      return Node(this->graph->aNode(e.e)); }
970    Node aNode(const InEdgeIt& e) const {
971      return Node(this->graph->aNode(e.e)); }
972    Node bNode(const OutEdgeIt& e) const {
973      return Node(this->graph->bNode(e.e)); }
974    Node bNode(const InEdgeIt& e) const {
975      return Node(this->graph->bNode(e.e)); }
976
977    void erase(const OutEdgeIt& e) const {
978      OutEdgeIt f=e;
979      this->next(f);
980      first_out_edges->set(this->tail(e), f.e);
981    }
982  };
983
984  ///@}
985
986} //namespace hugo
987
988
989#endif //HUGO_GRAPH_WRAPPER_H
990
Note: See TracBrowser for help on using the repository browser.