# source:lemon-0.x/src/work/marci/graph_wrapper.h@393:4535f78639e2

Last change on this file since 393:4535f78639e2 was 393:4535f78639e2, checked in by marci, 20 years ago

misc

File size: 48.5 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    friend class ClassNodeIt;
935    class OutEdgeIt;
936    friend class OutEdgeIt;
937    class InEdgeIt;
938    friend class InEdgeIt;
939    class ClassNodeIt {
940      friend class BipartiteGraphWrapper<Graph>;
941    protected:
942      Node n;
943    public:
944      ClassNodeIt() { }
945      ClassNodeIt(const Invalid& i) : n(i) { }
946      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
947        _G.s_false_t_true_map->first(n, _class);
948      }
949      //FIXME needed in new concept, important here
950      ClassNodeIt(const Node& _n) : n(_n) { }
951      operator Node() const { return n; }
952    };
953//     class SNodeIt {
954//       Node n;
955//     public:
956//       SNodeIt() { }
957//       SNodeIt(const Invalid& i) : n(i) { }
958//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
959//      _G.s_false_t_true_map->first(n, false);
960//       }
961//       operator Node() const { return n; }
962//     };
963//     class TNodeIt {
964//       Node n;
965//     public:
966//       TNodeIt() { }
967//       TNodeIt(const Invalid& i) : n(i) { }
968//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
969//      _G.s_false_t_true_map->first(n, true);
970//       }
971//       operator Node() const { return n; }
972//     };
973    class OutEdgeIt {
974      friend class BipartiteGraphWrapper<Graph>;
975    protected:
976      typename Graph::OutEdgeIt e;
977    public:
978      OutEdgeIt() { }
979      OutEdgeIt(const Invalid& i) : e(i) { }
980      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
981        if (!(*(_G.s_false_t_true_map))[_n])
982          e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
983        else
984          e=INVALID;
985      }
986      operator Edge() const { return Edge(typename Graph::Edge(e)); }
987    };
988    class InEdgeIt {
989      friend class BipartiteGraphWrapper<Graph>;
990    protected:
991      typename Graph::InEdgeIt e;
992    public:
993      InEdgeIt() { }
994      InEdgeIt(const Invalid& i) : e(i) { }
995      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
996        if ((*(_G.s_false_t_true_map))[_n])
997          e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
998        else
999          e=INVALID;
1000      }
1001      operator Edge() const { return Edge(typename Graph::Edge(e)); }
1002    };
1003
1004    using GraphWrapper<Graph>::first;
1005    ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
1006      n=ClassNodeIt(*this, _class) ; return n; }
1007//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
1008//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
1009    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1010      i=OutEdgeIt(*this, p); return i;
1011    }
1012    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1013      i=InEdgeIt(*this, p); return i;
1014    }
1015
1016    using GraphWrapper<Graph>::next;
1017    ClassNodeIt& next(ClassNodeIt& n) const {
1018      this->s_false_t_true_map->next(n.n); return n;
1019    }
1020//     SNodeIt& next(SNodeIt& n) const {
1021//       this->s_false_t_true_map->next(n); return n;
1022//     }
1023//     TNodeIt& next(TNodeIt& n) const {
1024//       this->s_false_t_true_map->next(n); return n;
1025//     }
1026    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1027    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1028
1029    Node tail(const Edge& e) {
1030      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1031        return Node(this->graph->tail(e));
1032      else
1034    }
1035    Node head(const Edge& e) {
1036      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1038      else
1039        return Node(this->graph->tail(e));
1040    }
1041
1042    Node aNode(const OutEdgeIt& e) const {
1043      return Node(this->graph->aNode(e.e));
1044    }
1045    Node aNode(const InEdgeIt& e) const {
1046      return Node(this->graph->aNode(e.e));
1047    }
1048    Node bNode(const OutEdgeIt& e) const {
1049      return Node(this->graph->bNode(e.e));
1050    }
1051    Node bNode(const InEdgeIt& e) const {
1052      return Node(this->graph->bNode(e.e));
1053    }
1054
1055    bool inSClass(const Node& n) const {
1056      return !(*(this->s_false_t_true_map))[n];
1057    }
1058    bool inTClass(const Node& n) const {
1059      return (*(this->s_false_t_true_map))[n];
1060    }
1061  };
1062
1063
1064  /// experimentral, do not try it.
1065  /// It eats a bipartite graph, oriented from S to T.
1066  /// Such one can be made e.g. by the above wrapper.
1067  template<typename Graph>
1068  class stGraphWrapper : public GraphWrapper<Graph> {
1069  public:
1070    class Node;
1071    friend class Node;
1072//GN, int
1073//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1074//es a vege a false azaz (invalid, 3)
1075    class NodeIt;
1076    friend class NodeIt;
1077//GNI, int
1078    class Edge;
1079    friend class Edge;
1080//GE, int, GN
1081//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1082//invalid: (invalid, 3, invalid)
1083    class OutEdgeIt;
1084    friend class OutEdgeIt;
1085//GO, int, GNI
1086//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1087//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1088//t-bol (invalid, 3, invalid)
1089    class InEdgeIt;
1090    friend class InEdgeIt;
1091//GI, int, GNI
1092//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1093//s-be (invalid, 3, invalid)
1094//t-be (invalid, 2, first), ... (invalid, 3, invalid)
1095    class EdgeIt;
1096    friend class EdgeIt;
1097//(first, 0, invalid) ...
1098//(invalid, 1, vmi)
1099//(invalid, 2, vmi)
1100//invalid, 3, invalid)
1101    template <typename T> class NodeMap;
1102    template <typename T> class EdgeMap;
1103
1104//    template <typename T> friend class NodeMap;
1105//    template <typename T> friend class EdgeMap;
1106
1107    const Node S_NODE;
1108    const Node T_NODE;
1109
1110    static const bool S_CLASS=false;
1111    static const bool T_CLASS=true;
1112
1113    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1114                                    S_NODE(INVALID, 1),
1115                                    T_NODE(INVALID, 2) { }
1116
1117    class Node : public Graph::Node {
1118    protected:
1119      friend class GraphWrapper<Graph>;
1120      friend class stGraphWrapper<Graph>;
1121      template <typename T> friend class NodeMap;
1122      friend class Edge;
1123      friend class OutEdgeIt;
1124      friend class InEdgeIt;
1125      friend class EdgeIt;
1126      int spec;
1127    public:
1128      Node() { }
1129      Node(const typename Graph::Node& _n, int _spec=0) :
1130        Graph::Node(_n), spec(_spec) { }
1131      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1132      friend bool operator==(const Node& u, const Node& v) {
1133        return (u.spec==v.spec &&
1134                static_cast<typename Graph::Node>(u)==
1135                static_cast<typename Graph::Node>(v));
1136      }
1137      friend bool operator!=(const Node& u, const Node& v) {
1138        return (v.spec!=u.spec ||
1139                static_cast<typename Graph::Node>(u)!=
1140                static_cast<typename Graph::Node>(v));
1141      }
1142      int getSpec() const { return spec; }
1143    };
1144    class NodeIt {
1145      friend class GraphWrapper<Graph>;
1146      friend class stGraphWrapper<Graph>;
1147      typename Graph::NodeIt n;
1148      int spec;
1149     public:
1150      NodeIt() { }
1151      NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1152        n(_n), spec(_spec) { }
1153      NodeIt(const Invalid& i) : n(i), spec(3) { }
1154      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1155        if (!_G->valid(n)) spec=1;
1156      }
1157      operator Node() const { return Node(n, spec); }
1158    };
1159    class Edge : public Graph::Edge {
1160      friend class GraphWrapper<Graph>;
1161      friend class stGraphWrapper<Graph>;
1162      template <typename T> friend class EdgeMap;
1163      int spec;
1164      typename Graph::Node n;
1165    public:
1166      Edge() { }
1167      Edge(const typename Graph::Edge& _e, int _spec,
1168           const typename Graph::Node& _n) :
1169        Graph::Edge(_e), spec(_spec), n(_n) {
1170      }
1171      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1172      friend bool operator==(const Edge& u, const Edge& v) {
1173        return (u.spec==v.spec &&
1174                static_cast<typename Graph::Edge>(u)==
1175                static_cast<typename Graph::Edge>(v) &&
1176                u.n==v.n);
1177      }
1178      friend bool operator!=(const Edge& u, const Edge& v) {
1179        return (v.spec!=u.spec ||
1180                static_cast<typename Graph::Edge>(u)!=
1181                static_cast<typename Graph::Edge>(v) ||
1182                u.n!=v.n);
1183      }
1184      int getSpec() const { return spec; }
1185    };
1186    class OutEdgeIt {
1187      friend class GraphWrapper<Graph>;
1188      friend class stGraphWrapper<Graph>;
1189      typename Graph::OutEdgeIt e;
1190      int spec;
1191      typename Graph::ClassNodeIt n;
1192    public:
1193      OutEdgeIt() { }
1194      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1195                const typename Graph::ClassNodeIt& _n) :
1196        e(_e), spec(_spec), n(_n) {
1197      }
1198      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1199      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1200        switch (_n.spec) {
1201          case 0 :
1202            if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1203              e=typename Graph::OutEdgeIt(*(_G.graph),
1204                                          typename Graph::Node(_n));
1205              spec=0;
1206              n=INVALID;
1207              if (!_G.graph->valid(e)) spec=3;
1208            } else { //T, specko kiel van
1209              e=INVALID;
1210              spec=2;
1211              n=_n;
1212            }
1213            break;
1214          case 1:
1215            e=INVALID;
1216            spec=1;
1217            _G.graph->first(n, S_CLASS); //s->vmi;
1218            if (!_G.graph->valid(n)) spec=3; //Ha S ures
1219            break;
1220          case 2:
1221            e=INVALID;
1222            spec=3;
1223            n=INVALID;
1224            break;
1225        }
1226      }
1227      operator Edge() const { return Edge(e, spec, n); }
1228    };
1229    class InEdgeIt {
1230      friend class GraphWrapper<Graph>;
1231      friend class stGraphWrapper<Graph>;
1232      typename Graph::InEdgeIt e;
1233      int spec;
1234      typename Graph::ClassNodeIt n;
1235    public:
1236      InEdgeIt() { }
1237      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1238               const typename Graph::ClassNodeIt& _n) :
1239        e(_e), spec(_spec), n(_n) {
1240      }
1241      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1242      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1243        switch (_n.spec) {
1244          case 0 :
1245            if (_G.graph->inTClass(_n)) { //T, van normalis beel
1246              e=typename Graph::InEdgeIt(*(_G.graph),
1247                                         typename Graph::Node(_n));
1248              spec=0;
1249              n=INVALID;
1250              if (!_G.graph->valid(e)) spec=3;
1251            } else { //S, specko beel van
1252              e=INVALID;
1253              spec=1;
1254              n=_n;
1255            }
1256            break;
1257          case 1:
1258            e=INVALID;
1259            spec=3;
1260            n=INVALID;
1261          case 2:
1262            e=INVALID;
1263            spec=1;
1264            _G.graph->first(n, T_CLASS); //vmi->t;
1265            if (!_G.graph->valid(n)) spec=3; //Ha T ures
1266            break;
1267        }
1268      }
1269      operator Edge() const { return Edge(e, spec, n); }
1270    };
1271    class EdgeIt {
1272      friend class GraphWrapper<Graph>;
1273      friend class stGraphWrapper<Graph>;
1274      typename Graph::EdgeIt e;
1275      int spec;
1276      typename Graph::ClassNodeIt n;
1277    public:
1278      EdgeIt() { }
1279      EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1280             const typename Graph::ClassNodeIt& _n) :
1281        e(_e), spec(_spec), n(_n) { }
1282      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1283      EdgeIt(const stGraphWrapper<Graph>& _G) :
1284        e(*(_G.graph)), spec(0), n(INVALID) {
1285        if (!_G.graph->valid(e)) {
1286          spec=1;
1287          _G.graph->first(n, S_CLASS);
1288          if (!_G.graph->valid(n)) { //Ha S ures
1289            spec=2;
1290            _G.graph->first(n, T_CLASS);
1291            if (!_G.graph->valid(n)) { //Ha T ures
1292              spec=3;
1293            }
1294          }
1295        }
1296      }
1297      operator Edge() const { return Edge(e, spec, n); }
1298    };
1299
1300    NodeIt& first(NodeIt& i) const {
1301      i=NodeIt(*this); return i;
1302    }
1303    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1304      i=OutEdgeIt(*this, p); return i;
1305    }
1306    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1307      i=InEdgeIt(*this, p); return i;
1308    }
1309    EdgeIt& first(EdgeIt& i) const {
1310      i=EdgeIt(*this); return i;
1311    }
1312
1313    NodeIt& next(NodeIt& i) const {
1314      switch (i.spec) {
1315        case 0:
1316          this->graph->next(i.n);
1317          if (!this->graph->valid(i.n)) {
1318            i.spec=1;
1319          }
1320          break;
1321        case 1:
1322          i.spec=2;
1323          break;
1324        case 2:
1325          i.spec=3;
1326          break;
1327      }
1328      return i;
1329    }
1330    OutEdgeIt& next(OutEdgeIt& i) const {
1331      typename Graph::Node v;
1332      switch (i.spec) {
1333        case 0: //normal edge
1334          this->graph->aNode(i.e);
1335          this->graph->next(i.e);
1336          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1337            if (this->graph->inSClass(v)) { //S, nincs kiel
1338              i.spec=3;
1339              i.n=INVALID;
1340            } else { //T, van kiel
1341              i.spec=2;
1342              i.n=v;
1343            }
1344          }
1345          break;
1346        case 1: //s->vmi
1347          this->graph->next(i.n);
1348          if (!this->graph->valid(i.n)) i.spec=3;
1349          break;
1350        case 2: //vmi->t
1351          i.spec=3;
1352          i.n=INVALID;
1353          break;
1354      }
1355      return i;
1356    }
1357    InEdgeIt& next(InEdgeIt& i) const {
1358      typename Graph::Node v;
1359      switch (i.spec) {
1360        case 0: //normal edge
1361          v=this->graph->aNode(i.e);
1362          this->graph->next(i.e);
1363          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1364            if (this->graph->inTClass(v)) { //S, nincs beel
1365              i.spec=3;
1366              i.n=INVALID;
1367            } else { //S, van beel
1368              i.spec=1;
1369              i.n=v;
1370            }
1371          }
1372          break;
1373        case 1: //s->vmi
1374          i.spec=3;
1375          i.n=INVALID;
1376          break;
1377        case 2: //vmi->t
1378          this->graph->next(i.n);
1379          if (!this->graph->valid(i.n)) i.spec=3;
1380          break;
1381      }
1382      return i;
1383    }
1384
1385    EdgeIt& next(EdgeIt& i) const {
1386      switch (i.spec) {
1387        case 0:
1388          this->graph->next(i.e);
1389          if (!this->graph->valid(i.e)) {
1390            i.spec=1;
1391            this->graph->first(i.n, S_CLASS);
1392            if (!this->graph->valid(i.n)) {
1393              i.spec=2;
1394              this->graph->first(i.n, T_CLASS);
1395              if (!this->graph->valid(i.n)) i.spec=3;
1396            }
1397          }
1398          break;
1399        case 1:
1400          this->graph->next(i.n);
1401          if (!this->graph->valid(i.n)) {
1402            i.spec=2;
1403            this->graph->first(i.n, T_CLASS);
1404            if (!this->graph->valid(i.n)) i.spec=3;
1405          }
1406          break;
1407        case 2:
1408          this->graph->next(i.n);
1409          if (!this->graph->valid(i.n)) i.spec=3;
1410          break;
1411      }
1412      return i;
1413    }
1414
1415    Node tail(const Edge& e) const {
1416      switch (e.spec) {
1417      case 0:
1418        return Node(this->graph->tail(e));
1419        break;
1420      case 1:
1421        return S_NODE;
1422        break;
1423      case 2:
1424      default:
1425        return Node(e.n);
1426        break;
1427      }
1428    }
1429    Node head(const Edge& e) const {
1430      switch (e.spec) {
1431      case 0:
1433        break;
1434      case 1:
1435        return Node(e.n);
1436        break;
1437      case 2:
1438      default:
1439        return T_NODE;
1440        break;
1441      }
1442    }
1443
1444    bool valid(const Node& n) const { return (n.spec<3); }
1445    bool valid(const Edge& e) const { return (e.spec<3); }
1446
1447//    int nodeNum() const { return this->graph->nodeNum(); }
1448//    int edgeNum() const { return this->graph->edgeNum(); }
1449
1450    Node aNode(const OutEdgeIt& e) const { return tail(e); }
1451    Node aNode(const InEdgeIt& e) const { return head(e); }
1452    Node bNode(const OutEdgeIt& e) const { return head(e); }
1453    Node bNode(const InEdgeIt& e) const { return tail(e); }
1454
1458
1459//    void erase(const Node& i) const { this->graph->erase(i); }
1460//    void erase(const Edge& i) const { this->graph->erase(i); }
1461
1462//    void clear() const { this->graph->clear(); }
1463
1464    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
1465      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
1466      T s_value, t_value;
1467    public:
1468      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G) { }
1469      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1470                                                      s_value(a),
1471                                                      t_value(a) { }
1472      T operator[](const Node& n) const {
1473        switch (n.spec) {
1474        case 0:
1475          return Parent::operator[](n);
1476          break;
1477        case 1:
1478          return s_value;
1479          break;
1480        case 2:
1481        default:
1482          return t_value;
1483          break;
1484        }
1485      }
1486      void set(const Node& n, T t) {
1487        switch (n.spec) {
1488        case 0:
1489          GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
1490          break;
1491        case 1:
1492          s_value=t;
1493          break;
1494        case 2:
1495        default:
1496          t_value=t;
1497          break;
1498        }
1499      }
1500    };
1501
1502    template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
1503      typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1504      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1505    public:
1506      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1507                                                 node_value(_G) { }
1508      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1509                                                      node_value(_G, a) { }
1510      T operator[](const Edge& e) const {
1511        switch (e.spec) {
1512        case 0:
1513          return Parent::operator[](e);
1514          break;
1515        case 1:
1516          return node_value[e.n];
1517          break;
1518        case 2:
1519        default:
1520          return node_value[e.n];
1521          break;
1522        }
1523      }
1524      void set(const Edge& e, T t) {
1525        switch (e.spec) {
1526        case 0:
1527          GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
1528          break;
1529        case 1:
1530          node_value.set(e.n, t);
1531          break;
1532        case 2:
1533        default:
1534          node_value.set(e.n, t);
1535          break;
1536        }
1537      }
1538    };
1539  };
1540
1541
1542} //namespace hugo
1543
1544#endif //HUGO_GRAPH_WRAPPER_H
1545
Note: See TracBrowser for help on using the repository browser.