COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 379:a5bff2813c4d

Last change on this file since 379:a5bff2813c4d was 379:a5bff2813c4d, checked in by marci, 21 years ago

.

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