COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/graph_wrapper.h @ 380:6399494e30b1

Last change on this file since 380:6399494e30b1 was 380:6399494e30b1, checked in by marci, 21 years ago

.

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