COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 384:f27d21767d38

Last change on this file since 384:f27d21767d38 was 381:d72470496fbe, checked in by marci, 20 years ago

misc

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