# source:lemon-0.x/src/work/marci/graph_wrapper.h@438:a0a2709cf178

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

The long description is now the description of the module.

File size: 51.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
13  /// A main parts of HUGOlib 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
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 {
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
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 {
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
416    void hide(const Node& n) const { node_filter_map->set(n, false); }
417    ///\todo
419    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
420
421    ///\todo
423    void unHide(const Node& n) const { node_filter_map->set(n, true); }
424    ///\todo
426    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
427
428    ///\todo
430    bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
431    ///\todo
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
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
1049    }
1050    Node head(const Edge& e) {
1051      if (!(*(this->s_false_t_true_map))[this->graph->tail(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  template<typename Graph>
1079  class stGraphWrapper;
1080
1081//   template<typename Graph>
1082//   std::ostream&
1083//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {
1084//     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1085//     return os;
1086//   }
1087//   template<typename Graph>
1088//   std::ostream&
1089//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {
1090//     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
1091//       " node: " << i.n << ")";
1092//     return os;
1093//   }
1094
1095  /// experimentral, do not try it.
1096  /// It eats a bipartite graph, oriented from S to T.
1097  /// Such one can be made e.g. by the above wrapper.
1098  template<typename Graph>
1099  class stGraphWrapper : public GraphWrapper<Graph> {
1100  public:
1101    class Node;
1102    friend class Node;
1103//GN, int
1104//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1105//es a vege a false azaz (invalid, 3)
1106    class NodeIt;
1107    friend class NodeIt;
1108//GNI, int
1109    class Edge;
1110    friend class Edge;
1111//GE, int, GN
1112//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1113//invalid: (invalid, 3, invalid)
1114    class OutEdgeIt;
1115    friend class OutEdgeIt;
1116//GO, int, GNI
1117//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1118//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1119//t-bol (invalid, 3, invalid)
1120    class InEdgeIt;
1121    friend class InEdgeIt;
1122//GI, int, GNI
1123//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1124//s-be (invalid, 3, invalid)
1125//t-be (invalid, 2, first), ... (invalid, 3, invalid)
1126    class EdgeIt;
1127    friend class EdgeIt;
1128//(first, 0, invalid) ...
1129//(invalid, 1, vmi)
1130//(invalid, 2, vmi)
1131//invalid, 3, invalid)
1132    template <typename T> class NodeMap;
1133    template <typename T, typename Parent> class EdgeMap;
1134
1135//    template <typename T> friend class NodeMap;
1136//    template <typename T> friend class EdgeMap;
1137
1138    const Node S_NODE;
1139    const Node T_NODE;
1140
1141    static const bool S_CLASS=false;
1142    static const bool T_CLASS=true;
1143
1144    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1145                                    S_NODE(INVALID, 1),
1146                                    T_NODE(INVALID, 2) { }
1147
1148
1149//    std::ostream&
1150//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
1151//    friend std::ostream&
1152//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
1153//    friend std::ostream&
1154//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
1155
1156    class Node : public Graph::Node {
1157    protected:
1158      friend class GraphWrapper<Graph>;
1159      friend class stGraphWrapper<Graph>;
1160      template <typename T> friend class NodeMap;
1161      friend class Edge;
1162      friend class OutEdgeIt;
1163      friend class InEdgeIt;
1164      friend class EdgeIt;
1165      int spec;
1166    public:
1167      Node() { }
1168      Node(const typename Graph::Node& _n, int _spec=0) :
1169        Graph::Node(_n), spec(_spec) { }
1170      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1171      friend bool operator==(const Node& u, const Node& v) {
1172        return (u.spec==v.spec &&
1173                static_cast<typename Graph::Node>(u)==
1174                static_cast<typename Graph::Node>(v));
1175      }
1176      friend bool operator!=(const Node& u, const Node& v) {
1177        return (v.spec!=u.spec ||
1178                static_cast<typename Graph::Node>(u)!=
1179                static_cast<typename Graph::Node>(v));
1180      }
1181//      template<typename G>
1182//      friend std::ostream&
1183//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);
1184      friend std::ostream& operator<< (std::ostream& os, const Node& i);
1185      int getSpec() const { return spec; }
1186    };
1187
1188    class NodeIt {
1189      friend class GraphWrapper<Graph>;
1190      friend class stGraphWrapper<Graph>;
1191      typename Graph::NodeIt n;
1192      int spec;
1193     public:
1194      NodeIt() { }
1195      NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1196        n(_n), spec(_spec) { }
1197      NodeIt(const Invalid& i) : n(i), spec(3) { }
1198      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1199        if (!_G.graph->valid(n)) spec=1;
1200      }
1201      operator Node() const { return Node(n, spec); }
1202    };
1203
1204    class Edge : public Graph::Edge {
1205      friend class GraphWrapper<Graph>;
1206      friend class stGraphWrapper<Graph>;
1207      template <typename T, typename Parent> friend class EdgeMap;
1208      int spec;
1209      typename Graph::Node n;
1210    public:
1211      Edge() { }
1212      Edge(const typename Graph::Edge& _e, int _spec,
1213           const typename Graph::Node& _n) :
1214        Graph::Edge(_e), spec(_spec), n(_n) {
1215      }
1216      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1217      friend bool operator==(const Edge& u, const Edge& v) {
1218        return (u.spec==v.spec &&
1219                static_cast<typename Graph::Edge>(u)==
1220                static_cast<typename Graph::Edge>(v) &&
1221                u.n==v.n);
1222      }
1223      friend bool operator!=(const Edge& u, const Edge& v) {
1224        return (v.spec!=u.spec ||
1225                static_cast<typename Graph::Edge>(u)!=
1226                static_cast<typename Graph::Edge>(v) ||
1227                u.n!=v.n);
1228      }
1229//      template<typename G>
1230//      friend std::ostream&
1231//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
1232      friend std::ostream& operator<< (std::ostream& os, const Edge& i);
1233      int getSpec() const { return spec; }
1234    };
1235
1236    class OutEdgeIt {
1237      friend class GraphWrapper<Graph>;
1238      friend class stGraphWrapper<Graph>;
1239      typename Graph::OutEdgeIt e;
1240      int spec;
1241      typename Graph::ClassNodeIt n;
1242    public:
1243      OutEdgeIt() { }
1244      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1245                const typename Graph::ClassNodeIt& _n) :
1246        e(_e), spec(_spec), n(_n) {
1247      }
1248      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1249      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1250        switch (_n.spec) {
1251          case 0 :
1252            if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1253              e=typename Graph::OutEdgeIt(*(_G.graph),
1254                                          typename Graph::Node(_n));
1255              spec=0;
1256              n=INVALID;
1257              if (!_G.graph->valid(e)) spec=3;
1258            } else { //T, specko kiel van
1259              e=INVALID;
1260              spec=2;
1261              n=_n;
1262            }
1263            break;
1264          case 1:
1265            e=INVALID;
1266            spec=1;
1267            _G.graph->first(n, S_CLASS); //s->vmi;
1268            if (!_G.graph->valid(n)) spec=3; //Ha S ures
1269            break;
1270          case 2:
1271            e=INVALID;
1272            spec=3;
1273            n=INVALID;
1274            break;
1275        }
1276      }
1277      operator Edge() const { return Edge(e, spec, n); }
1278    };
1279
1280    class InEdgeIt {
1281      friend class GraphWrapper<Graph>;
1282      friend class stGraphWrapper<Graph>;
1283      typename Graph::InEdgeIt e;
1284      int spec;
1285      typename Graph::ClassNodeIt n;
1286    public:
1287      InEdgeIt() { }
1288      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1289               const typename Graph::ClassNodeIt& _n) :
1290        e(_e), spec(_spec), n(_n) {
1291      }
1292      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1293      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1294        switch (_n.spec) {
1295          case 0 :
1296            if (_G.graph->inTClass(_n)) { //T, van normalis beel
1297              e=typename Graph::InEdgeIt(*(_G.graph),
1298                                         typename Graph::Node(_n));
1299              spec=0;
1300              n=INVALID;
1301              if (!_G.graph->valid(e)) spec=3;
1302            } else { //S, specko beel van
1303              e=INVALID;
1304              spec=1;
1305              n=_n;
1306            }
1307            break;
1308          case 1:
1309            e=INVALID;
1310            spec=3;
1311            n=INVALID;
1312            break;
1313          case 2:
1314            e=INVALID;
1315            spec=2;
1316            _G.graph->first(n, T_CLASS); //vmi->t;
1317            if (!_G.graph->valid(n)) spec=3; //Ha T ures
1318            break;
1319        }
1320      }
1321      operator Edge() const { return Edge(e, spec, n); }
1322    };
1323
1324    class EdgeIt {
1325      friend class GraphWrapper<Graph>;
1326      friend class stGraphWrapper<Graph>;
1327      typename Graph::EdgeIt e;
1328      int spec;
1329      typename Graph::ClassNodeIt n;
1330    public:
1331      EdgeIt() { }
1332      EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1333             const typename Graph::ClassNodeIt& _n) :
1334        e(_e), spec(_spec), n(_n) { }
1335      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1336      EdgeIt(const stGraphWrapper<Graph>& _G) :
1337        e(*(_G.graph)), spec(0), n(INVALID) {
1338        if (!_G.graph->valid(e)) {
1339          spec=1;
1340          _G.graph->first(n, S_CLASS);
1341          if (!_G.graph->valid(n)) { //Ha S ures
1342            spec=2;
1343            _G.graph->first(n, T_CLASS);
1344            if (!_G.graph->valid(n)) { //Ha T ures
1345              spec=3;
1346            }
1347          }
1348        }
1349      }
1350      operator Edge() const { return Edge(e, spec, n); }
1351    };
1352
1353    NodeIt& first(NodeIt& i) const {
1354      i=NodeIt(*this); return i;
1355    }
1356    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1357      i=OutEdgeIt(*this, p); return i;
1358    }
1359    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1360      i=InEdgeIt(*this, p); return i;
1361    }
1362    EdgeIt& first(EdgeIt& i) const {
1363      i=EdgeIt(*this); return i;
1364    }
1365
1366    NodeIt& next(NodeIt& i) const {
1367      switch (i.spec) {
1368        case 0:
1369          this->graph->next(i.n);
1370          if (!this->graph->valid(i.n)) {
1371            i.spec=1;
1372          }
1373          break;
1374        case 1:
1375          i.spec=2;
1376          break;
1377        case 2:
1378          i.spec=3;
1379          break;
1380      }
1381      return i;
1382    }
1383    OutEdgeIt& next(OutEdgeIt& i) const {
1384      typename Graph::Node v;
1385      switch (i.spec) {
1386        case 0: //normal edge
1387          v=this->graph->aNode(i.e);
1388          this->graph->next(i.e);
1389          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1390            if (this->graph->inSClass(v)) { //S, nincs kiel
1391              i.spec=3;
1392              i.n=INVALID;
1393            } else { //T, van kiel
1394              i.spec=2;
1395              i.n=v;
1396            }
1397          }
1398          break;
1399        case 1: //s->vmi
1400          this->graph->next(i.n);
1401          if (!this->graph->valid(i.n)) i.spec=3;
1402          break;
1403        case 2: //vmi->t
1404          i.spec=3;
1405          i.n=INVALID;
1406          break;
1407      }
1408      return i;
1409    }
1410    InEdgeIt& next(InEdgeIt& i) const {
1411      typename Graph::Node v;
1412      switch (i.spec) {
1413        case 0: //normal edge
1414          v=this->graph->aNode(i.e);
1415          this->graph->next(i.e);
1416          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1417            if (this->graph->inTClass(v)) { //S, nincs beel
1418              i.spec=3;
1419              i.n=INVALID;
1420            } else { //S, van beel
1421              i.spec=1;
1422              i.n=v;
1423            }
1424          }
1425          break;
1426        case 1: //s->vmi
1427          i.spec=3;
1428          i.n=INVALID;
1429          break;
1430        case 2: //vmi->t
1431          this->graph->next(i.n);
1432          if (!this->graph->valid(i.n)) i.spec=3;
1433          break;
1434      }
1435      return i;
1436    }
1437
1438    EdgeIt& next(EdgeIt& i) const {
1439      switch (i.spec) {
1440        case 0:
1441          this->graph->next(i.e);
1442          if (!this->graph->valid(i.e)) {
1443            i.spec=1;
1444            this->graph->first(i.n, S_CLASS);
1445            if (!this->graph->valid(i.n)) {
1446              i.spec=2;
1447              this->graph->first(i.n, T_CLASS);
1448              if (!this->graph->valid(i.n)) i.spec=3;
1449            }
1450          }
1451          break;
1452        case 1:
1453          this->graph->next(i.n);
1454          if (!this->graph->valid(i.n)) {
1455            i.spec=2;
1456            this->graph->first(i.n, T_CLASS);
1457            if (!this->graph->valid(i.n)) i.spec=3;
1458          }
1459          break;
1460        case 2:
1461          this->graph->next(i.n);
1462          if (!this->graph->valid(i.n)) i.spec=3;
1463          break;
1464      }
1465      return i;
1466    }
1467
1468    Node tail(const Edge& e) const {
1469      switch (e.spec) {
1470      case 0:
1471        return Node(this->graph->tail(e));
1472        break;
1473      case 1:
1474        return S_NODE;
1475        break;
1476      case 2:
1477      default:
1478        return Node(e.n);
1479        break;
1480      }
1481    }
1482    Node head(const Edge& e) const {
1483      switch (e.spec) {
1484      case 0:
1486        break;
1487      case 1:
1488        return Node(e.n);
1489        break;
1490      case 2:
1491      default:
1492        return T_NODE;
1493        break;
1494      }
1495    }
1496
1497    bool valid(const Node& n) const { return (n.spec<3); }
1498    bool valid(const Edge& e) const { return (e.spec<3); }
1499
1500    int nodeNum() const { return this->graph->nodeNum()+2; }
1501    int edgeNum() const {
1502      return this->graph->edgeNum()+this->graph->nodeNum();
1503    }
1504
1505    Node aNode(const OutEdgeIt& e) const { return tail(e); }
1506    Node aNode(const InEdgeIt& e) const { return head(e); }
1507    Node bNode(const OutEdgeIt& e) const { return head(e); }
1508    Node bNode(const InEdgeIt& e) const { return tail(e); }
1509
1510    void addNode() const { }
1511    void addEdge() const { }
1512
1516
1517//    void erase(const Node& i) const { this->graph->erase(i); }
1518//    void erase(const Edge& i) const { this->graph->erase(i); }
1519
1520//    void clear() const { this->graph->clear(); }
1521
1522    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
1523      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
1524      T s_value, t_value;
1525    public:
1526      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G),
1527                                                  s_value(),
1528                                                  t_value() { }
1529      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1530                                                      s_value(a),
1531                                                      t_value(a) { }
1532      T operator[](const Node& n) const {
1533        switch (n.spec) {
1534        case 0:
1535          return Parent::operator[](n);
1536          break;
1537        case 1:
1538          return s_value;
1539          break;
1540        case 2:
1541        default:
1542          return t_value;
1543          break;
1544        }
1545      }
1546      void set(const Node& n, T t) {
1547        switch (n.spec) {
1548        case 0:
1549          GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
1550          break;
1551        case 1:
1552          s_value=t;
1553          break;
1554        case 2:
1555        default:
1556          t_value=t;
1557          break;
1558        }
1559      }
1560    };
1561
1562    template<typename T,
1563             typename Parent=
1564             typename GraphWrapper<Graph>::template EdgeMap<T> >
1565    class EdgeMap : public Parent {
1566      //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1567      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1568    public:
1569      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1570                                                 node_value(_G) { }
1571      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1572                                                      node_value(_G, a) { }
1573      T operator[](const Edge& e) const {
1574        switch (e.spec) {
1575        case 0:
1576          return Parent::operator[](e);
1577          break;
1578        case 1:
1579          return node_value[e.n];
1580          break;
1581        case 2:
1582        default:
1583          return node_value[e.n];
1584          break;
1585        }
1586      }
1587      void set(const Edge& e, T t) {
1588        switch (e.spec) {
1589        case 0:
1590          Parent::set(e, t);
1591          break;
1592        case 1:
1593          node_value.set(e.n, t);
1594          break;
1595        case 2:
1596        default:
1597          node_value.set(e.n, t);
1598          break;
1599        }
1600      }
1601    };
1602
1603//     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
1604//       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1605//       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1606//     public:
1607//       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1608//                                               node_value(_G) { }
1609//       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1610//                                                    node_value(_G, a) { }
1611//       T operator[](const Edge& e) const {
1612//      switch (e.spec) {
1613//      case 0:
1614//        return Parent::operator[](e);
1615//        break;
1616//      case 1:
1617//        return node_value[e.n];
1618//        break;
1619//      case 2:
1620//      default:
1621//        return node_value[e.n];
1622//        break;
1623//      }
1624//       }
1625//       void set(const Edge& e, T t) {
1626//      switch (e.spec) {
1627//      case 0:
1628//        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
1629//        break;
1630//      case 1:
1631//        node_value.set(e.n, t);
1632//        break;
1633//      case 2:
1634//      default:
1635//        node_value.set(e.n, t);
1636//        break;
1637//      }
1638//       }
1639//     };
1640
1641//  template<typename G>
1642    friend std::ostream&
1643    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
1644      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1645      return os;
1646    }
1647//  template<typename G>
1648    friend std::ostream&
1649    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
1650      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
1651        " node: " << i.n << ")";
1652      return os;
1653    }
1654
1655  };
1656
1657  ///@}
1658
1659} //namespace hugo
1660
1661
1662#endif //HUGO_GRAPH_WRAPPER_H
1663
Note: See TracBrowser for help on using the repository browser.