# source:lemon-0.x/src/work/marci/graph_wrapper.h@389:770cc1f4861f

Last change on this file since 389:770cc1f4861f was 389:770cc1f4861f, checked in by marci, 17 years ago

modifications for better compatibility with gcc 3.4.0

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