COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/graph_wrapper.h @ 877:66dd225ca128

Last change on this file since 877:66dd225ca128 was 877:66dd225ca128, checked in by Balazs Dezso, 20 years ago

Fix maps in the GraphWrappers?.

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