COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 873:f3a30fda2e49

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