COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 844:9bf990cb066d

Last change on this file since 844:9bf990cb066d was 844:9bf990cb066d, checked in by Balazs Dezso, 17 years ago

Bug fix in the symmetric maps.
Faster map initialization.
Iterators and Containers STL compatible.

File size: 49.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    };
233
234    template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
235      typedef typename Graph::template EdgeMap<T> Parent;
236    public:
237      EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
238      EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
239    };
240  };
241
242
243
244  /// A graph wrapper which reverses the orientation of the edges.
245
246  /// A graph wrapper which reverses the orientation of the edges.
247  /// Thus \c Graph have to be a directed graph type.
248  ///
249  ///\author Marton Makai
250  template<typename Graph>
251  class RevGraphWrapper : public GraphWrapper<Graph> {
252  public:
253    typedef GraphWrapper<Graph> Parent;
254  protected:
255    RevGraphWrapper() : GraphWrapper<Graph>() { }
256  public:
257    RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
258    RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
259
260    typedef typename GraphWrapper<Graph>::Node Node;
261    typedef typename GraphWrapper<Graph>::Edge Edge;
262    //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
263    //because this does not work is some of them are not defined in the
264    //original graph. The problem with this is that typedef-ed stuff
265    //are instantiated in c++.
266    class OutEdgeIt : public Edge {
267      const RevGraphWrapper<Graph>* gw;
268      friend class GraphWrapper<Graph>;
269     public:
270      OutEdgeIt() { }
271      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
272      OutEdgeIt(Invalid i) : Edge(i) { }
273      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
274        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
275      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
276        Edge(e), gw(&_gw) { }
277      OutEdgeIt& operator++() {
278        *(static_cast<Edge*>(this))=
279          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
280        return *this;
281      }
282    };
283    class InEdgeIt : public Edge {
284      const RevGraphWrapper<Graph>* gw;
285      friend class GraphWrapper<Graph>;
286     public:
287      InEdgeIt() { }
288      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
289      InEdgeIt(Invalid i) : Edge(i) { }
290      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
291        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
292      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
293        Edge(e), gw(&_gw) { }
294      InEdgeIt& operator++() {
295        *(static_cast<Edge*>(this))=
296          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
297        return *this;
298      }
299    };
300
301    using GraphWrapper<Graph>::first;
302    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
303      i=OutEdgeIt(*this, p); return i;
304    }
305    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
306      i=InEdgeIt(*this, p); return i;
307    }
308
309//     using GraphWrapper<Graph>::next;
310//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
311//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
312
313//     Node aNode(const OutEdgeIt& e) const {
314//       return Node(this->graph->aNode(e.e)); }
315//     Node aNode(const InEdgeIt& e) const {
316//       return Node(this->graph->aNode(e.e)); }
317//     Node bNode(const OutEdgeIt& e) const {
318//       return Node(this->graph->bNode(e.e)); }
319//     Node bNode(const InEdgeIt& e) const {
320//       return Node(this->graph->bNode(e.e)); }
321
322    Node tail(const Edge& e) const {
323      return GraphWrapper<Graph>::head(e); }
324    Node head(const Edge& e) const {
325      return GraphWrapper<Graph>::tail(e); }
326
327  };
328
329
330
331  /// A graph wrapper for hiding nodes and edges from a graph.
332 
333  /// This wrapper shows a graph with filtered node-set and
334  /// edge-set. Given a bool-valued map on the node-set and one on
335  /// the edge-set of the graphs, the iterators shows only the objects
336  /// having true value.
337  /// The quick brown fox iterators jump over
338  /// the lazy dog nodes or edges if their values for are false in the
339  /// corresponding bool maps.
340  ///
341  ///\author Marton Makai
342  template<typename Graph, typename NodeFilterMap,
343           typename EdgeFilterMap>
344  class SubGraphWrapper : public GraphWrapper<Graph> {
345  public:
346    typedef GraphWrapper<Graph> Parent;
347  protected:
348    NodeFilterMap* node_filter_map;
349    EdgeFilterMap* edge_filter_map;
350
351    SubGraphWrapper() : GraphWrapper<Graph>(),
352                        node_filter_map(0), edge_filter_map(0) { }
353    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
354      node_filter_map=&_node_filter_map;
355    }
356    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
357      edge_filter_map=&_edge_filter_map;
358    }
359   
360  public:
361    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
362                    EdgeFilterMap& _edge_filter_map) :
363      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
364      edge_filter_map(&_edge_filter_map) { } 
365
366    typedef typename GraphWrapper<Graph>::Node Node;
367    class NodeIt : public Node {
368      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
369      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
370    public:
371      NodeIt() { }
372      //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
373      NodeIt(Invalid i) : Node(i) { }
374      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
375        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
376      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
377             const Node& n) :
378        Node(n), gw(&_gw) { }
379      NodeIt& operator++() {
380        *(static_cast<Node*>(this))=
381          ++(typename Graph::NodeIt(*(gw->graph), *this));
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        return *this;
387      }
388    };
389    typedef typename GraphWrapper<Graph>::Edge Edge;
390    class OutEdgeIt : public Edge {
391      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
392      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
393    public:
394      OutEdgeIt() { }
395      //      OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
396      OutEdgeIt(Invalid i) : Edge(i) { }
397      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
398        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
399      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
400             const Edge& e) :
401        Edge(e), gw(&_gw) { }
402      OutEdgeIt& operator++() {
403        *(static_cast<Edge*>(this))=
404          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
405        while (*static_cast<Edge*>(this)!=INVALID &&
406               !(*(gw->edge_filter_map))[*this])
407          *(static_cast<Edge*>(this))=
408            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
409        return *this;
410      }
411    };
412    class InEdgeIt : public Edge {
413      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
414      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
415    public:
416      InEdgeIt() { }
417      //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
418      InEdgeIt(Invalid i) : Edge(i) { }
419      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
420        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
421      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
422             const Edge& e) :
423        Edge(e), gw(&_gw) { }
424      InEdgeIt& operator++() {
425        *(static_cast<Edge*>(this))=
426          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
427        while (*static_cast<Edge*>(this)!=INVALID &&
428               !(*(gw->edge_filter_map))[*this])
429          *(static_cast<Edge*>(this))=
430            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
431        return *this;
432      }
433    };
434    class EdgeIt : public Edge {
435      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
436      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
437    public:
438      EdgeIt() { }
439      //      EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
440      EdgeIt(Invalid i) : Edge(i) { }
441      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
442        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
443      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
444             const Edge& e) :
445        Edge(e), gw(&_gw) { }
446      EdgeIt& operator++() {
447        *(static_cast<Edge*>(this))=
448          ++(typename Graph::EdgeIt(*(gw->graph), *this));
449        while (*static_cast<Edge*>(this)!=INVALID &&
450               !(*(gw->edge_filter_map))[*this])
451          *(static_cast<Edge*>(this))=
452            ++(typename Graph::EdgeIt(*(gw->graph), *this));
453        return *this;
454      }
455    };
456
457    NodeIt& first(NodeIt& i) const {
458      i=NodeIt(*this); return i;
459    }
460    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
461      i=OutEdgeIt(*this, p); return i;
462    }
463    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
464      i=InEdgeIt(*this, p); return i;
465    }
466    EdgeIt& first(EdgeIt& i) const {
467      i=EdgeIt(*this); return i;
468    }
469   
470//     NodeIt& next(NodeIt& i) const {
471//       this->graph->next(i.n);
472//       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
473//      this->graph->next(i.n); }
474//       return i;
475//     }
476//     OutEdgeIt& next(OutEdgeIt& i) const {
477//       this->graph->next(i.e);
478//       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
479//      this->graph->next(i.e); }
480//       return i;
481//     }
482//     InEdgeIt& next(InEdgeIt& i) const {
483//       this->graph->next(i.e);
484//       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
485//      this->graph->next(i.e); }
486//       return i;
487//     }
488//     EdgeIt& next(EdgeIt& i) const {
489//       this->graph->next(i.e);
490//       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
491//      this->graph->next(i.e); }
492//       return i;
493//     }
494
495//     Node aNode(const OutEdgeIt& e) const {
496//       return Node(this->graph->aNode(e.e)); }
497//     Node aNode(const InEdgeIt& e) const {
498//       return Node(this->graph->aNode(e.e)); }
499//     Node bNode(const OutEdgeIt& e) const {
500//       return Node(this->graph->bNode(e.e)); }
501//     Node bNode(const InEdgeIt& e) const {
502//       return Node(this->graph->bNode(e.e)); }
503
504    /// This function hides \c n in the graph, i.e. the iteration
505    /// jumps over it. This is done by simply setting the value of \c n 
506    /// to be false in the corresponding node-map.
507    void hide(const Node& n) const { node_filter_map->set(n, false); }
508
509    /// This function hides \c e in the graph, i.e. the iteration
510    /// jumps over it. This is done by simply setting the value of \c e 
511    /// to be false in the corresponding edge-map.
512    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
513
514    /// The value of \c n is set to be true in the node-map which stores
515    /// hide information. If \c n was hidden previuosly, then it is shown
516    /// again
517     void unHide(const Node& n) const { node_filter_map->set(n, true); }
518
519    /// The value of \c e is set to be true in the edge-map which stores
520    /// hide information. If \c e was hidden previuosly, then it is shown
521    /// again
522    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
523
524    /// Returns true if \c n is hidden.
525    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
526
527    /// Returns true if \c n is hidden.
528    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
529
530    /// \warning This is a linear time operation and works only if
531    /// \c Graph::NodeIt is defined.
532    int nodeNum() const {
533      int i=0;
534      for (NodeIt n(*this); n!=INVALID; ++n) ++i;
535      return i;
536    }
537
538    /// \warning This is a linear time operation and works only if
539    /// \c Graph::EdgeIt is defined.
540    int edgeNum() const {
541      int i=0;
542      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
543      return i;
544    }
545
546  };
547
548
549
550//   /// \brief A wrapper for forgetting the orientation of a graph.
551//   ///
552//   /// A wrapper for getting an undirected graph by forgetting
553//   /// the orientation of a directed one.
554//   ///
555//   /// \author Marton Makai
556//   /// does not work in the new concept.
557  template<typename Graph>
558  class UndirGraphWrapper : public GraphWrapper<Graph> {
559  public:
560    typedef GraphWrapper<Graph> Parent;
561  protected:
562    UndirGraphWrapper() : GraphWrapper<Graph>() { }
563   
564  public:
565    typedef typename GraphWrapper<Graph>::Node Node;
566    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
567    typedef typename GraphWrapper<Graph>::Edge Edge;
568    typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
569
570    UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
571
572    class OutEdgeIt {
573      friend class UndirGraphWrapper<Graph>;
574      bool out_or_in; //true iff out
575      typename Graph::OutEdgeIt out;
576      typename Graph::InEdgeIt in;
577    public:
578      OutEdgeIt() { }
579      OutEdgeIt(const Invalid& i) : Edge(i) { }
580      OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
581        out_or_in=true; _G.graph->first(out, _n);
582        if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
583      }
584      operator Edge() const {
585        if (out_or_in) return Edge(out); else return Edge(in);
586      }
587    };
588
589//FIXME InEdgeIt
590    typedef OutEdgeIt InEdgeIt;
591
592    using GraphWrapper<Graph>::first;
593//     NodeIt& first(NodeIt& i) const {
594//       i=NodeIt(*this); return i;
595//     }
596    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
597      i=OutEdgeIt(*this, p); return i;
598    }
599//FIXME
600//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
601//       i=InEdgeIt(*this, p); return i;
602//     }
603//     EdgeIt& first(EdgeIt& i) const {
604//       i=EdgeIt(*this); return i;
605//     }
606
607    using GraphWrapper<Graph>::next;
608//     NodeIt& next(NodeIt& n) const {
609//       GraphWrapper<Graph>::next(n);
610//       return n;
611//     }
612    OutEdgeIt& next(OutEdgeIt& e) const {
613      if (e.out_or_in) {
614        typename Graph::Node n=this->graph->tail(e.out);
615        this->graph->next(e.out);
616        if (!this->graph->valid(e.out)) {
617          e.out_or_in=false; this->graph->first(e.in, n); }
618      } else {
619        this->graph->next(e.in);
620      }
621      return e;
622    }
623    //FIXME InEdgeIt
624//     EdgeIt& next(EdgeIt& e) const {
625//       GraphWrapper<Graph>::next(n);
626// //      graph->next(e.e);
627//       return e;
628//     }
629
630    Node aNode(const OutEdgeIt& e) const {
631      if (e.out_or_in) return this->graph->tail(e); else
632        return this->graph->head(e); }
633    Node bNode(const OutEdgeIt& e) const {
634      if (e.out_or_in) return this->graph->head(e); else
635        return this->graph->tail(e); }
636  };
637 
638  /// \brief An undirected graph template.
639  ///
640  /// An undirected graph template.
641  /// This class works as an undirected graph and a directed graph of
642  /// class \c Graph is used for the physical storage.
643  /// \ingroup graphs
644  template<typename Graph>
645  class UndirGraph : public UndirGraphWrapper<Graph> {
646    typedef UndirGraphWrapper<Graph> Parent;
647  protected:
648    Graph gr;
649  public:
650    UndirGraph() : UndirGraphWrapper<Graph>() {
651      Parent::setGraph(gr);
652    }
653  };
654
655
656
657  ///\brief A wrapper for composing a subgraph of a
658  /// bidirected graph made from a directed one.
659  ///
660  /// Suppose that for a directed graph $G=(V, A)$,
661  /// two predicates on the edge-set, $forward_filter$, and $backward_filter$
662  /// is given, and we are dealing with the directed graph
663  /// 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}\})$.
664  /// The purpose of writing + instead of union is because parallel
665  /// edges can arose.
666  /// In other words, a subgraph of the bidirected graph obtained, which
667  /// is given by orienting the edges of the original graph in both directions.
668  /// An example for such a construction is the \c RevGraphWrapper where the
669  /// forward_filter is everywhere false and the backward_filter is
670  /// everywhere true. We note that for sake of efficiency,
671  /// \c RevGraphWrapper is implemented in a different way.
672  /// But BidirGraphWrapper is obtained from
673  /// SubBidirGraphWrapper by considering everywhere true
674  /// predicates both forward_filter and backward_filter.
675  /// Finally, one of the most important applications of SubBidirGraphWrapper
676  /// is ResGraphWrapper, which stands for the residual graph in directed
677  /// flow and circulation problems.
678  /// As wrappers usually, the SubBidirGraphWrapper implements the
679  /// above mentioned graph structure without its physical storage,
680  /// that is the whole stuff eats constant memory.
681  /// As the oppositely directed edges are logical different,
682  /// the maps are able to attach different values for them.
683  template<typename Graph,
684           typename ForwardFilterMap, typename BackwardFilterMap>
685  class SubBidirGraphWrapper : public GraphWrapper<Graph> {
686  public:
687    typedef GraphWrapper<Graph> Parent;
688  protected:
689    ForwardFilterMap* forward_filter;
690    BackwardFilterMap* backward_filter;
691
692    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
693    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
694      forward_filter=&_forward_filter;
695    }
696    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
697      backward_filter=&_backward_filter;
698    }
699
700  public:
701
702    SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
703                         BackwardFilterMap& _backward_filter) :
704      GraphWrapper<Graph>(_graph),
705      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
706    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
707                         ForwardFilterMap, BackwardFilterMap>& gw) :
708      Parent(gw),
709      forward_filter(gw.forward_filter),
710      backward_filter(gw.backward_filter) { }
711
712    class Edge;
713    class OutEdgeIt;
714    friend class Edge;
715    friend class OutEdgeIt;
716
717    template<typename T> class EdgeMap;
718
719    typedef typename GraphWrapper<Graph>::Node Node;
720
721    typedef typename Graph::Edge GraphEdge;
722    /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
723    /// Graph::Edge. It contains an extra bool flag which shows if the
724    /// edge is the backward version of the original edge.
725    class Edge : public Graph::Edge {
726      friend class SubBidirGraphWrapper<Graph,
727                                        ForwardFilterMap, BackwardFilterMap>;
728      template<typename T> friend class EdgeMap;
729    protected:
730      bool backward; //true, iff backward
731    public:
732      Edge() { }
733      /// \todo =false is needed, or causes problems?
734      /// If \c _backward is false, then we get an edge corresponding to the
735      /// original one, otherwise its oppositely directed pair is obtained.
736      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
737        Graph::Edge(e), backward(_backward) { }
738      Edge(Invalid i) : Graph::Edge(i), backward(true) { }
739//the unique invalid iterator
740//       friend bool operator==(const Edge& u, const Edge& v) {
741//      return (u.backward==v.backward &&
742//              static_cast<typename Graph::Edge>(u)==
743//              static_cast<typename Graph::Edge>(v));
744//       }
745//       friend bool operator!=(const Edge& u, const Edge& v) {
746//      return (u.backward!=v.backward ||
747//              static_cast<typename Graph::Edge>(u)!=
748//              static_cast<typename Graph::Edge>(v));
749//       }
750      bool operator==(const Edge& v) const {
751        return (this->backward==v.backward &&
752                static_cast<typename Graph::Edge>(*this)==
753                static_cast<typename Graph::Edge>(v));
754      }
755      bool operator!=(const Edge& v) const {
756        return (this->backward!=v.backward ||
757                static_cast<typename Graph::Edge>(*this)!=
758                static_cast<typename Graph::Edge>(v));
759      }
760    };
761
762    class OutEdgeIt : public Edge {
763      friend class SubBidirGraphWrapper<Graph,
764                                        ForwardFilterMap, BackwardFilterMap>;
765    protected:
766      const SubBidirGraphWrapper<Graph,
767                                 ForwardFilterMap, BackwardFilterMap>* gw;
768    public:
769      OutEdgeIt() { }
770      OutEdgeIt(Invalid i) : Edge(i) { }
771//the unique invalid iterator
772      OutEdgeIt(const SubBidirGraphWrapper<Graph,
773                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
774        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
775        while (*static_cast<GraphEdge*>(this)!=INVALID &&
776               !(*(gw->forward_filter))[*this])
777          *(static_cast<GraphEdge*>(this))=
778            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
779        if (*static_cast<GraphEdge*>(this)==INVALID) {
780          *static_cast<Edge*>(this)=
781            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
782          while (*static_cast<GraphEdge*>(this)!=INVALID &&
783                 !(*(gw->backward_filter))[*this])
784            *(static_cast<GraphEdge*>(this))=
785              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
786        }
787      }
788      OutEdgeIt(const SubBidirGraphWrapper<Graph,
789                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
790        Edge(e), gw(&_gw) { }
791      OutEdgeIt& operator++() {
792        if (!this->backward) {
793          Node n=gw->tail(*this);
794          *(static_cast<GraphEdge*>(this))=
795            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
796          while (*static_cast<GraphEdge*>(this)!=INVALID &&
797                 !(*(gw->forward_filter))[*this])
798            *(static_cast<GraphEdge*>(this))=
799              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
800          if (*static_cast<GraphEdge*>(this)==INVALID) {
801            *static_cast<Edge*>(this)=
802              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
803            while (*static_cast<GraphEdge*>(this)!=INVALID &&
804                   !(*(gw->backward_filter))[*this])
805              *(static_cast<GraphEdge*>(this))=
806                ++(typename Graph::InEdgeIt(*(gw->graph), *this));
807          }
808        } else {
809          *(static_cast<GraphEdge*>(this))=
810            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
811          while (*static_cast<GraphEdge*>(this)!=INVALID &&
812                 !(*(gw->backward_filter))[*this])
813            *(static_cast<GraphEdge*>(this))=
814              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
815        }
816        return *this;
817      }
818    };
819
820    class InEdgeIt : public Edge {
821      friend class SubBidirGraphWrapper<Graph,
822                                        ForwardFilterMap, BackwardFilterMap>;
823    protected:
824      const SubBidirGraphWrapper<Graph,
825                                 ForwardFilterMap, BackwardFilterMap>* gw;
826    public:
827      InEdgeIt() { }
828      InEdgeIt(Invalid i) : Edge(i) { }
829//the unique invalid iterator
830      InEdgeIt(const SubBidirGraphWrapper<Graph,
831               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
832        Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
833        while (*static_cast<GraphEdge*>(this)!=INVALID &&
834               !(*(gw->forward_filter))[*this])
835          *(static_cast<GraphEdge*>(this))=
836            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
837        if (*static_cast<GraphEdge*>(this)==INVALID) {
838          *static_cast<Edge*>(this)=
839            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
840          while (*static_cast<GraphEdge*>(this)!=INVALID &&
841                 !(*(gw->backward_filter))[*this])
842            *(static_cast<GraphEdge*>(this))=
843              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
844        }
845      }
846      InEdgeIt(const SubBidirGraphWrapper<Graph,
847               ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
848        Edge(e), gw(&_gw) { }
849      InEdgeIt& operator++() {
850        if (!this->backward) {
851          Node n=gw->tail(*this);
852          *(static_cast<GraphEdge*>(this))=
853            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
854          while (*static_cast<GraphEdge*>(this)!=INVALID &&
855                 !(*(gw->forward_filter))[*this])
856            *(static_cast<GraphEdge*>(this))=
857              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
858          if (*static_cast<GraphEdge*>(this)==INVALID) {
859            *static_cast<Edge*>(this)=
860              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
861            while (*static_cast<GraphEdge*>(this)!=INVALID &&
862                   !(*(gw->backward_filter))[*this])
863              *(static_cast<GraphEdge*>(this))=
864                ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
865          }
866        } else {
867          *(static_cast<GraphEdge*>(this))=
868            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
869          while (*static_cast<GraphEdge*>(this)!=INVALID &&
870                 !(*(gw->backward_filter))[*this])
871            *(static_cast<GraphEdge*>(this))=
872              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
873        }
874        return *this;
875      }
876    };
877
878    class EdgeIt : public Edge {
879      friend class SubBidirGraphWrapper<Graph,
880                                        ForwardFilterMap, BackwardFilterMap>;
881    protected:
882      const SubBidirGraphWrapper<Graph,
883                                 ForwardFilterMap, BackwardFilterMap>* gw;
884    public:
885      EdgeIt() { }
886      EdgeIt(Invalid i) : Edge(i) { }
887//the unique invalid iterator
888      EdgeIt(const SubBidirGraphWrapper<Graph,
889             ForwardFilterMap, BackwardFilterMap>& _gw) :
890        Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) {
891        while (*static_cast<GraphEdge*>(this)!=INVALID &&
892               !(*(gw->forward_filter))[*this])
893          *(static_cast<GraphEdge*>(this))=
894            ++(typename Graph::EdgeIt(*(gw->graph), *this));
895        if (*static_cast<GraphEdge*>(this)==INVALID) {
896          *static_cast<Edge*>(this)=
897            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
898          while (*static_cast<GraphEdge*>(this)!=INVALID &&
899                 !(*(gw->backward_filter))[*this])
900            *(static_cast<GraphEdge*>(this))=
901              ++(typename Graph::EdgeIt(*(gw->graph), *this));
902        }
903      }
904      EdgeIt(const SubBidirGraphWrapper<Graph,
905             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
906        Edge(e), gw(&_gw) { }
907      EdgeIt& operator++() {
908        if (!this->backward) {
909          *(static_cast<GraphEdge*>(this))=
910            ++(typename Graph::EdgeIt(*(gw->graph), *this));
911          while (*static_cast<GraphEdge*>(this)!=INVALID &&
912                 !(*(gw->forward_filter))[*this])
913            *(static_cast<GraphEdge*>(this))=
914              ++(typename Graph::EdgeIt(*(gw->graph), *this));
915          if (*static_cast<GraphEdge*>(this)==INVALID) {
916            *static_cast<Edge*>(this)=
917              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
918            while (*static_cast<GraphEdge*>(this)!=INVALID &&
919                   !(*(gw->backward_filter))[*this])
920              *(static_cast<GraphEdge*>(this))=
921                ++(typename Graph::EdgeIt(*(gw->graph), *this));
922          }
923        } else {
924          *(static_cast<GraphEdge*>(this))=
925            ++(typename Graph::EdgeIt(*(gw->graph), *this));
926          while (*static_cast<GraphEdge*>(this)!=INVALID &&
927                 !(*(gw->backward_filter))[*this])
928            *(static_cast<GraphEdge*>(this))=
929              ++(typename Graph::EdgeIt(*(gw->graph), *this));
930        }
931        return *this;
932      }
933    };
934
935    using GraphWrapper<Graph>::first;
936//     NodeIt& first(NodeIt& i) const {
937//       i=NodeIt(*this); return i;
938//     }
939    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
940      i=OutEdgeIt(*this, p); return i;
941    }
942    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
943      i=InEdgeIt(*this, p); return i;
944    }
945    EdgeIt& first(EdgeIt& i) const {
946      i=EdgeIt(*this); return i;
947    }
948 
949//     using GraphWrapper<Graph>::next;
950// //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
951//     OutEdgeIt& next(OutEdgeIt& e) const {
952//       if (!e.backward) {
953//      Node v=this->graph->aNode(e.out);
954//      this->graph->next(e.out);
955//      while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
956//        this->graph->next(e.out); }
957//      if (!this->graph->valid(e.out)) {
958//        e.backward=true;
959//        this->graph->first(e.in, v);
960//        while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
961//          this->graph->next(e.in); }
962//      }
963//       } else {
964//      this->graph->next(e.in);
965//      while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
966//        this->graph->next(e.in); }
967//       }
968//       return e;
969//     }
970// //     FIXME Not tested
971//     InEdgeIt& next(InEdgeIt& e) const {
972//       if (!e.backward) {
973//      Node v=this->graph->aNode(e.in);
974//      this->graph->next(e.in);
975//      while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
976//        this->graph->next(e.in); }
977//      if (!this->graph->valid(e.in)) {
978//        e.backward=true;
979//        this->graph->first(e.out, v);
980//        while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
981//          this->graph->next(e.out); }
982//      }
983//       } else {
984//      this->graph->next(e.out);
985//      while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
986//        this->graph->next(e.out); }
987//       }
988//       return e;
989//     }
990//     EdgeIt& next(EdgeIt& e) const {
991//       if (!e.backward) {
992//      this->graph->next(e.e);
993//      while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
994//        this->graph->next(e.e); }
995//      if (!this->graph->valid(e.e)) {
996//        e.backward=true;
997//        this->graph->first(e.e);
998//        while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
999//          this->graph->next(e.e); }
1000//      }
1001//       } else {
1002//      this->graph->next(e.e);
1003//      while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
1004//        this->graph->next(e.e); }
1005//       }
1006//       return e;
1007//     }
1008
1009    Node tail(Edge e) const {
1010      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1011    Node head(Edge e) const {
1012      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1013
1014//     Node aNode(OutEdgeIt e) const {
1015//       return ((!e.backward) ? this->graph->aNode(e.out) :
1016//            this->graph->aNode(e.in)); }
1017//     Node bNode(OutEdgeIt e) const {
1018//       return ((!e.backward) ? this->graph->bNode(e.out) :
1019//            this->graph->bNode(e.in)); }
1020
1021//     Node aNode(InEdgeIt e) const {
1022//       return ((!e.backward) ? this->graph->aNode(e.in) :
1023//            this->graph->aNode(e.out)); }
1024//     Node bNode(InEdgeIt e) const {
1025//       return ((!e.backward) ? this->graph->bNode(e.in) :
1026//            this->graph->bNode(e.out)); }
1027
1028    /// Gives back the opposite edge.
1029    Edge opposite(const Edge& e) const {
1030      Edge f=e;
1031      f.backward=!f.backward;
1032      return f;
1033    }
1034
1035    /// \warning This is a linear time operation and works only if
1036    /// \c Graph::EdgeIt is defined.
1037    int edgeNum() const {
1038      int i=0;
1039      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
1040      return i;
1041    }
1042
1043    bool forward(const Edge& e) const { return !e.backward; }
1044    bool backward(const Edge& e) const { return e.backward; }
1045
1046
1047    template <typename T>
1048    /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
1049    /// Graph::EdgeMap one for the forward edges and
1050    /// one for the backward edges.
1051    class EdgeMap {
1052      typename Graph::template EdgeMap<T> forward_map, backward_map;
1053    public:
1054      typedef T ValueType;
1055      typedef Edge KeyType;
1056      EdgeMap(const SubBidirGraphWrapper<Graph,
1057              ForwardFilterMap, BackwardFilterMap>& g) :
1058        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1059      EdgeMap(const SubBidirGraphWrapper<Graph,
1060              ForwardFilterMap, BackwardFilterMap>& g, T a) :
1061        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1062      void set(Edge e, T a) {
1063        if (!e.backward)
1064          forward_map.set(e, a);
1065        else
1066          backward_map.set(e, a);
1067      }
1068      T operator[](Edge e) const {
1069        if (!e.backward)
1070          return forward_map[e];
1071        else
1072          return backward_map[e];
1073      }
1074      void update() {
1075        forward_map.update();
1076        backward_map.update();
1077      }
1078//       T get(Edge e) const {
1079//      if (e.out_or_in)
1080//        return forward_map.get(e.out);
1081//      else
1082//        return backward_map.get(e.in);
1083//       }
1084    };
1085  };
1086
1087
1088  ///\brief A wrapper for composing bidirected graph from a directed one.
1089  ///
1090  /// A wrapper for composing bidirected graph from a directed one.
1091  /// A bidirected graph is composed over the directed one without physical
1092  /// storage. As the oppositely directed edges are logically different ones
1093  /// the maps are able to attach different values for them.
1094  template<typename Graph>
1095  class BidirGraphWrapper :
1096    public SubBidirGraphWrapper<
1097    Graph,
1098    ConstMap<typename Graph::Edge, bool>,
1099    ConstMap<typename Graph::Edge, bool> > {
1100  public:
1101    typedef  SubBidirGraphWrapper<
1102      Graph,
1103      ConstMap<typename Graph::Edge, bool>,
1104      ConstMap<typename Graph::Edge, bool> > Parent;
1105  protected:
1106    ConstMap<typename Graph::Edge, bool> cm;
1107
1108    BidirGraphWrapper() : Parent(), cm(true) {
1109      Parent::setForwardFilterMap(cm);
1110      Parent::setBackwardFilterMap(cm);
1111    }
1112  public:
1113    BidirGraphWrapper(Graph& _graph) : Parent() {
1114      Parent::setGraph(_graph);
1115      Parent::setForwardFilterMap(cm);
1116      Parent::setBackwardFilterMap(cm);
1117    }
1118
1119    int edgeNum() const {
1120      return 2*this->graph->edgeNum();
1121    }
1122  };
1123
1124
1125  /// \brief A bidirected graph template.
1126  ///
1127  /// A bidirected graph template.
1128  /// Such a bidirected graph stores each pair of oppositely directed edges
1129  /// ones in the memory, i.e. a directed graph of type
1130  /// \c Graph is used for that.
1131  /// As the oppositely directed edges are logically different ones
1132  /// the maps are able to attach different values for them.
1133  /// \ingroup graphs
1134  template<typename Graph>
1135  class BidirGraph : public BidirGraphWrapper<Graph> {
1136  public:
1137    typedef UndirGraphWrapper<Graph> Parent;
1138  protected:
1139    Graph gr;
1140  public:
1141    BidirGraph() : BidirGraphWrapper<Graph>() {
1142      Parent::setGraph(gr);
1143    }
1144  };
1145
1146
1147
1148  template<typename Graph, typename Number,
1149           typename CapacityMap, typename FlowMap>
1150  class ResForwardFilter {
1151    //    const Graph* graph;
1152    const CapacityMap* capacity;
1153    const FlowMap* flow;
1154  public:
1155    ResForwardFilter(/*const Graph& _graph, */
1156                     const CapacityMap& _capacity, const FlowMap& _flow) :
1157      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1158    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1159    //void setGraph(const Graph& _graph) { graph=&_graph; }
1160    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1161    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1162    bool operator[](const typename Graph::Edge& e) const {
1163      return (Number((*flow)[e]) < Number((*capacity)[e]));
1164    }
1165  };
1166
1167  template<typename Graph, typename Number,
1168           typename CapacityMap, typename FlowMap>
1169  class ResBackwardFilter {
1170    //const Graph* graph;
1171    const CapacityMap* capacity;
1172    const FlowMap* flow;
1173  public:
1174    ResBackwardFilter(/*const Graph& _graph,*/
1175                      const CapacityMap& _capacity, const FlowMap& _flow) :
1176      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1177    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1178    //void setGraph(const Graph& _graph) { graph=&_graph; }
1179    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1180    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1181    bool operator[](const typename Graph::Edge& e) const {
1182      return (Number(0) < Number((*flow)[e]));
1183    }
1184  };
1185
1186 
1187  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1188
1189  /// A wrapper for composing the residual graph for directed flow and circulation problems.
1190  template<typename Graph, typename Number,
1191           typename CapacityMap, typename FlowMap>
1192  class ResGraphWrapper :
1193    public SubBidirGraphWrapper<
1194    Graph,
1195    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1196    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1197  public:
1198    typedef SubBidirGraphWrapper<
1199      Graph,
1200      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1201      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1202  protected:
1203    const CapacityMap* capacity;
1204    FlowMap* flow;
1205    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1206    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1207    ResGraphWrapper() : Parent(),
1208                        capacity(0), flow(0) { }
1209    void setCapacityMap(const CapacityMap& _capacity) {
1210      capacity=&_capacity;
1211      forward_filter.setCapacity(_capacity);
1212      backward_filter.setCapacity(_capacity);
1213    }
1214    void setFlowMap(FlowMap& _flow) {
1215      flow=&_flow;
1216      forward_filter.setFlow(_flow);
1217      backward_filter.setFlow(_flow);
1218    }
1219//     /// \bug does graph reference needed in filtermaps??
1220//     void setGraph(const Graph& _graph) {
1221//       Parent::setGraph(_graph);
1222//       forward_filter.setGraph(_graph);
1223//       backward_filter.setGraph(_graph);
1224//     }
1225  public:
1226    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1227                       FlowMap& _flow) :
1228      Parent(), capacity(&_capacity), flow(&_flow),
1229      forward_filter(/*_graph,*/ _capacity, _flow),
1230      backward_filter(/*_graph,*/ _capacity, _flow) {
1231      Parent::setGraph(_graph);
1232      Parent::setForwardFilterMap(forward_filter);
1233      Parent::setBackwardFilterMap(backward_filter);
1234    }
1235
1236    typedef typename Parent::Edge Edge;
1237
1238    //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1239    //bool backward(const Edge& e) const { return e.backward; }
1240
1241    void augment(const Edge& e, Number a) const {
1242      if (Parent::forward(e)) 
1243//      flow->set(e.out, flow->get(e.out)+a);
1244        flow->set(e, (*flow)[e]+a);
1245      else 
1246        //flow->set(e.in, flow->get(e.in)-a);
1247        flow->set(e, (*flow)[e]-a);
1248    }
1249
1250    /// \deprecated
1251    ///
1252    Number resCap(const Edge& e) const {
1253      if (Parent::forward(e))
1254//      return (capacity->get(e.out)-flow->get(e.out));
1255        return ((*capacity)[e]-(*flow)[e]);
1256      else
1257//      return (flow->get(e.in));
1258        return ((*flow)[e]);
1259    }
1260
1261    /// \brief Residual capacity map.
1262    ///
1263    /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
1264    class ResCap {
1265    protected:
1266      const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1267    public:
1268      typedef Number ValueType;
1269      typedef Edge KeyType;
1270      ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) :
1271        res_graph(&_res_graph) { }
1272      Number operator[](const Edge& e) const {
1273        if (res_graph->forward(e))
1274          //    return (capacity->get(e.out)-flow->get(e.out));
1275          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1276        else
1277          //    return (flow->get(e.in));
1278          return (*(res_graph->flow))[e];
1279      }
1280      /// \bug not needed with dynamic maps, or does it?
1281      void update() { }
1282    };
1283
1284  };
1285
1286
1287  /// For blocking flows.
1288
1289  /// This graph wrapper is used for on-the-fly
1290  /// Dinits blocking flow computations.
1291  /// For each node, an out-edge is stored which is used when the
1292  /// \code
1293  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1294  /// \endcode
1295  /// is called.
1296  ///
1297  /// \author Marton Makai
1298  template<typename Graph, typename FirstOutEdgesMap>
1299  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
1300  public:
1301    typedef GraphWrapper<Graph> Parent;
1302  protected:
1303    FirstOutEdgesMap* first_out_edges;
1304  public:
1305    ErasingFirstGraphWrapper(Graph& _graph,
1306                             FirstOutEdgesMap& _first_out_edges) :
1307      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
1308
1309    typedef typename GraphWrapper<Graph>::Node Node;
1310    typedef typename GraphWrapper<Graph>::Edge Edge;
1311    class OutEdgeIt : public Edge {
1312      friend class GraphWrapper<Graph>;
1313      friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1314      const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
1315    public:
1316      OutEdgeIt() { }
1317      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
1318      OutEdgeIt(Invalid i) : Edge(i) { }
1319      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1320                const Node& n) :
1321        Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
1322      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
1323                const Edge& e) :
1324        Edge(e), gw(&_gw) { }
1325      OutEdgeIt& operator++() {
1326        *(static_cast<Edge*>(this))=
1327          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
1328        return *this;
1329      }
1330    };
1331//     class InEdgeIt {
1332//       friend class GraphWrapper<Graph>;
1333//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1334// //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
1335//       typename Graph::InEdgeIt e;
1336//     public:
1337//       InEdgeIt() { }
1338//       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
1339//       InEdgeIt(const Invalid& i) : e(i) { }
1340//       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
1341//             const Node& _n) :
1342//      e(*(_G.graph), typename Graph::Node(_n)) { }
1343//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1344//     };       
1345    //typedef typename Graph::SymEdgeIt SymEdgeIt;
1346//     class EdgeIt {
1347//       friend class GraphWrapper<Graph>;
1348//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
1349// //      typedef typename Graph::EdgeIt GraphEdgeIt;
1350//       typename Graph::EdgeIt e;
1351//     public:
1352//       EdgeIt() { }
1353//       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
1354//       EdgeIt(const Invalid& i) : e(i) { }
1355//       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
1356//      e(*(_G.graph)) { }
1357//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
1358//     };
1359
1360    using GraphWrapper<Graph>::first;
1361//     NodeIt& first(NodeIt& i) const {
1362//       i=NodeIt(*this); return i;
1363//     }
1364    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1365      i=OutEdgeIt(*this, p); return i;
1366    }
1367//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1368//       i=InEdgeIt(*this, p); return i;
1369//     }
1370//     EdgeIt& first(EdgeIt& i) const {
1371//       i=EdgeIt(*this); return i;
1372//     }
1373
1374//     using GraphWrapper<Graph>::next;
1375// //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
1376//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1377//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1378//     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
1379   
1380//     Node aNode(const OutEdgeIt& e) const {
1381//       return Node(this->graph->aNode(e.e)); }
1382//     Node aNode(const InEdgeIt& e) const {
1383//       return Node(this->graph->aNode(e.e)); }
1384//     Node bNode(const OutEdgeIt& e) const {
1385//       return Node(this->graph->bNode(e.e)); }
1386//     Node bNode(const InEdgeIt& e) const {
1387//       return Node(this->graph->bNode(e.e)); }
1388
1389    void erase(const Edge& e) const {
1390      Node n=tail(e);
1391      typename Graph::OutEdgeIt f(*Parent::graph, n);
1392      ++f;
1393      first_out_edges->set(n, f);
1394    }
1395  };
1396
1397  ///@}
1398
1399} //namespace hugo
1400
1401#endif //HUGO_GRAPH_WRAPPER_H
1402
Note: See TracBrowser for help on using the repository browser.