COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 415:679e64913c5e

Last change on this file since 415:679e64913c5e was 409:7ab7f083760a, checked in by marci, 20 years ago

stGraphWrapper is almost working

File size: 50.4 KB
RevLine 
[174]1// -*- c++ -*-
[259]2#ifndef HUGO_GRAPH_WRAPPER_H
3#define HUGO_GRAPH_WRAPPER_H
[76]4
[174]5#include <invalid.h>
[368]6#include <iter_map.h>
[174]7
[105]8namespace hugo {
[76]9
[406]10  /// \addtogroup gwrappers
11  /// @{
12
[335]13  /// Graph wrappers
14
[344]15  /// A main parts of HUGOlib are the different graph structures,
[335]16  /// generic graph algorithms, graph concepts which couple these, and
17  /// graph wrappers. While the previous ones are more or less clear, the
18  /// latter notion needs further explanation.
19  /// Graph wrappers are graph classes which serve for considering graph
[344]20  /// structures in different ways. A short example makes the notion much
21  /// clearer.
22  /// Suppose that we have an instance \c g of a directed graph
23  /// type say \c ListGraph and an algorithm
[335]24  /// \code template<typename Graph> int algorithm(const Graph&); \endcode
[344]25  /// is needed to run on the reversely oriented graph.
26  /// It may be expensive (in time or in memory usage) to copy
27  /// \c g with the reverse orientation.
[335]28  /// Thus, a wrapper class
29  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
30  /// The code looks as follows
31  /// \code
32  /// ListGraph g;
33  /// RevGraphWrapper<ListGraph> rgw(g);
34  /// int result=algorithm(rgw);
35  /// \endcode
[344]36  /// After running the algorithm, the original graph \c g
37  /// remains untouched. Thus the graph wrapper used above is to consider the
38  /// original graph with reverse orientation.
[335]39  /// This techniques gives rise to an elegant code, and
40  /// based on stable graph wrappers, complex algorithms can be
41  /// implemented easily.
42  /// In flow, circulation and bipartite matching problems, the residual
[344]43  /// graph is of particular importance. Combining a wrapper implementing
44  /// this, shortest path algorithms and minimum mean cycle algorithms,
[335]45  /// a range of weighted and cardinality optimization algorithms can be
46  /// obtained. For lack of space, for other examples,
[344]47  /// the interested user is referred to the detailed documentation of graph
[335]48  /// wrappers.
[344]49  /// The behavior of graph wrappers can be very different. Some of them keep
[335]50  /// capabilities of the original graph while in other cases this would be
[344]51  /// meaningless. This means that the concepts that they are a model of depend
[335]52  /// on the graph wrapper, and the wrapped graph(s).
[344]53  /// If an edge of \c rgw is deleted, this is carried out by
54  /// deleting the corresponding edge of \c g. But for a residual
[335]55  /// graph, this operation has no sense.
56  /// Let we stand one more example here to simplify your work.
57  /// wrapper class
58  /// \code template<typename Graph> class RevGraphWrapper; \endcode
59  /// has constructor
[344]60  /// <tt> RevGraphWrapper(Graph& _g)</tt>.
[335]61  /// This means that in a situation,
[344]62  /// when a <tt> const ListGraph& </tt> reference to a graph is given,
63  /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
[335]64  /// \code
65  /// int algorithm1(const ListGraph& g) {
66  ///   RevGraphWrapper<const ListGraph> rgw(g);
67  ///   return algorithm2(rgw);
68  /// }
69  /// \endcode
[303]70  template<typename Graph>
71  class GraphWrapper {
[212]72  protected:
[303]73    Graph* graph;
[212]74 
75  public:
[311]76    typedef Graph BaseGraph;
[303]77    typedef Graph ParentGraph;
[212]78
[303]79//     GraphWrapper() : graph(0) { }
80    GraphWrapper(Graph& _graph) : graph(&_graph) { }
81//     void setGraph(Graph& _graph) { graph=&_graph; }
82//     Graph& getGraph() const { return *graph; }
83 
[317]84//    typedef typename Graph::Node Node;
85    class Node : public Graph::Node {
86      friend class GraphWrapper<Graph>;
[265]87    public:
[317]88      Node() { }
89      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
90      Node(const Invalid& i) : Graph::Node(i) { }
91    };
92    class NodeIt {
93      friend class GraphWrapper<Graph>;
94      typename Graph::NodeIt n;
95     public:
[265]96      NodeIt() { }
[317]97      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
98      NodeIt(const Invalid& i) : n(i) { }
99      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
100      operator Node() const { return Node(typename Graph::Node(n)); }
[265]101    };
[317]102//    typedef typename Graph::Edge Edge;
103    class Edge : public Graph::Edge {
104      friend class GraphWrapper<Graph>;
105    public:
106      Edge() { }
107      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
108      Edge(const Invalid& i) : Graph::Edge(i) { }
109    };
110    class OutEdgeIt {
111      friend class GraphWrapper<Graph>;
112      typename Graph::OutEdgeIt e;
[265]113    public:
114      OutEdgeIt() { }
[317]115      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
116      OutEdgeIt(const Invalid& i) : e(i) { }
117      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
118        e(*(_G.graph), typename Graph::Node(_n)) { }
119      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[265]120    };
[317]121    class InEdgeIt {
122      friend class GraphWrapper<Graph>;
123      typename Graph::InEdgeIt e;
[265]124    public:
125      InEdgeIt() { }
[317]126      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
127      InEdgeIt(const Invalid& i) : e(i) { }
128      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
129        e(*(_G.graph), typename Graph::Node(_n)) { }
130      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[265]131    };
[303]132    //typedef typename Graph::SymEdgeIt SymEdgeIt;
[317]133    class EdgeIt {
134      friend class GraphWrapper<Graph>;
135      typename Graph::EdgeIt e;
[265]136    public:
137      EdgeIt() { }
[317]138      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
139      EdgeIt(const Invalid& i) : e(i) { }
140      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
141      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[265]142    };
[303]143   
144    NodeIt& first(NodeIt& i) const {
[317]145      i=NodeIt(*this); return i;
[265]146    }
[303]147    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
[317]148      i=OutEdgeIt(*this, p); return i;
[303]149    }
150    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
[317]151      i=InEdgeIt(*this, p); return i;
[303]152    }
[311]153    EdgeIt& first(EdgeIt& i) const {
[317]154      i=EdgeIt(*this); return i;
[311]155    }
[338]156
[317]157    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
158    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
159    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
160    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
[212]161
[379]162    Node tail(const Edge& e) const {
163      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
[317]164    Node head(const Edge& e) const {
165      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
[212]166
[317]167    bool valid(const Node& n) const {
168      return graph->valid(static_cast<typename Graph::Node>(n)); }
169    bool valid(const Edge& e) const {
170      return graph->valid(static_cast<typename Graph::Edge>(e)); }
[212]171
[303]172    int nodeNum() const { return graph->nodeNum(); }
173    int edgeNum() const { return graph->edgeNum(); }
[212]174 
[317]175    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
176    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
177    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
178    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
[212]179 
[317]180    Node addNode() const { return Node(graph->addNode()); }
[212]181    Edge addEdge(const Node& tail, const Node& head) const {
[317]182      return Edge(graph->addEdge(tail, head)); }
183
184    void erase(const Node& i) const { graph->erase(i); }
185    void erase(const Edge& i) const { graph->erase(i); }
[212]186 
[303]187    void clear() const { graph->clear(); }
[212]188   
[389]189    template<typename T> class NodeMap : public Graph::template NodeMap<T> {
190      typedef typename Graph::template NodeMap<T> Parent;
[212]191    public:
[389]192      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
193      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
[212]194    };
195
[389]196    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
197      typedef typename Graph::template EdgeMap<T> Parent;
[212]198    public:
[389]199      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
200      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
[212]201    };
202  };
203
[338]204  /// A graph wrapper which reverses the orientation of the edges.
[303]205
[338]206  /// A graph wrapper which reverses the orientation of the edges.
[303]207  template<typename Graph>
208  class RevGraphWrapper : public GraphWrapper<Graph> {
[230]209  public:
[338]210
211    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
212
[303]213    typedef typename GraphWrapper<Graph>::Node Node;
214    typedef typename GraphWrapper<Graph>::Edge Edge;
215    //If Graph::OutEdgeIt is not defined
[279]216    //and we do not want to use RevGraphWrapper::InEdgeIt,
[338]217    //the typdef techinque does not work.
218    //Unfortunately all the typedefs are instantiated in templates.
219    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
220    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
[237]221
[338]222    class OutEdgeIt {
223      friend class GraphWrapper<Graph>;
224      friend class RevGraphWrapper<Graph>;
[379]225      typename Graph::InEdgeIt e;
[338]226    public:
227      OutEdgeIt() { }
[379]228      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
[338]229      OutEdgeIt(const Invalid& i) : e(i) { }
230      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
231        e(*(_G.graph), typename Graph::Node(_n)) { }
232      operator Edge() const { return Edge(typename Graph::Edge(e)); }
233    };
234    class InEdgeIt {
235      friend class GraphWrapper<Graph>;
236      friend class RevGraphWrapper<Graph>;
[379]237      typename Graph::OutEdgeIt e;
[338]238    public:
239      InEdgeIt() { }
[379]240      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
[338]241      InEdgeIt(const Invalid& i) : e(i) { }
242      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
243        e(*(_G.graph), typename Graph::Node(_n)) { }
244      operator Edge() const { return Edge(typename Graph::Edge(e)); }
245    };
[238]246
[338]247    using GraphWrapper<Graph>::first;
248    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
249      i=OutEdgeIt(*this, p); return i;
250    }
251    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
252      i=InEdgeIt(*this, p); return i;
253    }
254
255    using GraphWrapper<Graph>::next;
[389]256    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
257    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
[338]258
[389]259    Node aNode(const OutEdgeIt& e) const {
260      return Node(this->graph->aNode(e.e)); }
261    Node aNode(const InEdgeIt& e) const {
262      return Node(this->graph->aNode(e.e)); }
263    Node bNode(const OutEdgeIt& e) const {
264      return Node(this->graph->bNode(e.e)); }
265    Node bNode(const InEdgeIt& e) const {
266      return Node(this->graph->bNode(e.e)); }
[379]267
268    Node tail(const Edge& e) const {
269      return GraphWrapper<Graph>::head(e); }
270    Node head(const Edge& e) const {
271      return GraphWrapper<Graph>::tail(e); }
272
[76]273  };
274
[335]275  /// Wrapper for hiding nodes and edges from a graph.
276 
277  /// This wrapper shows a graph with filtered node-set and
[363]278  /// edge-set. The quick brown fox iterator jumps over
[335]279  /// the lazy dog nodes or edges if the values for them are false
280  /// in the bool maps.
[311]281  template<typename Graph, typename NodeFilterMap,
282           typename EdgeFilterMap>
[303]283  class SubGraphWrapper : public GraphWrapper<Graph> {
[263]284  protected:
[311]285    NodeFilterMap* node_filter_map;
286    EdgeFilterMap* edge_filter_map;
[263]287  public:
[338]288
[311]289    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
290                    EdgeFilterMap& _edge_filter_map) :
291      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
292      edge_filter_map(&_edge_filter_map) { } 
[263]293
[317]294    typedef typename GraphWrapper<Graph>::Node Node;
295    class NodeIt {
296      friend class GraphWrapper<Graph>;
297      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
298      typename Graph::NodeIt n;
299     public:
[311]300      NodeIt() { }
[317]301      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
302      NodeIt(const Invalid& i) : n(i) { }
[311]303      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
[317]304        n(*(_G.graph)) {
305        while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
306          _G.graph->next(n);
[311]307      }
[317]308      operator Node() const { return Node(typename Graph::Node(n)); }
[311]309    };
[317]310    typedef typename GraphWrapper<Graph>::Edge Edge;
311    class OutEdgeIt {
312      friend class GraphWrapper<Graph>;
313      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
314      typename Graph::OutEdgeIt e;
[311]315    public:
316      OutEdgeIt() { }
[317]317      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
318      OutEdgeIt(const Invalid& i) : e(i) { }
319      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
320                const Node& _n) :
321        e(*(_G.graph), typename Graph::Node(_n)) {
322        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
323          _G.graph->next(e);
[311]324      }
[317]325      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]326    };
[317]327    class InEdgeIt {
328      friend class GraphWrapper<Graph>;
329      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
330      typename Graph::InEdgeIt e;
[311]331    public:
332      InEdgeIt() { }
[317]333      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
334      InEdgeIt(const Invalid& i) : e(i) { }
[311]335      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
[317]336               const Node& _n) :
337        e(*(_G.graph), typename Graph::Node(_n)) {
338        while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
339          _G.graph->next(e);
[311]340      }
[317]341      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]342    };
[317]343    //typedef typename Graph::SymEdgeIt SymEdgeIt;
344    class EdgeIt {
345      friend class GraphWrapper<Graph>;
346      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
347      typename Graph::EdgeIt e;
[311]348    public:
349      EdgeIt() { }
[317]350      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
351      EdgeIt(const Invalid& i) : e(i) { }
[311]352      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
[317]353        e(*(_G.graph)) {
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
360    NodeIt& first(NodeIt& i) const {
361      i=NodeIt(*this); return i;
[263]362    }
[317]363    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
364      i=OutEdgeIt(*this, p); return i;
[311]365    }
[317]366    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
367      i=InEdgeIt(*this, p); return i;
[311]368    }
[317]369    EdgeIt& first(EdgeIt& i) const {
370      i=EdgeIt(*this); return i;
[263]371    }
372   
[311]373    NodeIt& next(NodeIt& i) const {
[389]374      this->graph->next(i.n);
375      while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
376        this->graph->next(i.n); }
[311]377      return i;
378    }
379    OutEdgeIt& next(OutEdgeIt& i) const {
[389]380      this->graph->next(i.e);
381      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
382        this->graph->next(i.e); }
[311]383      return i;
384    }
385    InEdgeIt& next(InEdgeIt& i) const {
[389]386      this->graph->next(i.e);
387      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
388        this->graph->next(i.e); }
[311]389      return i;
390    }
391    EdgeIt& next(EdgeIt& i) const {
[389]392      this->graph->next(i.e);
393      while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
394        this->graph->next(i.e); }
[311]395      return i;
396    }
397
[389]398    Node aNode(const OutEdgeIt& e) const {
399      return Node(this->graph->aNode(e.e)); }
400    Node aNode(const InEdgeIt& e) const {
401      return Node(this->graph->aNode(e.e)); }
402    Node bNode(const OutEdgeIt& e) const {
403      return Node(this->graph->bNode(e.e)); }
404    Node bNode(const InEdgeIt& e) const {
405      return Node(this->graph->bNode(e.e)); }
[323]406
[357]407    ///\todo
408    ///Some doki, please.
[323]409    void hide(const Node& n) const { node_filter_map->set(n, false); }
[357]410    ///\todo
411    ///Some doki, please.
[323]412    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
413
[357]414    ///\todo
415    ///Some doki, please.
[323]416    void unHide(const Node& n) const { node_filter_map->set(n, true); }
[357]417    ///\todo
418    ///Some doki, please.
[323]419    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
420
[357]421    ///\todo
422    ///Some doki, please.
[323]423    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
[357]424    ///\todo
425    ///Some doki, please.
[323]426    bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
[263]427  };
[155]428
[356]429  /// A wrapper for forgetting the orientation of a graph.
[317]430
[356]431  /// A wrapper for getting an undirected graph by forgetting
432  /// the orientation of a directed one.
[303]433  template<typename Graph>
434  class UndirGraphWrapper : public GraphWrapper<Graph> {
435  public:
436    typedef typename GraphWrapper<Graph>::Node Node;
437    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
[317]438    typedef typename GraphWrapper<Graph>::Edge Edge;
439    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
[236]440
[303]441    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
[158]442
[317]443    class OutEdgeIt {
[303]444      friend class UndirGraphWrapper<Graph>;
[158]445      bool out_or_in; //true iff out
[317]446      typename Graph::OutEdgeIt out;
447      typename Graph::InEdgeIt in;
[158]448    public:
[317]449      OutEdgeIt() { }
450      OutEdgeIt(const Invalid& i) : Edge(i) { }
451      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
452        out_or_in=true; _G.graph->first(out, _n);
453        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
[174]454      }
[317]455      operator Edge() const {
456        if (out_or_in) return Edge(out); else return Edge(in);
[158]457      }
458    };
459
[317]460//FIXME InEdgeIt
[238]461    typedef OutEdgeIt InEdgeIt;
462
[338]463    using GraphWrapper<Graph>::first;
464//     NodeIt& first(NodeIt& i) const {
465//       i=NodeIt(*this); return i;
466//     }
[317]467    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
468      i=OutEdgeIt(*this, p); return i;
469    }
470//FIXME
471//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
472//       i=InEdgeIt(*this, p); return i;
473//     }
[338]474//     EdgeIt& first(EdgeIt& i) const {
475//       i=EdgeIt(*this); return i;
476//     }
[238]477
[338]478    using GraphWrapper<Graph>::next;
479//     NodeIt& next(NodeIt& n) const {
480//       GraphWrapper<Graph>::next(n);
481//       return n;
482//     }
[158]483    OutEdgeIt& next(OutEdgeIt& e) const {
484      if (e.out_or_in) {
[389]485        typename Graph::Node n=this->graph->tail(e.out);
486        this->graph->next(e.out);
487        if (!this->graph->valid(e.out)) {
488          e.out_or_in=false; this->graph->first(e.in, n); }
[158]489      } else {
[389]490        this->graph->next(e.in);
[158]491      }
492      return e;
493    }
[317]494    //FIXME InEdgeIt
[338]495//     EdgeIt& next(EdgeIt& e) const {
496//       GraphWrapper<Graph>::next(n);
497// //      graph->next(e.e);
498//       return e;
499//     }
[238]500
501    Node aNode(const OutEdgeIt& e) const {
[389]502      if (e.out_or_in) return this->graph->tail(e); else
503        return this->graph->head(e); }
[238]504    Node bNode(const OutEdgeIt& e) const {
[389]505      if (e.out_or_in) return this->graph->head(e); else
506        return this->graph->tail(e); }
[338]507  };
[158]508 
[338]509  /// A wrapper for composing the residual graph for directed flow and circulation problems.
[238]510
[338]511  /// A wrapper for composing the residual graph for directed flow and circulation problems.
[330]512  template<typename Graph, typename Number,
513           typename CapacityMap, typename FlowMap>
[311]514  class ResGraphWrapper : public GraphWrapper<Graph> {
[199]515  protected:
[330]516    const CapacityMap* capacity;
[155]517    FlowMap* flow;
518  public:
[168]519
[330]520    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
521                    FlowMap& _flow) :
522      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
[168]523
[174]524    class Edge;
[155]525    class OutEdgeIt;
[174]526    friend class Edge;
[155]527    friend class OutEdgeIt;
[76]528
[311]529    typedef typename GraphWrapper<Graph>::Node Node;
530    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
[317]531    class Edge : public Graph::Edge {
[330]532      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[155]533    protected:
[317]534      bool forward; //true, iff forward
535//      typename Graph::Edge e;
[155]536    public:
[317]537      Edge() { }
538      Edge(const typename Graph::Edge& _e, bool _forward) :
539        Graph::Edge(_e), forward(_forward) { }
540      Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
541//the unique invalid iterator
[174]542      friend bool operator==(const Edge& u, const Edge& v) {
[317]543        return (v.forward==u.forward &&
544                static_cast<typename Graph::Edge>(u)==
545                static_cast<typename Graph::Edge>(v));
[174]546      }
547      friend bool operator!=(const Edge& u, const Edge& v) {
[317]548        return (v.forward!=u.forward ||
549                static_cast<typename Graph::Edge>(u)!=
550                static_cast<typename Graph::Edge>(v));
[174]551      }
[155]552    };
[338]553
[317]554    class OutEdgeIt {
[330]555      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[317]556    protected:
557      typename Graph::OutEdgeIt out;
558      typename Graph::InEdgeIt in;
559      bool forward;
[155]560    public:
561      OutEdgeIt() { }
[168]562      //FIXME
[317]563//      OutEdgeIt(const Edge& e) : Edge(e) { }
564      OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
565//the unique invalid iterator
[330]566      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
[317]567        forward=true;
[303]568        resG.graph->first(out, v);
[317]569        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
[303]570        if (!resG.graph->valid(out)) {
[317]571          forward=false;
[303]572          resG.graph->first(in, v);
[317]573          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
[155]574        }
575      }
[317]576      operator Edge() const {
577//      Edge e;
578//      e.forward=this->forward;
579//      if (this->forward) e=out; else e=in;
580//      return e;
581        if (this->forward)
582          return Edge(out, this->forward);
583        else
584          return Edge(in, this->forward);
585      }
586    };
[263]587
[317]588    class InEdgeIt {
[330]589      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[317]590    protected:
591      typename Graph::OutEdgeIt out;
592      typename Graph::InEdgeIt in;
593      bool forward;
594    public:
595      InEdgeIt() { }
596      //FIXME
597//      OutEdgeIt(const Edge& e) : Edge(e) { }
598      InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
599//the unique invalid iterator
[330]600      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
[317]601        forward=true;
602        resG.graph->first(in, v);
603        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
604        if (!resG.graph->valid(in)) {
605          forward=false;
606          resG.graph->first(out, v);
607          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
608        }
609      }
610      operator Edge() const {
611//      Edge e;
612//      e.forward=this->forward;
613//      if (this->forward) e=out; else e=in;
614//      return e;
615        if (this->forward)
616          return Edge(in, this->forward);
617        else
618          return Edge(out, this->forward);
619      }
620    };
621
622    class EdgeIt {
[330]623      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
[317]624    protected:
625      typename Graph::EdgeIt e;
626      bool forward;
[155]627    public:
[174]628      EdgeIt() { }
[317]629      EdgeIt(const Invalid& i) : e(i), forward(false) { }
[330]630      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
[317]631        forward=true;
632        resG.graph->first(e);
633        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
634        if (!resG.graph->valid(e)) {
635          forward=false;
636          resG.graph->first(e);
637          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
[155]638        }
639      }
[317]640      operator Edge() const {
641        return Edge(e, this->forward);
642      }
643    };
[155]644
[338]645    using GraphWrapper<Graph>::first;
646//     NodeIt& first(NodeIt& i) const {
647//       i=NodeIt(*this); return i;
648//     }
[311]649    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
[317]650      i=OutEdgeIt(*this, p); return i;
[311]651    }
[317]652//    FIXME not tested
653    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
654      i=InEdgeIt(*this, p); return i;
655    }
656    EdgeIt& first(EdgeIt& i) const {
657      i=EdgeIt(*this); return i;
[155]658    }
[338]659 
660    using GraphWrapper<Graph>::next;
661//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
[155]662    OutEdgeIt& next(OutEdgeIt& e) const {
[317]663      if (e.forward) {
[389]664        Node v=this->graph->aNode(e.out);
665        this->graph->next(e.out);
666        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
667          this->graph->next(e.out); }
668        if (!this->graph->valid(e.out)) {
[317]669          e.forward=false;
[389]670          this->graph->first(e.in, v);
671          while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
672            this->graph->next(e.in); }
[155]673        }
674      } else {
[389]675        this->graph->next(e.in);
676        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
677          this->graph->next(e.in); }
[155]678      }
679      return e;
680    }
[317]681//     FIXME Not tested
682    InEdgeIt& next(InEdgeIt& e) const {
683      if (e.forward) {
[389]684        Node v=this->graph->aNode(e.in);
685        this->graph->next(e.in);
686        while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
687          this->graph->next(e.in); }
688        if (!this->graph->valid(e.in)) {
[317]689          e.forward=false;
[389]690          this->graph->first(e.out, v);
691          while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
692            this->graph->next(e.out); }
[317]693        }
694      } else {
[389]695        this->graph->next(e.out);
696        while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
697          this->graph->next(e.out); }
[317]698      }
699      return e;
700    }
701    EdgeIt& next(EdgeIt& e) const {
702      if (e.forward) {
[389]703        this->graph->next(e.e);
704        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
705          this->graph->next(e.e); }
706        if (!this->graph->valid(e.e)) {
[317]707          e.forward=false;
[389]708          this->graph->first(e.e);
709          while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
710            this->graph->next(e.e); }
[155]711        }
[317]712      } else {
[389]713        this->graph->next(e.e);
714        while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
715          this->graph->next(e.e); }
[155]716      }
[317]717      return e;
718    }
[76]719
[174]720    Node tail(Edge e) const {
[389]721      return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
[174]722    Node head(Edge e) const {
[389]723      return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
[76]724
[174]725    Node aNode(OutEdgeIt e) const {
[389]726      return ((e.forward) ? this->graph->aNode(e.out) :
727              this->graph->aNode(e.in)); }
[174]728    Node bNode(OutEdgeIt e) const {
[389]729      return ((e.forward) ? this->graph->bNode(e.out) :
730              this->graph->bNode(e.in)); }
[76]731
[376]732    Node aNode(InEdgeIt e) const {
[389]733      return ((e.forward) ? this->graph->aNode(e.in) :
734              this->graph->aNode(e.out)); }
[376]735    Node bNode(InEdgeIt e) const {
[389]736      return ((e.forward) ? this->graph->bNode(e.in) :
737              this->graph->bNode(e.out)); }
[376]738
[338]739//    int nodeNum() const { return graph->nodeNum(); }
[263]740    //FIXME
[338]741    void edgeNum() const { }
[303]742    //int edgeNum() const { return graph->edgeNum(); }
[263]743
744
[317]745//    int id(Node v) const { return graph->id(v); }
[155]746
[317]747    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
[174]748    bool valid(Edge e) const {
[389]749      return this->graph->valid(e);
[317]750        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
751    }
[155]752
[174]753    void augment(const Edge& e, Number a) const {
[317]754      if (e.forward) 
[303]755//      flow->set(e.out, flow->get(e.out)+a);
[317]756        flow->set(e, (*flow)[e]+a);
[168]757      else 
[303]758//      flow->set(e.in, flow->get(e.in)-a);
[317]759        flow->set(e, (*flow)[e]-a);
[168]760    }
761
[269]762    Number resCap(const Edge& e) const {
[317]763      if (e.forward)
[303]764//      return (capacity->get(e.out)-flow->get(e.out));
[317]765        return ((*capacity)[e]-(*flow)[e]);
[168]766      else
[303]767//      return (flow->get(e.in));
[317]768        return ((*flow)[e]);
[168]769    }
770
[317]771//     Number resCap(typename Graph::OutEdgeIt out) const {
772// //      return (capacity->get(out)-flow->get(out));
773//       return ((*capacity)[out]-(*flow)[out]);
774//     }
[168]775   
[317]776//     Number resCap(typename Graph::InEdgeIt in) const {
777// //      return (flow->get(in));
778//       return ((*flow)[in]);
779//     }
[168]780
[155]781    template <typename T>
782    class EdgeMap {
[389]783      typename Graph::template EdgeMap<T> forward_map, backward_map;
[155]784    public:
[330]785      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
786      EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
[174]787      void set(Edge e, T a) {
[317]788        if (e.forward)
[155]789          forward_map.set(e.out, a);
790        else
791          backward_map.set(e.in, a);
792      }
[303]793      T operator[](Edge e) const {
[317]794        if (e.forward)
[303]795          return forward_map[e.out];
[155]796        else
[303]797          return backward_map[e.in];
[155]798      }
[303]799//       T get(Edge e) const {
800//      if (e.out_or_in)
801//        return forward_map.get(e.out);
802//      else
803//        return backward_map.get(e.in);
804//       }
[155]805    };
[168]806  };
807
[338]808  /// ErasingFirstGraphWrapper for blocking flows.
[317]809
[338]810  /// ErasingFirstGraphWrapper for blocking flows.
[303]811  template<typename Graph, typename FirstOutEdgesMap>
812  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
[269]813  protected:
814    FirstOutEdgesMap* first_out_edges;
815  public:
[303]816    ErasingFirstGraphWrapper(Graph& _graph,
817                             FirstOutEdgesMap& _first_out_edges) :
818      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
[269]819
[317]820    typedef typename GraphWrapper<Graph>::Node Node;
[338]821//     class NodeIt {
822//       friend class GraphWrapper<Graph>;
823//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
824//       typename Graph::NodeIt n;
825//      public:
826//       NodeIt() { }
827//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
828//       NodeIt(const Invalid& i) : n(i) { }
829//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
830//      n(*(_G.graph)) { }
831//       operator Node() const { return Node(typename Graph::Node(n)); }
832//     };
[317]833    typedef typename GraphWrapper<Graph>::Edge Edge;
834    class OutEdgeIt {
835      friend class GraphWrapper<Graph>;
836      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
837//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
838      typename Graph::OutEdgeIt e;
[311]839    public:
840      OutEdgeIt() { }
[317]841      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
842      OutEdgeIt(const Invalid& i) : e(i) { }
[311]843      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
[317]844                const Node& _n) :
845        e((*_G.first_out_edges)[_n]) { }
846      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]847    };
[317]848    class InEdgeIt {
849      friend class GraphWrapper<Graph>;
850      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
851//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
852      typename Graph::InEdgeIt e;
[311]853    public:
854      InEdgeIt() { }
[317]855      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
856      InEdgeIt(const Invalid& i) : e(i) { }
[311]857      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
[317]858               const Node& _n) :
859        e(*(_G.graph), typename Graph::Node(_n)) { }
860      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]861    };
862    //typedef typename Graph::SymEdgeIt SymEdgeIt;
[317]863    class EdgeIt {
864      friend class GraphWrapper<Graph>;
865      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
866//      typedef typename Graph::EdgeIt GraphEdgeIt;
867      typename Graph::EdgeIt e;
[311]868    public:
869      EdgeIt() { }
[317]870      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
871      EdgeIt(const Invalid& i) : e(i) { }
[311]872      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
[317]873        e(*(_G.graph)) { }
874      operator Edge() const { return Edge(typename Graph::Edge(e)); }
[311]875    };
876
[338]877    using GraphWrapper<Graph>::first;
878//     NodeIt& first(NodeIt& i) const {
879//       i=NodeIt(*this); return i;
880//     }
[317]881    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
882      i=OutEdgeIt(*this, p); return i;
[269]883    }
[317]884    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
885      i=InEdgeIt(*this, p); return i;
[311]886    }
[317]887    EdgeIt& first(EdgeIt& i) const {
888      i=EdgeIt(*this); return i;
[311]889    }
890
[338]891    using GraphWrapper<Graph>::next;
892//    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
[389]893    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
894    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
895    EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
[317]896   
[389]897    Node aNode(const OutEdgeIt& e) const {
898      return Node(this->graph->aNode(e.e)); }
899    Node aNode(const InEdgeIt& e) const {
900      return Node(this->graph->aNode(e.e)); }
901    Node bNode(const OutEdgeIt& e) const {
902      return Node(this->graph->bNode(e.e)); }
903    Node bNode(const InEdgeIt& e) const {
904      return Node(this->graph->bNode(e.e)); }
[311]905
[269]906    void erase(const OutEdgeIt& e) const {
907      OutEdgeIt f=e;
908      this->next(f);
[317]909      first_out_edges->set(this->tail(e), f.e);
[269]910    }
911  };
912
[368]913  /// A wrapper for composing a bipartite graph.
[371]914  /// \c _graph have to be a reference to a graph of type \c Graph
915  /// and \c _s_false_t_true_map is an \c IterableBoolMap
[368]916  /// reference containing the elements for the
[371]917  /// color classes S and T. \c _graph is to be referred to an undirected
918  /// graph or a directed graph with edges oriented from S to T.
[368]919  template<typename Graph>
920  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
[389]921    typedef IterableBoolMap< typename Graph::template NodeMap<int> >
922    SFalseTTrueMap;
[368]923    SFalseTTrueMap* s_false_t_true_map;
[393]924
[368]925  public:
[409]926    //marci
927    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
928    //static const bool S_CLASS=false;
929    //static const bool T_CLASS=true;
[379]930   
[409]931    bool S_CLASS;
932    bool T_CLASS;
933
[368]934    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
[409]935      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),
936      S_CLASS(false), T_CLASS(true) { }
[368]937    typedef typename GraphWrapper<Graph>::Node Node;
938    //using GraphWrapper<Graph>::NodeIt;
939    typedef typename GraphWrapper<Graph>::Edge Edge;
940    //using GraphWrapper<Graph>::EdgeIt;
[393]941    class ClassNodeIt;
942    friend class ClassNodeIt;
943    class OutEdgeIt;
944    friend class OutEdgeIt;
945    class InEdgeIt;
946    friend class InEdgeIt;
[379]947    class ClassNodeIt {
[393]948      friend class BipartiteGraphWrapper<Graph>;
949    protected:
[368]950      Node n;
951    public:
[379]952      ClassNodeIt() { }
953      ClassNodeIt(const Invalid& i) : n(i) { }
954      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
955        _G.s_false_t_true_map->first(n, _class);
[368]956      }
[381]957      //FIXME needed in new concept, important here
958      ClassNodeIt(const Node& _n) : n(_n) { }
[368]959      operator Node() const { return n; }
960    };
[379]961//     class SNodeIt {
962//       Node n;
963//     public:
964//       SNodeIt() { }
965//       SNodeIt(const Invalid& i) : n(i) { }
966//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
967//      _G.s_false_t_true_map->first(n, false);
968//       }
969//       operator Node() const { return n; }
970//     };
971//     class TNodeIt {
972//       Node n;
973//     public:
974//       TNodeIt() { }
975//       TNodeIt(const Invalid& i) : n(i) { }
976//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
977//      _G.s_false_t_true_map->first(n, true);
978//       }
979//       operator Node() const { return n; }
980//     };
[368]981    class OutEdgeIt {
[393]982      friend class BipartiteGraphWrapper<Graph>;
983    protected:
[368]984      typename Graph::OutEdgeIt e;
985    public:
986      OutEdgeIt() { }
987      OutEdgeIt(const Invalid& i) : e(i) { }
988      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
989        if (!(*(_G.s_false_t_true_map))[_n])
[379]990          e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
[368]991        else
992          e=INVALID;
993      }
994      operator Edge() const { return Edge(typename Graph::Edge(e)); }
995    };
996    class InEdgeIt {
[393]997      friend class BipartiteGraphWrapper<Graph>;
998    protected:
[368]999      typename Graph::InEdgeIt e;
1000    public:
1001      InEdgeIt() { }
1002      InEdgeIt(const Invalid& i) : e(i) { }
1003      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1004        if ((*(_G.s_false_t_true_map))[_n])
[379]1005          e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
[368]1006        else
1007          e=INVALID;
1008      }
1009      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1010    };
1011
1012    using GraphWrapper<Graph>::first;
[379]1013    ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
[393]1014      n=ClassNodeIt(*this, _class) ; return n; }
[379]1015//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
1016//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
1017    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1018      i=OutEdgeIt(*this, p); return i;
1019    }
1020    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1021      i=InEdgeIt(*this, p); return i;
1022    }
[368]1023
1024    using GraphWrapper<Graph>::next;
[379]1025    ClassNodeIt& next(ClassNodeIt& n) const {
[393]1026      this->s_false_t_true_map->next(n.n); return n;
[368]1027    }
[379]1028//     SNodeIt& next(SNodeIt& n) const {
1029//       this->s_false_t_true_map->next(n); return n;
1030//     }
1031//     TNodeIt& next(TNodeIt& n) const {
1032//       this->s_false_t_true_map->next(n); return n;
1033//     }
[389]1034    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1035    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
[368]1036
1037    Node tail(const Edge& e) {
1038      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1039        return Node(this->graph->tail(e));
1040      else
1041        return Node(this->graph->head(e));     
1042    }
1043    Node head(const Edge& e) {
1044      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1045        return Node(this->graph->head(e));
1046      else
1047        return Node(this->graph->tail(e));     
1048    }
1049
1050    Node aNode(const OutEdgeIt& e) const {
1051      return Node(this->graph->aNode(e.e));
1052    }
1053    Node aNode(const InEdgeIt& e) const {
1054      return Node(this->graph->aNode(e.e));
1055    }
1056    Node bNode(const OutEdgeIt& e) const {
1057      return Node(this->graph->bNode(e.e));
1058    }
1059    Node bNode(const InEdgeIt& e) const {
1060      return Node(this->graph->bNode(e.e));
1061    }
[379]1062
1063    bool inSClass(const Node& n) const {
[381]1064      return !(*(this->s_false_t_true_map))[n];
[379]1065    }
1066    bool inTClass(const Node& n) const {
[381]1067      return (*(this->s_false_t_true_map))[n];
[379]1068    }
[368]1069  };
1070
[341]1071
[379]1072  /// experimentral, do not try it.
1073  /// It eats a bipartite graph, oriented from S to T.
1074  /// Such one can be made e.g. by the above wrapper.
1075  template<typename Graph>
1076  class stGraphWrapper : public GraphWrapper<Graph> {
1077  public:
1078    class Node;
[381]1079    friend class Node;
[379]1080//GN, int
1081//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1082//es a vege a false azaz (invalid, 3)   
1083    class NodeIt;
[381]1084    friend class NodeIt;
[379]1085//GNI, int
1086    class Edge;
[381]1087    friend class Edge;
[379]1088//GE, int, GN
1089//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1090//invalid: (invalid, 3, invalid)
1091    class OutEdgeIt;
[381]1092    friend class OutEdgeIt;
[379]1093//GO, int, GNI
1094//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1095//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1096//t-bol (invalid, 3, invalid)
1097    class InEdgeIt;
[381]1098    friend class InEdgeIt;
[379]1099//GI, int, GNI
1100//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1101//s-be (invalid, 3, invalid)
1102//t-be (invalid, 2, first), ... (invalid, 3, invalid)
1103    class EdgeIt;
[381]1104    friend class EdgeIt;
[379]1105//(first, 0, invalid) ...
1106//(invalid, 1, vmi)
1107//(invalid, 2, vmi)
1108//invalid, 3, invalid)
1109    template <typename T> class NodeMap;
[409]1110    template <typename T, typename Parent> class EdgeMap;
[341]1111
[379]1112//    template <typename T> friend class NodeMap;
1113//    template <typename T> friend class EdgeMap;
[341]1114
[379]1115    const Node S_NODE;
1116    const Node T_NODE;
[341]1117
[379]1118    static const bool S_CLASS=false;
1119    static const bool T_CLASS=true;
[341]1120
[379]1121    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1122                                    S_NODE(INVALID, 1),
1123                                    T_NODE(INVALID, 2) { }
[341]1124
[379]1125    class Node : public Graph::Node {
1126    protected:
1127      friend class GraphWrapper<Graph>;
1128      friend class stGraphWrapper<Graph>;
[389]1129      template <typename T> friend class NodeMap;
[380]1130      friend class Edge;
1131      friend class OutEdgeIt;
1132      friend class InEdgeIt;
1133      friend class EdgeIt;
[379]1134      int spec;
1135    public:
1136      Node() { }
1137      Node(const typename Graph::Node& _n, int _spec=0) :
1138        Graph::Node(_n), spec(_spec) { }
1139      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1140      friend bool operator==(const Node& u, const Node& v) {
1141        return (u.spec==v.spec &&
1142                static_cast<typename Graph::Node>(u)==
1143                static_cast<typename Graph::Node>(v));
1144      }
1145      friend bool operator!=(const Node& u, const Node& v) {
1146        return (v.spec!=u.spec ||
1147                static_cast<typename Graph::Node>(u)!=
1148                static_cast<typename Graph::Node>(v));
[409]1149      }
1150      friend std::ostream& operator<<(std::ostream& os, const Node& i);
[379]1151      int getSpec() const { return spec; }
1152    };
[409]1153
[379]1154    class NodeIt {
1155      friend class GraphWrapper<Graph>;
1156      friend class stGraphWrapper<Graph>;
1157      typename Graph::NodeIt n;
1158      int spec;
1159     public:
1160      NodeIt() { }
1161      NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1162        n(_n), spec(_spec) { }
1163      NodeIt(const Invalid& i) : n(i), spec(3) { }
[381]1164      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
[409]1165        if (!_G.graph->valid(n)) spec=1;
[379]1166      }
1167      operator Node() const { return Node(n, spec); }
1168    };
[409]1169
[379]1170    class Edge : public Graph::Edge {
1171      friend class GraphWrapper<Graph>;
1172      friend class stGraphWrapper<Graph>;
[409]1173      template <typename T, typename Parent> friend class EdgeMap;
[379]1174      int spec;
1175      typename Graph::Node n;
1176    public:
1177      Edge() { }
1178      Edge(const typename Graph::Edge& _e, int _spec,
1179           const typename Graph::Node& _n) :
1180        Graph::Edge(_e), spec(_spec), n(_n) {
1181      }
1182      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1183      friend bool operator==(const Edge& u, const Edge& v) {
1184        return (u.spec==v.spec &&
1185                static_cast<typename Graph::Edge>(u)==
1186                static_cast<typename Graph::Edge>(v) &&
1187                u.n==v.n);
1188      }
1189      friend bool operator!=(const Edge& u, const Edge& v) {
1190        return (v.spec!=u.spec ||
1191                static_cast<typename Graph::Edge>(u)!=
1192                static_cast<typename Graph::Edge>(v) ||
1193                u.n!=v.n);
1194      }
[409]1195      friend std::ostream& operator<<(std::ostream& os, const Edge& i);
[379]1196      int getSpec() const { return spec; }
1197    };
[409]1198
[379]1199    class OutEdgeIt {
1200      friend class GraphWrapper<Graph>;
1201      friend class stGraphWrapper<Graph>;
1202      typename Graph::OutEdgeIt e;
1203      int spec;
1204      typename Graph::ClassNodeIt n;
1205    public:
1206      OutEdgeIt() { }
1207      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1208                const typename Graph::ClassNodeIt& _n) :
1209        e(_e), spec(_spec), n(_n) {
1210      }
1211      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
[381]1212      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
[379]1213        switch (_n.spec) {
1214          case 0 :
[381]1215            if (_G.graph->inSClass(_n)) { //S, van normalis kiel
[379]1216              e=typename Graph::OutEdgeIt(*(_G.graph),
1217                                          typename Graph::Node(_n));
1218              spec=0;
1219              n=INVALID;
1220              if (!_G.graph->valid(e)) spec=3;
1221            } else { //T, specko kiel van
1222              e=INVALID;
1223              spec=2;
1224              n=_n;
1225            }
1226            break;
1227          case 1:
1228            e=INVALID;
1229            spec=1;
1230            _G.graph->first(n, S_CLASS); //s->vmi;
1231            if (!_G.graph->valid(n)) spec=3; //Ha S ures
1232            break;
1233          case 2:
1234            e=INVALID;
1235            spec=3;
1236            n=INVALID;
1237            break;
1238        }
1239      }
1240      operator Edge() const { return Edge(e, spec, n); }
1241    };
[409]1242
[379]1243    class InEdgeIt {
1244      friend class GraphWrapper<Graph>;
1245      friend class stGraphWrapper<Graph>;
1246      typename Graph::InEdgeIt e;
1247      int spec;
1248      typename Graph::ClassNodeIt n;
1249    public:
1250      InEdgeIt() { }
1251      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1252               const typename Graph::ClassNodeIt& _n) :
1253        e(_e), spec(_spec), n(_n) {
1254      }
1255      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
[381]1256      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
[379]1257        switch (_n.spec) {
1258          case 0 :
[381]1259            if (_G.graph->inTClass(_n)) { //T, van normalis beel
[379]1260              e=typename Graph::InEdgeIt(*(_G.graph),
1261                                         typename Graph::Node(_n));
1262              spec=0;
1263              n=INVALID;
1264              if (!_G.graph->valid(e)) spec=3;
1265            } else { //S, specko beel van
1266              e=INVALID;
1267              spec=1;
1268              n=_n;
1269            }
1270            break;
1271          case 1:
1272            e=INVALID;
1273            spec=3;
1274            n=INVALID;
[409]1275            break;
[379]1276          case 2:
1277            e=INVALID;
[409]1278            spec=2;
[379]1279            _G.graph->first(n, T_CLASS); //vmi->t;
1280            if (!_G.graph->valid(n)) spec=3; //Ha T ures
1281            break;
1282        }
1283      }
1284      operator Edge() const { return Edge(e, spec, n); }
1285    };
[409]1286
[379]1287    class EdgeIt {
1288      friend class GraphWrapper<Graph>;
1289      friend class stGraphWrapper<Graph>;
1290      typename Graph::EdgeIt e;
1291      int spec;
1292      typename Graph::ClassNodeIt n;
1293    public:
1294      EdgeIt() { }
1295      EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1296             const typename Graph::ClassNodeIt& _n) :
1297        e(_e), spec(_spec), n(_n) { }
1298      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
[381]1299      EdgeIt(const stGraphWrapper<Graph>& _G) :
[379]1300        e(*(_G.graph)), spec(0), n(INVALID) {
1301        if (!_G.graph->valid(e)) {
1302          spec=1;
1303          _G.graph->first(n, S_CLASS);
1304          if (!_G.graph->valid(n)) { //Ha S ures
1305            spec=2;
1306            _G.graph->first(n, T_CLASS);
1307            if (!_G.graph->valid(n)) { //Ha T ures
1308              spec=3;
1309            }
1310          }
1311        }
1312      }
1313      operator Edge() const { return Edge(e, spec, n); }
1314    };
[341]1315   
[379]1316    NodeIt& first(NodeIt& i) const {
1317      i=NodeIt(*this); return i;
1318    }
1319    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1320      i=OutEdgeIt(*this, p); return i;
1321    }
1322    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1323      i=InEdgeIt(*this, p); return i;
1324    }
1325    EdgeIt& first(EdgeIt& i) const {
1326      i=EdgeIt(*this); return i;
1327    }
[341]1328
[379]1329    NodeIt& next(NodeIt& i) const {
1330      switch (i.spec) {
1331        case 0:
[389]1332          this->graph->next(i.n);
1333          if (!this->graph->valid(i.n)) {
[379]1334            i.spec=1;
1335          }
1336          break;
1337        case 1:
1338          i.spec=2;
1339          break;
1340        case 2:
1341          i.spec=3;
1342          break;
1343      }
1344      return i;
1345    }
1346    OutEdgeIt& next(OutEdgeIt& i) const {
[393]1347      typename Graph::Node v;
[379]1348      switch (i.spec) {
1349        case 0: //normal edge
[409]1350          v=this->graph->aNode(i.e);
[389]1351          this->graph->next(i.e);
1352          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1353            if (this->graph->inSClass(v)) { //S, nincs kiel
[379]1354              i.spec=3;
1355              i.n=INVALID;
1356            } else { //T, van kiel
1357              i.spec=2;
1358              i.n=v;
1359            }
1360          }
1361          break;
1362        case 1: //s->vmi
[389]1363          this->graph->next(i.n);
1364          if (!this->graph->valid(i.n)) i.spec=3;
[379]1365          break;
1366        case 2: //vmi->t
1367          i.spec=3;
1368          i.n=INVALID;
1369          break;
1370      }
1371      return i;
1372    }
1373    InEdgeIt& next(InEdgeIt& i) const {
[393]1374      typename Graph::Node v;
[379]1375      switch (i.spec) {
1376        case 0: //normal edge
[393]1377          v=this->graph->aNode(i.e);
[389]1378          this->graph->next(i.e);
1379          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1380            if (this->graph->inTClass(v)) { //S, nincs beel
[379]1381              i.spec=3;
1382              i.n=INVALID;
1383            } else { //S, van beel
1384              i.spec=1;
1385              i.n=v;
1386            }
1387          }
1388          break;
1389        case 1: //s->vmi
1390          i.spec=3;
1391          i.n=INVALID;
1392          break;
1393        case 2: //vmi->t
[389]1394          this->graph->next(i.n);
1395          if (!this->graph->valid(i.n)) i.spec=3;
[379]1396          break;
1397      }
1398      return i;
1399    }
[341]1400
[379]1401    EdgeIt& next(EdgeIt& i) const {
1402      switch (i.spec) {
1403        case 0:
[389]1404          this->graph->next(i.e);
1405          if (!this->graph->valid(i.e)) {
[379]1406            i.spec=1;
[389]1407            this->graph->first(i.n, S_CLASS);
1408            if (!this->graph->valid(i.n)) {
[379]1409              i.spec=2;
[389]1410              this->graph->first(i.n, T_CLASS);
1411              if (!this->graph->valid(i.n)) i.spec=3;
[379]1412            }
1413          }
1414          break;
1415        case 1:
[389]1416          this->graph->next(i.n);
1417          if (!this->graph->valid(i.n)) {
[379]1418            i.spec=2;
[389]1419            this->graph->first(i.n, T_CLASS);
1420            if (!this->graph->valid(i.n)) i.spec=3;
[379]1421          }
1422          break;
1423        case 2:
[389]1424          this->graph->next(i.n);
1425          if (!this->graph->valid(i.n)) i.spec=3;
[379]1426          break;
1427      }
1428      return i;
1429    }   
[341]1430
[379]1431    Node tail(const Edge& e) const {
1432      switch (e.spec) {
[393]1433      case 0:
1434        return Node(this->graph->tail(e));
1435        break;
1436      case 1:
1437        return S_NODE;
1438        break;
1439      case 2:
1440      default:
1441        return Node(e.n);
1442        break;
[379]1443      }
1444    }
1445    Node head(const Edge& e) const {
1446      switch (e.spec) {
[393]1447      case 0:
1448        return Node(this->graph->head(e));
1449        break;
1450      case 1:
1451        return Node(e.n);
1452        break;
1453      case 2:
1454      default:
1455        return T_NODE;
1456        break;
[379]1457      }
1458    }
[341]1459
[379]1460    bool valid(const Node& n) const { return (n.spec<3); }
1461    bool valid(const Edge& e) const { return (e.spec<3); }
1462
[409]1463    int nodeNum() const { return this->graph->nodeNum()+2; }
1464    int edgeNum() const {
1465      return this->graph->edgeNum()+this->graph->nodeNum();
1466    }
[341]1467 
[379]1468    Node aNode(const OutEdgeIt& e) const { return tail(e); }
1469    Node aNode(const InEdgeIt& e) const { return head(e); }
1470    Node bNode(const OutEdgeIt& e) const { return head(e); }
1471    Node bNode(const InEdgeIt& e) const { return tail(e); }
[409]1472
1473    void addNode() const { }
1474    void addEdge() const { }
1475   
[389]1476//    Node addNode() const { return Node(this->graph->addNode()); }
[379]1477//    Edge addEdge(const Node& tail, const Node& head) const {
[389]1478//      return Edge(this->graph->addEdge(tail, head)); }
[341]1479
[389]1480//    void erase(const Node& i) const { this->graph->erase(i); }
1481//    void erase(const Edge& i) const { this->graph->erase(i); }
[341]1482 
[389]1483//    void clear() const { this->graph->clear(); }
[341]1484   
[389]1485    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
1486      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
[379]1487      T s_value, t_value;
1488    public:
[409]1489      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G),
1490                                                  s_value(),
1491                                                  t_value() { }
[389]1492      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1493                                                      s_value(a),
1494                                                      t_value(a) { }
[379]1495      T operator[](const Node& n) const {
1496        switch (n.spec) {
[393]1497        case 0:
1498          return Parent::operator[](n);
1499          break;
1500        case 1:
1501          return s_value;
1502          break;
1503        case 2:
1504        default:
1505          return t_value;
1506          break;
[379]1507        }
1508      }
1509      void set(const Node& n, T t) {
1510        switch (n.spec) {
[393]1511        case 0:
1512          GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
1513          break;
1514        case 1:
1515          s_value=t;
1516          break;
1517        case 2:
1518        default:
1519          t_value=t;
1520          break;
[379]1521        }
1522      }
1523    };
[341]1524
[409]1525    template<typename T,
1526             typename Parent=
1527             typename GraphWrapper<Graph>::template EdgeMap<T> >
1528    class EdgeMap : public Parent {
1529      //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
[389]1530      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
[379]1531    public:
[393]1532      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1533                                                 node_value(_G) { }
[389]1534      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1535                                                      node_value(_G, a) { }
[379]1536      T operator[](const Edge& e) const {
1537        switch (e.spec) {
[393]1538        case 0:
1539          return Parent::operator[](e);
1540          break;
1541        case 1:
1542          return node_value[e.n];
1543          break;
1544        case 2:
1545        default:
1546          return node_value[e.n];
1547          break;
[379]1548        }
1549      }
1550      void set(const Edge& e, T t) {
1551        switch (e.spec) {
[393]1552        case 0:
[409]1553          Parent::set(e, t);
[393]1554          break;
1555        case 1:
1556          node_value.set(e.n, t);
1557          break;
1558        case 2:
1559        default:
1560          node_value.set(e.n, t);
1561          break;
[379]1562        }
1563      }
1564    };
[409]1565
1566//     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
1567//       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1568//       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1569//     public:
1570//       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1571//                                               node_value(_G) { }
1572//       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1573//                                                    node_value(_G, a) { }
1574//       T operator[](const Edge& e) const {
1575//      switch (e.spec) {
1576//      case 0:
1577//        return Parent::operator[](e);
1578//        break;
1579//      case 1:
1580//        return node_value[e.n];
1581//        break;
1582//      case 2:
1583//      default:
1584//        return node_value[e.n];
1585//        break;
1586//      }
1587//       }
1588//       void set(const Edge& e, T t) {
1589//      switch (e.spec) {
1590//      case 0:
1591//        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
1592//        break;
1593//      case 1:
1594//        node_value.set(e.n, t);
1595//        break;
1596//      case 2:
1597//      default:
1598//        node_value.set(e.n, t);
1599//        break;
1600//      }
1601//       }
1602//     };
1603
1604    friend std::ostream& operator<<(std::ostream& os, const Node& i) {
1605      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1606      return os;
1607    }
1608    friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
1609      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
1610        " node: " << i.n << ")";
1611      return os;
1612    }
1613
[379]1614  };
1615
[406]1616  ///@}
[341]1617
[105]1618} //namespace hugo
[76]1619
[406]1620
[259]1621#endif //HUGO_GRAPH_WRAPPER_H
[76]1622
Note: See TracBrowser for help on using the repository browser.