# source:lemon-0.x/src/hugo/graph_wrapper.h@849:cc3867a7d380

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