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
RevLine 
[174]1// -*- c++ -*-
[259]2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
[76]4
[491]5///\ingroup gwrappers
[457]6///\file
7///\brief Several graph wrappers.
8///
9///This file contains several useful graph wrapper functions.
10///
11///\author Marton Makai
12
[174]13#include <invalid.h>
[499]14//#include <iter_map.h>
[174]15
[105]16namespace hugo {
[76]17
[438]18  // Graph wrappers
19
[406]20  /// \addtogroup gwrappers
[344]21  /// A main parts of HUGOlib are the different graph structures,
[335]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
[344]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
[335]30  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
[344]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.
[335]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
[344]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.
[335]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
[344]49  /// graph is of particular importance. Combining a wrapper implementing
50  /// this, shortest path algorithms and minimum mean cycle algorithms,
[335]51  /// a range of weighted and cardinality optimization algorithms can be
52  /// obtained. For lack of space, for other examples,
[344]53  /// the interested user is referred to the detailed documentation of graph
[335]54  /// wrappers.
[344]55  /// The behavior of graph wrappers can be very different. Some of them keep
[335]56  /// capabilities of the original graph while in other cases this would be
[344]57  /// meaningless. This means that the concepts that they are a model of depend
[335]58  /// on the graph wrapper, and the wrapped graph(s).
[344]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
[335]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
[344]66  /// <tt> RevGraphWrapper(Graph& _g)</tt>.
[335]67  /// This means that in a situation,
[344]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>.
[335]70  /// \code
71  /// int algorithm1(const ListGraph& g) {
72  ///   RevGraphWrapper<const ListGraph> rgw(g);
73  ///   return algorithm2(rgw);
74  /// }
75  /// \endcode
[438]76
77  /// \addtogroup gwrappers
78  /// @{
79
80  ///Base type for the Graph Wrappers
81
82  ///This is the base type for the Graph Wrappers.
[457]83  ///\todo Some more docs...
84  ///
85  ///\author Marton Makai
86 
[303]87  template<typename Graph>
88  class GraphWrapper {
[212]89  protected:
[303]90    Graph* graph;
[497]91    GraphWrapper() : graph(0) { }
92    void setGraph(Graph& _graph) { graph=&_graph; }
93
[212]94  public:
[311]95    typedef Graph BaseGraph;
[303]96    typedef Graph ParentGraph;
[212]97
[303]98    GraphWrapper(Graph& _graph) : graph(&_graph) { }
99//     Graph& getGraph() const { return *graph; }
100 
[317]101//    typedef typename Graph::Node Node;
102    class Node : public Graph::Node {
103      friend class GraphWrapper<Graph>;
[265]104    public:
[317]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:
[265]113      NodeIt() { }
[317]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)); }
[265]118    };
[317]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;
[265]130    public:
131      OutEdgeIt() { }
[317]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)); }
[265]137    };
[317]138    class InEdgeIt {
139      friend class GraphWrapper<Graph>;
140      typename Graph::InEdgeIt e;
[265]141    public:
142      InEdgeIt() { }
[317]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)); }
[265]148    };
[303]149    //typedef typename Graph::SymEdgeIt SymEdgeIt;
[317]150    class EdgeIt {
151      friend class GraphWrapper<Graph>;
152      typename Graph::EdgeIt e;
[265]153    public:
154      EdgeIt() { }
[317]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)); }
[265]159    };
[303]160   
161    NodeIt& first(NodeIt& i) const {
[317]162      i=NodeIt(*this); return i;
[265]163    }
[303]164    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
[317]165      i=OutEdgeIt(*this, p); return i;
[303]166    }
167    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
[317]168      i=InEdgeIt(*this, p); return i;
[303]169    }
[311]170    EdgeIt& first(EdgeIt& i) const {
[317]171      i=EdgeIt(*this); return i;
[311]172    }
[338]173
[317]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; }   
[212]178
[379]179    Node tail(const Edge& e) const {
180      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
[317]181    Node head(const Edge& e) const {
182      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
[212]183
[317]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)); }
[212]188
[303]189    int nodeNum() const { return graph->nodeNum(); }
190    int edgeNum() const { return graph->edgeNum(); }
[212]191 
[317]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)); }
[212]196 
[317]197    Node addNode() const { return Node(graph->addNode()); }
[212]198    Edge addEdge(const Node& tail, const Node& head) const {
[317]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); }
[212]203 
[303]204    void clear() const { graph->clear(); }
[212]205   
[389]206    template<typename T> class NodeMap : public Graph::template NodeMap<T> {
207      typedef typename Graph::template NodeMap<T> Parent;
[212]208    public:
[389]209      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
210      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
[212]211    };
212
[389]213    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
214      typedef typename Graph::template EdgeMap<T> Parent;
[212]215    public:
[389]216      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
217      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
[212]218    };
219  };
220
[338]221  /// A graph wrapper which reverses the orientation of the edges.
[303]222
[338]223  /// A graph wrapper which reverses the orientation of the edges.
[457]224  ///
225  ///\author Marton Makai
[303]226  template<typename Graph>
227  class RevGraphWrapper : public GraphWrapper<Graph> {
[497]228  protected:
229    RevGraphWrapper() : GraphWrapper<Graph>(0) { }
[230]230  public:
[338]231    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
232
[303]233    typedef typename GraphWrapper<Graph>::Node Node;
234    typedef typename GraphWrapper<Graph>::Edge Edge;
235    //If Graph::OutEdgeIt is not defined
[279]236    //and we do not want to use RevGraphWrapper::InEdgeIt,
[338]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;
[237]241
[338]242    class OutEdgeIt {
243      friend class GraphWrapper<Graph>;
244      friend class RevGraphWrapper<Graph>;
[379]245      typename Graph::InEdgeIt e;
[338]246    public:
247      OutEdgeIt() { }
[379]248      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
[338]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>;
[379]257      typename Graph::OutEdgeIt e;
[338]258    public:
259      InEdgeIt() { }
[379]260      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
[338]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    };
[238]266
[338]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;
[389]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; }
[338]278
[389]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)); }
[379]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
[76]293  };
294
[335]295  /// Wrapper for hiding nodes and edges from a graph.
296 
297  /// This wrapper shows a graph with filtered node-set and
[363]298  /// edge-set. The quick brown fox iterator jumps over
[335]299  /// the lazy dog nodes or edges if the values for them are false
300  /// in the bool maps.
[457]301  ///
302  ///\author Marton Makai
[311]303  template<typename Graph, typename NodeFilterMap,
304           typename EdgeFilterMap>
[303]305  class SubGraphWrapper : public GraphWrapper<Graph> {
[263]306  protected:
[311]307    NodeFilterMap* node_filter_map;
308    EdgeFilterMap* edge_filter_map;
[497]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   
[263]319  public:
[338]320
[311]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) { } 
[263]325
[317]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:
[311]332      NodeIt() { }
[317]333      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
334      NodeIt(const Invalid& i) : n(i) { }
[311]335      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
[317]336        n(*(_G.graph)) {
337        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
338          _G.graph->next(n);
[311]339      }
[317]340      operator Node() const { return Node(typename Graph::Node(n)); }
[311]341    };
[317]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;
[311]347    public:
348      OutEdgeIt() { }
[317]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);
[311]356      }
[317]357      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]358    };
[317]359    class InEdgeIt {
360      friend class GraphWrapper<Graph>;
361      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
362      typename Graph::InEdgeIt e;
[311]363    public:
364      InEdgeIt() { }
[317]365      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
366      InEdgeIt(const Invalid& i) : e(i) { }
[311]367      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
[317]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);
[311]372      }
[317]373      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]374    };
[317]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;
[311]380    public:
381      EdgeIt() { }
[317]382      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
383      EdgeIt(const Invalid& i) : e(i) { }
[311]384      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
[317]385        e(*(_G.graph)) {
386        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
387          _G.graph->next(e);
[311]388      }
[317]389      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]390    };
[317]391
392    NodeIt& first(NodeIt& i) const {
393      i=NodeIt(*this); return i;
[263]394    }
[317]395    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
396      i=OutEdgeIt(*this, p); return i;
[311]397    }
[317]398    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
399      i=InEdgeIt(*this, p); return i;
[311]400    }
[317]401    EdgeIt& first(EdgeIt& i) const {
402      i=EdgeIt(*this); return i;
[263]403    }
404   
[311]405    NodeIt& next(NodeIt& i) const {
[389]406      this->graph->next(i.n);
407      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
408        this->graph->next(i.n); }
[311]409      return i;
410    }
411    OutEdgeIt& next(OutEdgeIt& i) const {
[389]412      this->graph->next(i.e);
413      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
414        this->graph->next(i.e); }
[311]415      return i;
416    }
417    InEdgeIt& next(InEdgeIt& i) const {
[389]418      this->graph->next(i.e);
419      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
420        this->graph->next(i.e); }
[311]421      return i;
422    }
423    EdgeIt& next(EdgeIt& i) const {
[389]424      this->graph->next(i.e);
425      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
426        this->graph->next(i.e); }
[311]427      return i;
428    }
429
[389]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)); }
[323]438
[357]439    ///\todo
440    ///Some doki, please.
[323]441    void hide(const Node& n) const { node_filter_map->set(n, false); }
[357]442    ///\todo
443    ///Some doki, please.
[323]444    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
445
[357]446    ///\todo
447    ///Some doki, please.
[323]448    void unHide(const Node& n) const { node_filter_map->set(n, true); }
[357]449    ///\todo
450    ///Some doki, please.
[323]451    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
452
[357]453    ///\todo
454    ///Some doki, please.
[323]455    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
[357]456    ///\todo
457    ///Some doki, please.
[323]458    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
[263]459  };
[155]460
[356]461  /// A wrapper for forgetting the orientation of a graph.
[317]462
[356]463  /// A wrapper for getting an undirected graph by forgetting
464  /// the orientation of a directed one.
[303]465  template<typename Graph>
466  class UndirGraphWrapper : public GraphWrapper<Graph> {
[497]467  protected:
468    UndirGraphWrapper() : GraphWrapper<Graph>(0) { }
469   
[303]470  public:
471    typedef typename GraphWrapper<Graph>::Node Node;
472    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
[317]473    typedef typename GraphWrapper<Graph>::Edge Edge;
474    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
[236]475
[303]476    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
[158]477
[317]478    class OutEdgeIt {
[303]479      friend class UndirGraphWrapper<Graph>;
[158]480      bool out_or_in; //true iff out
[317]481      typename Graph::OutEdgeIt out;
482      typename Graph::InEdgeIt in;
[158]483    public:
[317]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);        }
[174]489      }
[317]490      operator Edge() const {
491        if (out_or_in) return Edge(out); else return Edge(in);
[158]492      }
493    };
494
[317]495//FIXME InEdgeIt
[238]496    typedef OutEdgeIt InEdgeIt;
497
[338]498    using GraphWrapper<Graph>::first;
499//     NodeIt& first(NodeIt& i) const {
500//       i=NodeIt(*this); return i;
501//     }
[317]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//     }
[338]509//     EdgeIt& first(EdgeIt& i) const {
510//       i=EdgeIt(*this); return i;
511//     }
[238]512
[338]513    using GraphWrapper<Graph>::next;
514//     NodeIt& next(NodeIt& n) const {
515//       GraphWrapper<Graph>::next(n);
516//       return n;
517//     }
[158]518    OutEdgeIt& next(OutEdgeIt& e) const {
519      if (e.out_or_in) {
[389]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); }
[158]524      } else {
[389]525        this->graph->next(e.in);
[158]526      }
527      return e;
528    }
[317]529    //FIXME InEdgeIt
[338]530//     EdgeIt& next(EdgeIt& e) const {
531//       GraphWrapper<Graph>::next(n);
532// //      graph->next(e.e);
533//       return e;
534//     }
[238]535
536    Node aNode(const OutEdgeIt& e) const {
[389]537      if (e.out_or_in) return this->graph->tail(e); else
538        return this->graph->head(e); }
[238]539    Node bNode(const OutEdgeIt& e) const {
[389]540      if (e.out_or_in) return this->graph->head(e); else
541        return this->graph->tail(e); }
[338]542  };
[158]543 
[338]544  /// A wrapper for composing the residual graph for directed flow and circulation problems.
[238]545
[338]546  /// A wrapper for composing the residual graph for directed flow and circulation problems.
[330]547  template<typename Graph, typename Number,
548           typename CapacityMap, typename FlowMap>
[311]549  class ResGraphWrapper : public GraphWrapper<Graph> {
[199]550  protected:
[330]551    const CapacityMap* capacity;
[155]552    FlowMap* flow;
[497]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
[155]563  public:
[168]564
[330]565    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
566                    FlowMap& _flow) :
567      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
[168]568
[174]569    class Edge;
[155]570    class OutEdgeIt;
[174]571    friend class Edge;
[155]572    friend class OutEdgeIt;
[76]573
[311]574    typedef typename GraphWrapper<Graph>::Node Node;
575    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
[317]576    class Edge : public Graph::Edge {
[330]577      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[155]578    protected:
[317]579      bool forward; //true, iff forward
580//      typename Graph::Edge e;
[155]581    public:
[317]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
[174]587      friend bool operator==(const Edge& u, const Edge& v) {
[317]588        return (v.forward==u.forward &&
589                static_cast<typename Graph::Edge>(u)==
590                static_cast<typename Graph::Edge>(v));
[174]591      }
592      friend bool operator!=(const Edge& u, const Edge& v) {
[317]593        return (v.forward!=u.forward ||
594                static_cast<typename Graph::Edge>(u)!=
595                static_cast<typename Graph::Edge>(v));
[174]596      }
[155]597    };
[338]598
[317]599    class OutEdgeIt {
[330]600      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[317]601    protected:
602      typename Graph::OutEdgeIt out;
603      typename Graph::InEdgeIt in;
604      bool forward;
[155]605    public:
606      OutEdgeIt() { }
[168]607      //FIXME
[317]608//      OutEdgeIt(const Edge& e) : Edge(e) { }
609      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
610//the unique invalid iterator
[330]611      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
[317]612        forward=true;
[303]613        resG.graph->first(out, v);
[317]614        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
[303]615        if (!resG.graph->valid(out)) {
[317]616          forward=false;
[303]617          resG.graph->first(in, v);
[317]618          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
[155]619        }
620      }
[317]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    };
[263]632
[317]633    class InEdgeIt {
[330]634      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[317]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
[330]645      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
[317]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 {
[330]668      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[317]669    protected:
670      typename Graph::EdgeIt e;
671      bool forward;
[155]672    public:
[174]673      EdgeIt() { }
[317]674      EdgeIt(const Invalid& i) : e(i), forward(false) { }
[330]675      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
[317]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);
[155]683        }
684      }
[317]685      operator Edge() const {
686        return Edge(e, this->forward);
687      }
688    };
[155]689
[338]690    using GraphWrapper<Graph>::first;
691//     NodeIt& first(NodeIt& i) const {
692//       i=NodeIt(*this); return i;
693//     }
[311]694    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
[317]695      i=OutEdgeIt(*this, p); return i;
[311]696    }
[317]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;
[155]703    }
[338]704 
705    using GraphWrapper<Graph>::next;
706//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
[155]707    OutEdgeIt& next(OutEdgeIt& e) const {
[317]708      if (e.forward) {
[389]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)) {
[317]714          e.forward=false;
[389]715          this->graph->first(e.in, v);
716          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
717            this->graph->next(e.in); }
[155]718        }
719      } else {
[389]720        this->graph->next(e.in);
721        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
722          this->graph->next(e.in); }
[155]723      }
724      return e;
725    }
[317]726//     FIXME Not tested
727    InEdgeIt& next(InEdgeIt& e) const {
728      if (e.forward) {
[389]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)) {
[317]734          e.forward=false;
[389]735          this->graph->first(e.out, v);
736          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
737            this->graph->next(e.out); }
[317]738        }
739      } else {
[389]740        this->graph->next(e.out);
741        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
742          this->graph->next(e.out); }
[317]743      }
744      return e;
745    }
746    EdgeIt& next(EdgeIt& e) const {
747      if (e.forward) {
[389]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)) {
[317]752          e.forward=false;
[389]753          this->graph->first(e.e);
754          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
755            this->graph->next(e.e); }
[155]756        }
[317]757      } else {
[389]758        this->graph->next(e.e);
759        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
760          this->graph->next(e.e); }
[155]761      }
[317]762      return e;
763    }
[76]764
[174]765    Node tail(Edge e) const {
[389]766      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
[174]767    Node head(Edge e) const {
[389]768      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
[76]769
[174]770    Node aNode(OutEdgeIt e) const {
[389]771      return ((e.forward) ? this->graph->aNode(e.out) :
772              this->graph->aNode(e.in)); }
[174]773    Node bNode(OutEdgeIt e) const {
[389]774      return ((e.forward) ? this->graph->bNode(e.out) :
775              this->graph->bNode(e.in)); }
[76]776
[376]777    Node aNode(InEdgeIt e) const {
[389]778      return ((e.forward) ? this->graph->aNode(e.in) :
779              this->graph->aNode(e.out)); }
[376]780    Node bNode(InEdgeIt e) const {
[389]781      return ((e.forward) ? this->graph->bNode(e.in) :
782              this->graph->bNode(e.out)); }
[376]783
[338]784//    int nodeNum() const { return graph->nodeNum(); }
[263]785    //FIXME
[338]786    void edgeNum() const { }
[303]787    //int edgeNum() const { return graph->edgeNum(); }
[263]788
789
[317]790//    int id(Node v) const { return graph->id(v); }
[155]791
[317]792    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
[174]793    bool valid(Edge e) const {
[389]794      return this->graph->valid(e);
[317]795        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
796    }
[155]797
[174]798    void augment(const Edge& e, Number a) const {
[317]799      if (e.forward) 
[303]800//      flow->set(e.out, flow->get(e.out)+a);
[317]801        flow->set(e, (*flow)[e]+a);
[168]802      else 
[303]803//      flow->set(e.in, flow->get(e.in)-a);
[317]804        flow->set(e, (*flow)[e]-a);
[168]805    }
806
[269]807    Number resCap(const Edge& e) const {
[317]808      if (e.forward)
[303]809//      return (capacity->get(e.out)-flow->get(e.out));
[317]810        return ((*capacity)[e]-(*flow)[e]);
[168]811      else
[303]812//      return (flow->get(e.in));
[317]813        return ((*flow)[e]);
[168]814    }
815
[317]816//     Number resCap(typename Graph::OutEdgeIt out) const {
817// //      return (capacity->get(out)-flow->get(out));
818//       return ((*capacity)[out]-(*flow)[out]);
819//     }
[168]820   
[317]821//     Number resCap(typename Graph::InEdgeIt in) const {
822// //      return (flow->get(in));
823//       return ((*flow)[in]);
824//     }
[168]825
[155]826    template <typename T>
827    class EdgeMap {
[389]828      typename Graph::template EdgeMap<T> forward_map, backward_map;
[155]829    public:
[330]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) { }
[174]832      void set(Edge e, T a) {
[317]833        if (e.forward)
[155]834          forward_map.set(e.out, a);
835        else
836          backward_map.set(e.in, a);
837      }
[303]838      T operator[](Edge e) const {
[317]839        if (e.forward)
[303]840          return forward_map[e.out];
[155]841        else
[303]842          return backward_map[e.in];
[155]843      }
[303]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//       }
[155]850    };
[168]851  };
852
[338]853  /// ErasingFirstGraphWrapper for blocking flows.
[317]854
[338]855  /// ErasingFirstGraphWrapper for blocking flows.
[457]856  ///
857  ///\author Marton Makai
[303]858  template<typename Graph, typename FirstOutEdgesMap>
859  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
[269]860  protected:
861    FirstOutEdgesMap* first_out_edges;
862  public:
[303]863    ErasingFirstGraphWrapper(Graph& _graph,
864                             FirstOutEdgesMap& _first_out_edges) :
865      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
[269]866
[317]867    typedef typename GraphWrapper<Graph>::Node Node;
[338]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//     };
[317]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;
[311]886    public:
887      OutEdgeIt() { }
[317]888      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
889      OutEdgeIt(const Invalid& i) : e(i) { }
[311]890      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
[317]891                const Node& _n) :
892        e((*_G.first_out_edges)[_n]) { }
893      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]894    };
[317]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;
[311]900    public:
901      InEdgeIt() { }
[317]902      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
903      InEdgeIt(const Invalid& i) : e(i) { }
[311]904      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
[317]905               const Node& _n) :
906        e(*(_G.graph), typename Graph::Node(_n)) { }
907      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]908    };
909    //typedef typename Graph::SymEdgeIt SymEdgeIt;
[317]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;
[311]915    public:
916      EdgeIt() { }
[317]917      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
918      EdgeIt(const Invalid& i) : e(i) { }
[311]919      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
[317]920        e(*(_G.graph)) { }
921      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]922    };
923
[338]924    using GraphWrapper<Graph>::first;
925//     NodeIt& first(NodeIt& i) const {
926//       i=NodeIt(*this); return i;
927//     }
[317]928    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
929      i=OutEdgeIt(*this, p); return i;
[269]930    }
[317]931    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
932      i=InEdgeIt(*this, p); return i;
[311]933    }
[317]934    EdgeIt& first(EdgeIt& i) const {
935      i=EdgeIt(*this); return i;
[311]936    }
937
[338]938    using GraphWrapper<Graph>::next;
939//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
[389]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; }   
[317]943   
[389]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)); }
[311]952
[269]953    void erase(const OutEdgeIt& e) const {
954      OutEdgeIt f=e;
955      this->next(f);
[317]956      first_out_edges->set(this->tail(e), f.e);
[269]957    }
958  };
959
[406]960  ///@}
[341]961
[105]962} //namespace hugo
[76]963
[406]964
[259]965#endif //HUGO_GRAPH_WRAPPER_H
[76]966
Note: See TracBrowser for help on using the repository browser.