COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 406:e8377ac921b6

Last change on this file since 406:e8377ac921b6 was 406:e8377ac921b6, checked in by Alpar Juttner, 17 years ago

Docs are now divided into modules.

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