COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/experiment/graph_wrapper_st_ostream_op.h @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

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