COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1663:f6741cfab647

Last change on this file since 1663:f6741cfab647 was 1631:e15162d8eca1, checked in by Alpar Juttner, 19 years ago

Fixed most (but not all) of Doxygen warnings

File size: 49.4 KB
Line 
1/* -*- C++ -*-
2 * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_GRAPH_ADAPTOR_H
18#define LEMON_GRAPH_ADAPTOR_H
19
20///\ingroup graph_adaptors
21///\file
22///\brief Several graph adaptors.
23///
24///This file contains several useful graph adaptor functions.
25///
26///\author Marton Makai
27
28#include <lemon/invalid.h>
29#include <lemon/maps.h>
30#include <lemon/bits/erasable_graph_extender.h>
31#include <lemon/bits/clearable_graph_extender.h>
32#include <lemon/bits/extendable_graph_extender.h>
33#include <lemon/bits/iterable_graph_extender.h>
34#include <lemon/bits/alteration_notifier.h>
35#include <lemon/bits/default_map.h>
36#include <lemon/bits/undir_graph_extender.h>
37#include <iostream>
38
39namespace lemon {
40
41  // Graph adaptors
42
43  /*!
44    \addtogroup graph_adaptors
45    @{
46   */
47
48  /*!
49    Base type for the Graph Adaptors
50   
51    \warning Graph adaptors are in even more experimental state than the other
52    parts of the lib. Use them at you own risk.
53   
54    This is the base type for most of LEMON graph adaptors.
55    This class implements a trivial graph adaptor i.e. it only wraps the
56    functions and types of the graph. The purpose of this class is to
57    make easier implementing graph adaptors. E.g. if an adaptor is
58    considered which differs from the wrapped graph only in some of its
59    functions or types, then it can be derived from GraphAdaptor, and only the
60    differences should be implemented.
61 
62    \author Marton Makai
63  */
64  template<typename _Graph>
65  class GraphAdaptorBase {
66  public:
67    typedef _Graph Graph;
68    /// \todo Is it needed?
69    typedef Graph BaseGraph;
70    typedef Graph ParentGraph;
71
72  protected:
73    Graph* graph;
74    GraphAdaptorBase() : graph(0) { }
75    void setGraph(Graph& _graph) { graph=&_graph; }
76
77  public:
78    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
79 
80    typedef typename Graph::Node Node;
81    typedef typename Graph::Edge Edge;
82   
83    void first(Node& i) const { graph->first(i); }
84    void first(Edge& i) const { graph->first(i); }
85    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
86    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
87
88    void next(Node& i) const { graph->next(i); }
89    void next(Edge& i) const { graph->next(i); }
90    void nextIn(Edge& i) const { graph->nextIn(i); }
91    void nextOut(Edge& i) const { graph->nextOut(i); }
92
93    Node source(const Edge& e) const { return graph->source(e); }
94    Node target(const Edge& e) const { return graph->target(e); }
95
96    int nodeNum() const { return graph->nodeNum(); }
97    int edgeNum() const { return graph->edgeNum(); }
98 
99    Node addNode() const { return Node(graph->addNode()); }
100    Edge addEdge(const Node& source, const Node& target) const {
101      return Edge(graph->addEdge(source, target)); }
102
103    void erase(const Node& i) const { graph->erase(i); }
104    void erase(const Edge& i) const { graph->erase(i); }
105 
106    void clear() const { graph->clear(); }
107   
108    int id(const Node& v) const { return graph->id(v); }
109    int id(const Edge& e) const { return graph->id(e); }
110   
111    Edge oppositeNode(const Edge& e) const {
112      return Edge(graph->opposite(e));
113    }
114
115    template <typename _Value>
116    class NodeMap : public _Graph::template NodeMap<_Value> {
117    public:
118      typedef typename _Graph::template NodeMap<_Value> Parent;
119      NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
120      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
121      : Parent(*gw.graph, value) { }
122    };
123
124    template <typename _Value>
125    class EdgeMap : public _Graph::template EdgeMap<_Value> {
126    public:
127      typedef typename _Graph::template EdgeMap<_Value> Parent;
128      EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
129      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
130      : Parent(*gw.graph, value) { }
131    };
132
133  };
134
135  template <typename _Graph>
136  class GraphAdaptor :
137    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
138  public:
139    typedef _Graph Graph;
140    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
141  protected:
142    GraphAdaptor() : Parent() { }
143
144  public:
145    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
146  };
147
148  template <typename _Graph>
149  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
150  public:
151    typedef _Graph Graph;
152    typedef GraphAdaptorBase<_Graph> Parent;
153  protected:
154    RevGraphAdaptorBase() : Parent() { }
155  public:
156    typedef typename Parent::Node Node;
157    typedef typename Parent::Edge Edge;
158
159    //    using Parent::first;
160    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
161    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
162
163    //    using Parent::next;
164    void nextIn(Edge& i) const { Parent::nextOut(i); }
165    void nextOut(Edge& i) const { Parent::nextIn(i); }
166
167    Node source(const Edge& e) const { return Parent::target(e); }
168    Node target(const Edge& e) const { return Parent::source(e); }
169  };
170   
171
172  /// A graph adaptor which reverses the orientation of the edges.
173
174  ///\warning Graph adaptors are in even more experimental state than the other
175  ///parts of the lib. Use them at you own risk.
176  ///
177  /// Let \f$G=(V, A)\f$ be a directed graph and
178  /// suppose that a graph instange \c g of type
179  /// \c ListGraph implements \f$G\f$.
180  /// \code
181  /// ListGraph g;
182  /// \endcode
183  /// For each directed edge
184  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
185  /// reversing its orientation.
186  /// Then RevGraphAdaptor implements the graph structure with node-set
187  /// \f$V\f$ and edge-set
188  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
189  /// reversing the orientation of its edges. The following code shows how
190  /// such an instance can be constructed.
191  /// \code
192  /// RevGraphAdaptor<ListGraph> gw(g);
193  /// \endcode
194  ///\author Marton Makai
195  template<typename _Graph>
196  class RevGraphAdaptor :
197    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
198  public:
199    typedef _Graph Graph;
200    typedef IterableGraphExtender<
201      RevGraphAdaptorBase<_Graph> > Parent;
202  protected:
203    RevGraphAdaptor() { }
204  public:
205    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
206  };
207
208 
209  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
210  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
211  public:
212    typedef _Graph Graph;
213    typedef GraphAdaptorBase<_Graph> Parent;
214  protected:
215    NodeFilterMap* node_filter_map;
216    EdgeFilterMap* edge_filter_map;
217    SubGraphAdaptorBase() : Parent(),
218                            node_filter_map(0), edge_filter_map(0) { }
219
220    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
221      node_filter_map=&_node_filter_map;
222    }
223    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
224      edge_filter_map=&_edge_filter_map;
225    }
226
227  public:
228//     SubGraphAdaptorBase(Graph& _graph,
229//                      NodeFilterMap& _node_filter_map,
230//                      EdgeFilterMap& _edge_filter_map) :
231//       Parent(&_graph),
232//       node_filter_map(&node_filter_map),
233//       edge_filter_map(&edge_filter_map) { }
234
235    typedef typename Parent::Node Node;
236    typedef typename Parent::Edge Edge;
237
238    void first(Node& i) const {
239      Parent::first(i);
240      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
241    }
242    void first(Edge& i) const {
243      Parent::first(i);
244      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
245    }
246    void firstIn(Edge& i, const Node& n) const {
247      Parent::firstIn(i, n);
248      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
249    }
250    void firstOut(Edge& i, const Node& n) const {
251      Parent::firstOut(i, n);
252      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
253    }
254
255    void next(Node& i) const {
256      Parent::next(i);
257      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
258    }
259    void next(Edge& i) const {
260      Parent::next(i);
261      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
262    }
263    void nextIn(Edge& i) const {
264      Parent::nextIn(i);
265      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
266    }
267    void nextOut(Edge& i) const {
268      Parent::nextOut(i);
269      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
270    }
271
272    /// This function hides \c n in the graph, i.e. the iteration
273    /// jumps over it. This is done by simply setting the value of \c n 
274    /// to be false in the corresponding node-map.
275    void hide(const Node& n) const { node_filter_map->set(n, false); }
276
277    /// This function hides \c e in the graph, i.e. the iteration
278    /// jumps over it. This is done by simply setting the value of \c e 
279    /// to be false in the corresponding edge-map.
280    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
281
282    /// The value of \c n is set to be true in the node-map which stores
283    /// hide information. If \c n was hidden previuosly, then it is shown
284    /// again
285     void unHide(const Node& n) const { node_filter_map->set(n, true); }
286
287    /// The value of \c e is set to be true in the edge-map which stores
288    /// hide information. If \c e was hidden previuosly, then it is shown
289    /// again
290    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
291
292    /// Returns true if \c n is hidden.
293    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
294
295    /// Returns true if \c n is hidden.
296    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
297
298    /// \warning This is a linear time operation and works only if s
299    /// \c Graph::NodeIt is defined.
300    /// \todo assign tags.
301    int nodeNum() const {
302      int i=0;
303      Node n;
304      for (first(n); n!=INVALID; next(n)) ++i;
305      return i;
306    }
307
308    /// \warning This is a linear time operation and works only if
309    /// \c Graph::EdgeIt is defined.
310    /// \todo assign tags.
311    int edgeNum() const {
312      int i=0;
313      Edge e;
314      for (first(e); e!=INVALID; next(e)) ++i;
315      return i;
316    }
317
318
319  };
320
321  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
322   
323  \warning Graph adaptors are in even more experimental state than the other
324  parts of the lib. Use them at you own risk.
325 
326  SubGraphAdaptor shows the graph with filtered node-set and
327  edge-set.
328  Let \f$G=(V, A)\f$ be a directed graph
329  and suppose that the graph instance \c g of type ListGraph implements
330  \f$G\f$.
331  Let moreover \f$b_V\f$ and
332  \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
333  SubGraphAdaptor<...>::NodeIt iterates
334  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
335  SubGraphAdaptor<...>::EdgeIt iterates
336  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
337  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
338  only on edges leaving and entering a specific node which have true value.
339
340  We have to note that this does not mean that an
341  induced subgraph is obtained, the node-iterator cares only the filter
342  on the node-set, and the edge-iterators care only the filter on the
343  edge-set.
344  \code
345  typedef ListGraph Graph;
346  Graph g;
347  typedef Graph::Node Node;
348  typedef Graph::Edge Edge;
349  Node u=g.addNode(); //node of id 0
350  Node v=g.addNode(); //node of id 1
351  Node e=g.addEdge(u, v); //edge of id 0
352  Node f=g.addEdge(v, u); //edge of id 1
353  Graph::NodeMap<bool> nm(g, true);
354  nm.set(u, false);
355  Graph::EdgeMap<bool> em(g, true);
356  em.set(e, false);
357  typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
358  SubGW gw(g, nm, em);
359  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
360  std::cout << ":-)" << std::endl;
361  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
362  \endcode
363  The output of the above code is the following.
364  \code
365  1
366  :-)
367  1
368  \endcode
369  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
370  \c Graph::Node that is why \c g.id(n) can be applied.
371
372  For other examples see also the documentation of NodeSubGraphAdaptor and
373  EdgeSubGraphAdaptor.
374
375  \author Marton Makai
376  */
377  template<typename _Graph, typename NodeFilterMap,
378           typename EdgeFilterMap>
379  class SubGraphAdaptor :
380    public IterableGraphExtender<
381    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
382  public:
383    typedef _Graph Graph;
384    typedef IterableGraphExtender<
385      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
386  protected:
387    SubGraphAdaptor() { }
388  public:
389    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
390                    EdgeFilterMap& _edge_filter_map) {
391      setGraph(_graph);
392      setNodeFilterMap(_node_filter_map);
393      setEdgeFilterMap(_edge_filter_map);
394    }
395  };
396
397
398
399  /*! \brief An adaptor for hiding nodes from a graph.
400
401  \warning Graph adaptors are in even more experimental state than the other
402  parts of the lib. Use them at you own risk.
403 
404  An adaptor for hiding nodes from a graph.
405  This adaptor specializes SubGraphAdaptor in the way that only the node-set
406  can be filtered. Note that this does not mean of considering induced
407  subgraph, the edge-iterators consider the original edge-set.
408  \author Marton Makai
409  */
410  template<typename Graph, typename NodeFilterMap>
411  class NodeSubGraphAdaptor :
412    public SubGraphAdaptor<Graph, NodeFilterMap,
413                           ConstMap<typename Graph::Edge,bool> > {
414  public:
415    typedef SubGraphAdaptor<Graph, NodeFilterMap,
416                            ConstMap<typename Graph::Edge,bool> > Parent;
417  protected:
418    ConstMap<typename Graph::Edge, bool> const_true_map;
419  public:
420    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
421      Parent(), const_true_map(true) {
422      Parent::setGraph(_graph);
423      Parent::setNodeFilterMap(_node_filter_map);
424      Parent::setEdgeFilterMap(const_true_map);
425    }
426  };
427
428
429  /*! \brief An adaptor for hiding edges from a graph.
430
431  \warning Graph adaptors are in even more experimental state than the other
432  parts of the lib. Use them at you own risk.
433 
434  An adaptor for hiding edges from a graph.
435  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
436  can be filtered. The usefulness of this adaptor is demonstrated in the
437  problem of searching a maximum number of edge-disjoint shortest paths
438  between
439  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
440  non-negative edge-lengths. Note that
441  the comprehension of the presented solution
442  need's some elementary knowledge from combinatorial optimization.
443
444  If a single shortest path is to be
445  searched between \c s and \c t, then this can be done easily by
446  applying the Dijkstra algorithm. What happens, if a maximum number of
447  edge-disjoint shortest paths is to be computed. It can be proved that an
448  edge can be in a shortest path if and only if it is tight with respect to
449  the potential function computed by Dijkstra. Moreover, any path containing
450  only such edges is a shortest one. Thus we have to compute a maximum number
451  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
452  all the tight edges. The computation will be demonstrated on the following
453  graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
454  The full source code is available in \ref sub_graph_adaptor_demo.cc.
455  If you are interested in more demo programs, you can use
456  \ref dim_to_dot.cc to generate .dot files from dimacs files.
457  The .dot file of the following figure was generated by 
458  the demo program \ref dim_to_dot.cc.
459
460  \dot
461  digraph lemon_dot_example {
462  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
463  n0 [ label="0 (s)" ];
464  n1 [ label="1" ];
465  n2 [ label="2" ];
466  n3 [ label="3" ];
467  n4 [ label="4" ];
468  n5 [ label="5" ];
469  n6 [ label="6 (t)" ];
470  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
471  n5 ->  n6 [ label="9, length:4" ];
472  n4 ->  n6 [ label="8, length:2" ];
473  n3 ->  n5 [ label="7, length:1" ];
474  n2 ->  n5 [ label="6, length:3" ];
475  n2 ->  n6 [ label="5, length:5" ];
476  n2 ->  n4 [ label="4, length:2" ];
477  n1 ->  n4 [ label="3, length:3" ];
478  n0 ->  n3 [ label="2, length:1" ];
479  n0 ->  n2 [ label="1, length:2" ];
480  n0 ->  n1 [ label="0, length:3" ];
481  }
482  \enddot
483
484  \code
485  Graph g;
486  Node s, t;
487  LengthMap length(g);
488
489  readDimacs(std::cin, g, length, s, t);
490
491  cout << "edges with lengths (of form id, source--length->target): " << endl;
492  for(EdgeIt e(g); e!=INVALID; ++e)
493    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
494         << length[e] << "->" << g.id(g.target(e)) << endl;
495
496  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
497  \endcode
498  Next, the potential function is computed with Dijkstra.
499  \code
500  typedef Dijkstra<Graph, LengthMap> Dijkstra;
501  Dijkstra dijkstra(g, length);
502  dijkstra.run(s);
503  \endcode
504  Next, we consrtruct a map which filters the edge-set to the tight edges.
505  \code
506  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
507    TightEdgeFilter;
508  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
509 
510  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
511  SubGW gw(g, tight_edge_filter);
512  \endcode
513  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
514  with a max flow algorithm Preflow.
515  \code
516  ConstMap<Edge, int> const_1_map(1);
517  Graph::EdgeMap<int> flow(g, 0);
518
519  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
520    preflow(gw, s, t, const_1_map, flow);
521  preflow.run();
522  \endcode
523  Last, the output is:
524  \code 
525  cout << "maximum number of edge-disjoint shortest path: "
526       << preflow.flowValue() << endl;
527  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
528       << endl;
529  for(EdgeIt e(g); e!=INVALID; ++e)
530    if (flow[e])
531      cout << " " << g.id(g.source(e)) << "--"
532           << length[e] << "->" << g.id(g.target(e)) << endl;
533  \endcode
534  The program has the following (expected :-)) output:
535  \code
536  edges with lengths (of form id, source--length->target):
537   9, 5--4->6
538   8, 4--2->6
539   7, 3--1->5
540   6, 2--3->5
541   5, 2--5->6
542   4, 2--2->4
543   3, 1--3->4
544   2, 0--1->3
545   1, 0--2->2
546   0, 0--3->1
547  s: 0 t: 6
548  maximum number of edge-disjoint shortest path: 2
549  edges of the maximum number of edge-disjoint shortest s-t paths:
550   9, 5--4->6
551   8, 4--2->6
552   7, 3--1->5
553   4, 2--2->4
554   2, 0--1->3
555   1, 0--2->2
556  \endcode
557
558  \author Marton Makai
559  */
560  template<typename Graph, typename EdgeFilterMap>
561  class EdgeSubGraphAdaptor :
562    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
563                           EdgeFilterMap> {
564  public:
565    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
566                            EdgeFilterMap> Parent;
567  protected:
568    ConstMap<typename Graph::Node, bool> const_true_map;
569  public:
570    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
571      Parent(), const_true_map(true) {
572      Parent::setGraph(_graph);
573      Parent::setNodeFilterMap(const_true_map);
574      Parent::setEdgeFilterMap(_edge_filter_map);
575    }
576  };
577
578  template <typename _Graph>
579  class UndirGraphAdaptorBase :
580    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
581  public:
582    typedef _Graph Graph;
583    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
584  protected:
585    UndirGraphAdaptorBase() : Parent() { }
586  public:
587    typedef typename Parent::UndirEdge UndirEdge;
588    typedef typename Parent::Edge Edge;
589   
590    /// \bug Why cant an edge say that it is forward or not???
591    /// By this, a pointer to the graph have to be stored
592    /// The implementation
593    template <typename T>
594    class EdgeMap {
595    protected:
596      const UndirGraphAdaptorBase<_Graph>* g;
597      template <typename TT> friend class EdgeMap;
598      typename _Graph::template EdgeMap<T> forward_map, backward_map;
599    public:
600      typedef T Value;
601      typedef Edge Key;
602     
603      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
604        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
605
606      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
607        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
608     
609      void set(Edge e, T a) {
610        if (g->direction(e))
611          forward_map.set(e, a);
612        else
613          backward_map.set(e, a);
614      }
615
616      T operator[](Edge e) const {
617        if (g->direction(e))
618          return forward_map[e];
619        else
620          return backward_map[e];
621      }
622    };
623       
624    template <typename T>
625    class UndirEdgeMap {
626      template <typename TT> friend class UndirEdgeMap;
627      typename _Graph::template EdgeMap<T> map;
628    public:
629      typedef T Value;
630      typedef UndirEdge Key;
631     
632      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
633        map(*(g.graph)) { }
634
635      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
636        map(*(g.graph), a) { }
637     
638      void set(UndirEdge e, T a) {
639        map.set(e, a);
640      }
641
642      T operator[](UndirEdge e) const {
643        return map[e];
644      }
645    };
646     
647  };
648
649  /// \brief An undirected graph is made from a directed graph by an adaptor
650  ///
651  /// Undocumented, untested!!!
652  /// If somebody knows nice demo application, let's polulate it.
653  ///
654  /// \author Marton Makai
655  template<typename _Graph>
656  class UndirGraphAdaptor :
657    public IterableUndirGraphExtender<
658    UndirGraphAdaptorBase<_Graph> > {
659  public:
660    typedef _Graph Graph;
661    typedef IterableUndirGraphExtender<
662      UndirGraphAdaptorBase<_Graph> > Parent;
663  protected:
664    UndirGraphAdaptor() { }
665  public:
666    UndirGraphAdaptor(_Graph& _graph) {
667      setGraph(_graph);
668    }
669  };
670
671 
672  template <typename _Graph,
673            typename ForwardFilterMap, typename BackwardFilterMap>
674  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
675  public:
676    typedef _Graph Graph;
677    typedef GraphAdaptorBase<_Graph> Parent;
678  protected:
679    ForwardFilterMap* forward_filter;
680    BackwardFilterMap* backward_filter;
681    SubBidirGraphAdaptorBase() : Parent(),
682                                 forward_filter(0), backward_filter(0) { }
683
684    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
685      forward_filter=&_forward_filter;
686    }
687    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
688      backward_filter=&_backward_filter;
689    }
690
691  public:
692//     SubGraphAdaptorBase(Graph& _graph,
693//                      NodeFilterMap& _node_filter_map,
694//                      EdgeFilterMap& _edge_filter_map) :
695//       Parent(&_graph),
696//       node_filter_map(&node_filter_map),
697//       edge_filter_map(&edge_filter_map) { }
698
699    typedef typename Parent::Node Node;
700    typedef typename _Graph::Edge GraphEdge;
701    template <typename T> class EdgeMap;
702    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
703    /// _Graph::Edge. It contains an extra bool flag which is true
704    /// if and only if the
705    /// edge is the backward version of the original edge.
706    class Edge : public _Graph::Edge {
707      friend class SubBidirGraphAdaptorBase<
708        Graph, ForwardFilterMap, BackwardFilterMap>;
709      template<typename T> friend class EdgeMap;
710    protected:
711      bool backward; //true, iff backward
712    public:
713      Edge() { }
714      /// \todo =false is needed, or causes problems?
715      /// If \c _backward is false, then we get an edge corresponding to the
716      /// original one, otherwise its oppositely directed pair is obtained.
717      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
718        _Graph::Edge(e), backward(_backward) { }
719      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
720      bool operator==(const Edge& v) const {
721        return (this->backward==v.backward &&
722                static_cast<typename _Graph::Edge>(*this)==
723                static_cast<typename _Graph::Edge>(v));
724      }
725      bool operator!=(const Edge& v) const {
726        return (this->backward!=v.backward ||
727                static_cast<typename _Graph::Edge>(*this)!=
728                static_cast<typename _Graph::Edge>(v));
729      }
730    };
731
732    void first(Node& i) const {
733      Parent::first(i);
734    }
735
736    void first(Edge& i) const {
737      Parent::first(i);
738      i.backward=false;
739      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
740             !(*forward_filter)[i]) Parent::next(i);
741      if (*static_cast<GraphEdge*>(&i)==INVALID) {
742        Parent::first(i);
743        i.backward=true;
744        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
745               !(*backward_filter)[i]) Parent::next(i);
746      }
747    }
748
749    void firstIn(Edge& i, const Node& n) const {
750      Parent::firstIn(i, n);
751      i.backward=false;
752      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
753             !(*forward_filter)[i]) Parent::nextIn(i);
754      if (*static_cast<GraphEdge*>(&i)==INVALID) {
755        Parent::firstOut(i, n);
756        i.backward=true;
757        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
758               !(*backward_filter)[i]) Parent::nextOut(i);
759      }
760    }
761
762    void firstOut(Edge& i, const Node& n) const {
763      Parent::firstOut(i, n);
764      i.backward=false;
765      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
766             !(*forward_filter)[i]) Parent::nextOut(i);
767      if (*static_cast<GraphEdge*>(&i)==INVALID) {
768        Parent::firstIn(i, n);
769        i.backward=true;
770        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
771               !(*backward_filter)[i]) Parent::nextIn(i);
772      }
773    }
774
775    void next(Node& i) const {
776      Parent::next(i);
777    }
778
779    void next(Edge& i) const {
780      if (!(i.backward)) {
781        Parent::next(i);
782        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
783               !(*forward_filter)[i]) Parent::next(i);
784        if (*static_cast<GraphEdge*>(&i)==INVALID) {
785          Parent::first(i);
786          i.backward=true;
787          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
788                 !(*backward_filter)[i]) Parent::next(i);
789        }
790      } else {
791        Parent::next(i);
792        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
793               !(*backward_filter)[i]) Parent::next(i);
794      }
795    }
796
797    void nextIn(Edge& i) const {
798      if (!(i.backward)) {
799        Node n=Parent::target(i);
800        Parent::nextIn(i);
801        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
802               !(*forward_filter)[i]) Parent::nextIn(i);
803        if (*static_cast<GraphEdge*>(&i)==INVALID) {
804          Parent::firstOut(i, n);
805          i.backward=true;
806          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
807                 !(*backward_filter)[i]) Parent::nextOut(i);
808        }
809      } else {
810        Parent::nextOut(i);
811        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
812               !(*backward_filter)[i]) Parent::nextOut(i);
813      }
814    }
815
816    void nextOut(Edge& i) const {
817      if (!(i.backward)) {
818        Node n=Parent::source(i);
819        Parent::nextOut(i);
820        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
821               !(*forward_filter)[i]) Parent::nextOut(i);
822        if (*static_cast<GraphEdge*>(&i)==INVALID) {
823          Parent::firstIn(i, n);
824          i.backward=true;
825          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
826                 !(*backward_filter)[i]) Parent::nextIn(i);
827        }
828      } else {
829        Parent::nextIn(i);
830        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
831               !(*backward_filter)[i]) Parent::nextIn(i);
832      }
833    }
834
835    Node source(Edge e) const {
836      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
837    Node target(Edge e) const {
838      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
839
840    /// Gives back the opposite edge.
841    Edge opposite(const Edge& e) const {
842      Edge f=e;
843      f.backward=!f.backward;
844      return f;
845    }
846
847    /// \warning This is a linear time operation and works only if
848    /// \c Graph::EdgeIt is defined.
849    /// \todo hmm
850    int edgeNum() const {
851      int i=0;
852      Edge e;
853      for (first(e); e!=INVALID; next(e)) ++i;
854      return i;
855    }
856
857    bool forward(const Edge& e) const { return !e.backward; }
858    bool backward(const Edge& e) const { return e.backward; }
859
860    template <typename T>
861    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
862    /// _Graph::EdgeMap one for the forward edges and
863    /// one for the backward edges.
864    class EdgeMap {
865      template <typename TT> friend class EdgeMap;
866      typename _Graph::template EdgeMap<T> forward_map, backward_map;
867    public:
868      typedef T Value;
869      typedef Edge Key;
870
871      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
872              ForwardFilterMap, BackwardFilterMap>& g) :
873        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
874
875      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
876              ForwardFilterMap, BackwardFilterMap>& g, T a) :
877        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
878     
879      void set(Edge e, T a) {
880        if (!e.backward)
881          forward_map.set(e, a);
882        else
883          backward_map.set(e, a);
884      }
885
886//       typename _Graph::template EdgeMap<T>::ConstReference
887//       operator[](Edge e) const {
888//      if (!e.backward)
889//        return forward_map[e];
890//      else
891//        return backward_map[e];
892//       }
893
894//      typename _Graph::template EdgeMap<T>::Reference
895      T operator[](Edge e) const {
896        if (!e.backward)
897          return forward_map[e];
898        else
899          return backward_map[e];
900      }
901
902      void update() {
903        forward_map.update();
904        backward_map.update();
905      }
906    };
907
908  };
909
910
911  ///\brief An adaptor for composing a subgraph of a
912  /// bidirected graph made from a directed one.
913  ///
914  /// An adaptor for composing a subgraph of a
915  /// bidirected graph made from a directed one.
916  ///
917  ///\warning Graph adaptors are in even more experimental state than the other
918  ///parts of the lib. Use them at you own risk.
919  ///
920  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
921  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
922  /// reversing its orientation. We are given moreover two bool valued
923  /// maps on the edge-set,
924  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
925  /// SubBidirGraphAdaptor implements the graph structure with node-set
926  /// \f$V\f$ and edge-set
927  /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
928  /// The purpose of writing + instead of union is because parallel
929  /// edges can arise. (Similarly, antiparallel edges also can arise).
930  /// In other words, a subgraph of the bidirected graph obtained, which
931  /// is given by orienting the edges of the original graph in both directions.
932  /// As the oppositely directed edges are logically different,
933  /// the maps are able to attach different values for them.
934  ///
935  /// An example for such a construction is \c RevGraphAdaptor where the
936  /// forward_filter is everywhere false and the backward_filter is
937  /// everywhere true. We note that for sake of efficiency,
938  /// \c RevGraphAdaptor is implemented in a different way.
939  /// But BidirGraphAdaptor is obtained from
940  /// SubBidirGraphAdaptor by considering everywhere true
941  /// valued maps both for forward_filter and backward_filter.
942  ///
943  /// The most important application of SubBidirGraphAdaptor
944  /// is ResGraphAdaptor, which stands for the residual graph in directed
945  /// flow and circulation problems.
946  /// As adaptors usually, the SubBidirGraphAdaptor implements the
947  /// above mentioned graph structure without its physical storage,
948  /// that is the whole stuff is stored in constant memory.
949  template<typename _Graph,
950           typename ForwardFilterMap, typename BackwardFilterMap>
951  class SubBidirGraphAdaptor :
952    public IterableGraphExtender<
953    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
954  public:
955    typedef _Graph Graph;
956    typedef IterableGraphExtender<
957      SubBidirGraphAdaptorBase<
958      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
959  protected:
960    SubBidirGraphAdaptor() { }
961  public:
962    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
963                         BackwardFilterMap& _backward_filter) {
964      setGraph(_graph);
965      setForwardFilterMap(_forward_filter);
966      setBackwardFilterMap(_backward_filter);
967    }
968  };
969
970
971
972  ///\brief An adaptor for composing bidirected graph from a directed one.
973  ///
974  ///\warning Graph adaptors are in even more experimental state than the other
975  ///parts of the lib. Use them at you own risk.
976  ///
977  /// An adaptor for composing bidirected graph from a directed one.
978  /// A bidirected graph is composed over the directed one without physical
979  /// storage. As the oppositely directed edges are logically different ones
980  /// the maps are able to attach different values for them.
981  template<typename Graph>
982  class BidirGraphAdaptor :
983    public SubBidirGraphAdaptor<
984    Graph,
985    ConstMap<typename Graph::Edge, bool>,
986    ConstMap<typename Graph::Edge, bool> > {
987  public:
988    typedef  SubBidirGraphAdaptor<
989      Graph,
990      ConstMap<typename Graph::Edge, bool>,
991      ConstMap<typename Graph::Edge, bool> > Parent;
992  protected:
993    ConstMap<typename Graph::Edge, bool> cm;
994
995    BidirGraphAdaptor() : Parent(), cm(true) {
996      Parent::setForwardFilterMap(cm);
997      Parent::setBackwardFilterMap(cm);
998    }
999  public:
1000    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1001      Parent::setGraph(_graph);
1002      Parent::setForwardFilterMap(cm);
1003      Parent::setBackwardFilterMap(cm);
1004    }
1005
1006    int edgeNum() const {
1007      return 2*this->graph->edgeNum();
1008    }
1009    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
1010  };
1011
1012
1013  template<typename Graph, typename Number,
1014           typename CapacityMap, typename FlowMap>
1015  class ResForwardFilter {
1016    //    const Graph* graph;
1017    const CapacityMap* capacity;
1018    const FlowMap* flow;
1019  public:
1020    ResForwardFilter(/*const Graph& _graph, */
1021                     const CapacityMap& _capacity, const FlowMap& _flow) :
1022      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1023    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1024    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1025    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1026    bool operator[](const typename Graph::Edge& e) const {
1027      return (Number((*flow)[e]) < Number((*capacity)[e]));
1028    }
1029  };
1030
1031  template<typename Graph, typename Number,
1032           typename CapacityMap, typename FlowMap>
1033  class ResBackwardFilter {
1034    const CapacityMap* capacity;
1035    const FlowMap* flow;
1036  public:
1037    ResBackwardFilter(/*const Graph& _graph,*/
1038                      const CapacityMap& _capacity, const FlowMap& _flow) :
1039      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1040    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1041    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1042    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1043    bool operator[](const typename Graph::Edge& e) const {
1044      return (Number(0) < Number((*flow)[e]));
1045    }
1046  };
1047
1048 
1049  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1050
1051  An adaptor for composing the residual graph for directed flow and circulation problems.
1052  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1053  number type. Let moreover
1054  \f$f,c:A\to F\f$, be functions on the edge-set.
1055  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1056  and \f$c\f$ for a capacity function.   
1057  Suppose that a graph instange \c g of type
1058  \c ListGraph implements \f$G\f$.
1059  \code
1060  ListGraph g;
1061  \endcode
1062  Then RevGraphAdaptor implements the graph structure with node-set
1063  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1064  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1065  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1066  i.e. the so called residual graph.
1067  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1068  multilicities are counted, i.e. if an edge is in both
1069  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1070  appears twice.
1071  The following code shows how
1072  such an instance can be constructed.
1073  \code
1074  typedef ListGraph Graph;
1075  Graph::EdgeMap<int> f(g);
1076  Graph::EdgeMap<int> c(g);
1077  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1078  \endcode
1079  \author Marton Makai
1080  */
1081  template<typename Graph, typename Number,
1082           typename CapacityMap, typename FlowMap>
1083  class ResGraphAdaptor :
1084    public SubBidirGraphAdaptor<
1085    Graph,
1086    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1087    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1088  public:
1089    typedef SubBidirGraphAdaptor<
1090      Graph,
1091      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1092      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1093  protected:
1094    const CapacityMap* capacity;
1095    FlowMap* flow;
1096    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1097    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1098    ResGraphAdaptor() : Parent(),
1099                        capacity(0), flow(0) { }
1100    void setCapacityMap(const CapacityMap& _capacity) {
1101      capacity=&_capacity;
1102      forward_filter.setCapacity(_capacity);
1103      backward_filter.setCapacity(_capacity);
1104    }
1105    void setFlowMap(FlowMap& _flow) {
1106      flow=&_flow;
1107      forward_filter.setFlow(_flow);
1108      backward_filter.setFlow(_flow);
1109    }
1110  public:
1111    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1112                       FlowMap& _flow) :
1113      Parent(), capacity(&_capacity), flow(&_flow),
1114      forward_filter(/*_graph,*/ _capacity, _flow),
1115      backward_filter(/*_graph,*/ _capacity, _flow) {
1116      Parent::setGraph(_graph);
1117      Parent::setForwardFilterMap(forward_filter);
1118      Parent::setBackwardFilterMap(backward_filter);
1119    }
1120
1121    typedef typename Parent::Edge Edge;
1122
1123    void augment(const Edge& e, Number a) const {
1124      if (Parent::forward(e)) 
1125        flow->set(e, (*flow)[e]+a);
1126      else 
1127        flow->set(e, (*flow)[e]-a);
1128    }
1129
1130    /// \brief Residual capacity map.
1131    ///
1132    /// In generic residual graphs the residual capacity can be obtained
1133    /// as a map.
1134    class ResCap {
1135    protected:
1136      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1137    public:
1138      typedef Number Value;
1139      typedef Edge Key;
1140      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1141             _res_graph) : res_graph(&_res_graph) { }
1142      Number operator[](const Edge& e) const {
1143        if (res_graph->forward(e))
1144          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1145        else
1146          return (*(res_graph->flow))[e];
1147      }
1148    };
1149
1150    //    KEEP_MAPS(Parent, ResGraphAdaptor);
1151  };
1152
1153
1154
1155  template <typename _Graph, typename FirstOutEdgesMap>
1156  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1157  public:
1158    typedef _Graph Graph;
1159    typedef GraphAdaptorBase<_Graph> Parent;
1160  protected:
1161    FirstOutEdgesMap* first_out_edges;
1162    ErasingFirstGraphAdaptorBase() : Parent(),
1163                                     first_out_edges(0) { }
1164
1165    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1166      first_out_edges=&_first_out_edges;
1167    }
1168
1169  public:
1170
1171    typedef typename Parent::Node Node;
1172    typedef typename Parent::Edge Edge;
1173
1174    void firstOut(Edge& i, const Node& n) const {
1175      i=(*first_out_edges)[n];
1176    }
1177
1178    void erase(const Edge& e) const {
1179      Node n=source(e);
1180      Edge f=e;
1181      Parent::nextOut(f);
1182      first_out_edges->set(n, f);
1183    }   
1184  };
1185
1186
1187  /// For blocking flows.
1188
1189  ///\warning Graph adaptors are in even more experimental state than the other
1190  ///parts of the lib. Use them at you own risk.
1191  ///
1192  /// This graph adaptor is used for on-the-fly
1193  /// Dinits blocking flow computations.
1194  /// For each node, an out-edge is stored which is used when the
1195  /// \code
1196  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1197  /// \endcode
1198  /// is called.
1199  ///
1200  /// \author Marton Makai
1201  template <typename _Graph, typename FirstOutEdgesMap>
1202  class ErasingFirstGraphAdaptor :
1203    public IterableGraphExtender<
1204    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1205  public:
1206    typedef _Graph Graph;
1207    typedef IterableGraphExtender<
1208      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1209    ErasingFirstGraphAdaptor(Graph& _graph,
1210                             FirstOutEdgesMap& _first_out_edges) {
1211      setGraph(_graph);
1212      setFirstOutEdgesMap(_first_out_edges);
1213    }
1214
1215  };
1216
1217  template <typename _Graph>
1218  class NewEdgeSetAdaptorBase {
1219  public:
1220
1221    typedef _Graph Graph;
1222    typedef typename Graph::Node Node;
1223    typedef typename Graph::NodeIt NodeIt;
1224
1225  protected:
1226
1227    struct NodeT {
1228      int first_out, first_in;
1229      NodeT() : first_out(-1), first_in(-1) {}
1230    };
1231   
1232    class NodesImpl : protected Graph::template NodeMap<NodeT> {
1233
1234      typedef typename Graph::template NodeMap<NodeT> Parent;
1235      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1236
1237      Adaptor& adaptor;
1238
1239    public:
1240
1241      NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1242        : Parent(_graph), adaptor(_adaptor) {}
1243
1244      virtual ~NodesImpl() {}
1245
1246      virtual void build() {
1247        Parent::build();
1248      }
1249
1250      virtual void clear() {
1251        adaptor._clear();
1252        Parent::clear();
1253      }
1254     
1255      virtual void add(const Node& node) {
1256        Parent::add(node);
1257        adaptor._add(node);
1258      }
1259     
1260      virtual void erase(const Node& node) {
1261        adaptor._erase(node);
1262        Parent::erase(node);
1263      }
1264
1265      NodeT& operator[](const Node& node) {
1266        return Parent::operator[](node);
1267      }
1268
1269      const NodeT& operator[](const Node& node) const {
1270        return Parent::operator[](node);
1271      }
1272     
1273    };
1274
1275    NodesImpl* nodes;
1276
1277    struct EdgeT {
1278      Node source, target;
1279      int next_out, next_in;
1280      int prev_out, prev_in;
1281      EdgeT() : prev_out(-1), prev_in(-1) {}
1282    };
1283
1284    std::vector<EdgeT> edges;
1285
1286    int first_edge;
1287    int first_free_edge;
1288
1289    virtual void _clear() = 0;
1290    virtual void _add(const Node& node) = 0;
1291    virtual void _erase(const Node& node) = 0;
1292   
1293    const Graph* graph;
1294
1295    void initalize(const Graph& _graph, NodesImpl& _nodes) {
1296      graph = &_graph;
1297      nodes = &_nodes;
1298    }
1299   
1300  public:
1301
1302    class Edge {
1303      friend class NewEdgeSetAdaptorBase<Graph>;
1304    protected:
1305      Edge(int _id) : id(_id) {}
1306      int id;
1307    public:
1308      Edge() {}
1309      Edge(Invalid) : id(-1) {}
1310      bool operator==(const Edge& edge) const { return id == edge.id; }
1311      bool operator!=(const Edge& edge) const { return id != edge.id; }
1312      bool operator<(const Edge& edge) const { return id < edge.id; }
1313    };
1314
1315    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1316    virtual ~NewEdgeSetAdaptorBase() {}
1317
1318    Edge addEdge(const Node& source, const Node& target) {
1319      int n;
1320      if (first_free_edge == -1) {
1321        n = edges.size();
1322        edges.push_back(EdgeT());
1323      } else {
1324        n = first_free_edge;
1325        first_free_edge = edges[first_free_edge].next_in;
1326      }
1327      edges[n].next_in = (*nodes)[target].first_in;
1328      (*nodes)[target].first_in = n;
1329      edges[n].next_out = (*nodes)[source].first_out;
1330      (*nodes)[source].first_out = n;
1331      edges[n].source = source;
1332      edges[n].target = target;
1333      return Edge(n);
1334    }
1335
1336    void erase(const Edge& edge) {
1337      int n = edge.id;
1338      if (edges[n].prev_in != -1) {
1339        edges[edges[n].prev_in].next_in = edges[n].next_in;
1340      } else {
1341        (*nodes)[edges[n].target].first_in = edges[n].next_in;
1342      }
1343      if (edges[n].next_in != -1) {
1344        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1345      }
1346
1347      if (edges[n].prev_out != -1) {
1348        edges[edges[n].prev_out].next_out = edges[n].next_out;
1349      } else {
1350        (*nodes)[edges[n].source].first_out = edges[n].next_out;
1351      }
1352      if (edges[n].next_out != -1) {
1353        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1354      }
1355           
1356    }
1357
1358    void first(Node& node) const {
1359      graph->first(node);
1360    }
1361
1362    void next(Node& node) const {
1363      graph->next(node);
1364    }
1365
1366    void first(Edge& edge) const {
1367      Node node;
1368      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1369           next(node));
1370      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1371    }
1372
1373    void next(Edge& edge) const {
1374      if (edges[edge.id].next_in != -1) {
1375        edge.id = edges[edge.id].next_in;
1376      } else {
1377        Node node = edges[edge.id].target;
1378        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1379             next(node));
1380        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1381      }     
1382    }
1383
1384    void firstOut(Edge& edge, const Node& node) const {
1385      edge.id = (*nodes)[node].first_out;   
1386    }
1387   
1388    void nextOut(Edge& edge) const {
1389      edge.id = edges[edge.id].next_out;       
1390    }
1391
1392    void firstIn(Edge& edge, const Node& node) const {
1393      edge.id = (*nodes)[node].first_in;         
1394    }
1395
1396    void nextIn(Edge& edge) const {
1397      edge.id = edges[edge.id].next_in;   
1398    }
1399
1400    int id(const Node& node) const { return graph->id(node); }
1401    int id(const Edge& edge) const { return edge.id; }
1402
1403    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
1404    Edge fromId(int id, Edge) const { return Edge(id); }
1405
1406    int maxId(Node) const { return graph->maxId(Node()); };
1407    int maxId(Edge) const { return edges.size() - 1; }
1408
1409    Node source(const Edge& edge) const { return edges[edge.id].source;}
1410    Node target(const Edge& edge) const { return edges[edge.id].target;}
1411
1412  };
1413
1414
1415  /// \brief Graph adaptor using a node set of another graph and an
1416  /// own edge set.
1417  ///
1418  /// This structure can be used to establish another graph over a node set
1419  /// of an existing one. The node iterator will go through the nodes of the
1420  /// original graph.
1421  ///
1422  /// \param _Graph The type of the graph which shares its node set with
1423  /// this class. Its interface must conform to the \ref concept::StaticGraph
1424  /// "StaticGraph" concept.
1425  ///
1426  /// In the edge extension and removing it conforms to the
1427  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1428  template <typename _Graph>
1429  class NewEdgeSetAdaptor :
1430    public ErasableGraphExtender<
1431    ClearableGraphExtender<
1432    ExtendableGraphExtender<
1433    DefaultMappableGraphExtender<
1434    IterableGraphExtender<
1435    AlterableGraphExtender<
1436    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1437
1438  public:
1439
1440    typedef ErasableGraphExtender<
1441      ClearableGraphExtender<
1442      ExtendableGraphExtender<
1443      DefaultMappableGraphExtender<
1444      IterableGraphExtender<
1445      AlterableGraphExtender<
1446      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1447   
1448
1449    typedef typename Parent::Node Node;
1450    typedef typename Parent::Edge Edge;
1451
1452  private:
1453
1454    virtual void _clear() {
1455      Parent::edges.clear();
1456      Parent::first_edge = -1;
1457      Parent::first_free_edge = -1;
1458      Parent::getNotifier(Edge()).clear();
1459      Parent::getNotifier(Node()).clear();
1460    }
1461
1462    virtual void _add(const Node& node) {
1463      Parent::getNotifier(Node()).add(node);
1464    }
1465
1466    virtual void _erase(const Node& node) {
1467      Edge edge;
1468      Parent::firstOut(edge, node);
1469      while (edge != INVALID) {
1470        Parent::erase(edge);
1471        Parent::firstOut(edge, node);
1472      }
1473
1474      Parent::firstIn(edge, node);
1475      while (edge != INVALID) {
1476        Parent::erase(edge);
1477        Parent::firstIn(edge, node);
1478      }
1479     
1480      Parent::getNotifier(Node()).erase(node);
1481    }
1482
1483
1484    typedef typename Parent::NodesImpl NodesImpl;
1485
1486    NodesImpl nodes;
1487   
1488  public:
1489
1490    /// \brief Constructor of the adaptor.
1491    ///
1492    /// Constructor of the adaptor.
1493    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1494      Parent::initalize(_graph, nodes);
1495    }
1496
1497    void clear() {
1498      Parent::getNotifier(Edge()).clear();     
1499
1500      Parent::edges.clear();
1501      Parent::first_edge = -1;
1502      Parent::first_free_edge = -1;
1503    }
1504   
1505  };
1506
1507  /// \brief Graph adaptor using a node set of another graph and an
1508  /// own undir edge set.
1509  ///
1510  /// This structure can be used to establish another undirected graph over
1511  /// a node set of an existing one. The node iterator will go through the
1512  /// nodes of the original graph.
1513  ///
1514  /// \param _Graph The type of the graph which shares its node set with
1515  /// this class. Its interface must conform to the \ref concept::StaticGraph
1516  /// "StaticGraph" concept.
1517  ///
1518  /// In the edge extension and removing it conforms to the
1519  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1520  template <typename _Graph>
1521  class NewUndirEdgeSetAdaptor :
1522    public ErasableUndirGraphExtender<
1523    ClearableUndirGraphExtender<
1524    ExtendableUndirGraphExtender<
1525    MappableUndirGraphExtender<
1526    IterableUndirGraphExtender<
1527    AlterableUndirGraphExtender<
1528    UndirGraphExtender<
1529    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1530
1531  public:
1532
1533    typedef ErasableUndirGraphExtender<
1534      ClearableUndirGraphExtender<
1535      ExtendableUndirGraphExtender<
1536      MappableUndirGraphExtender<
1537      IterableUndirGraphExtender<
1538      AlterableUndirGraphExtender<
1539      UndirGraphExtender<
1540      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1541   
1542
1543    typedef typename Parent::Node Node;
1544    typedef typename Parent::Edge Edge;
1545    typedef typename Parent::UndirEdge UndirEdge;
1546
1547  private:
1548
1549    virtual void _clear() {
1550      Parent::edges.clear();
1551      Parent::first_edge = -1;
1552      Parent::first_free_edge = -1;
1553      Parent::getNotifier(Edge()).clear();
1554      Parent::getNotifier(Node()).clear();
1555    }
1556
1557    virtual void _add(const Node& node) {
1558      Parent::getNotifier(Node()).add(node);
1559    }
1560
1561    virtual void _erase(const Node& node) {
1562      Edge edge;
1563      Parent::firstOut(edge, node);
1564      while (edge != INVALID) {
1565        Parent::erase(edge);
1566        Parent::firstOut(edge, node);
1567      }
1568
1569      Parent::firstIn(edge, node);
1570      while (edge != INVALID) {
1571        Parent::erase(edge);
1572        Parent::firstIn(edge, node);
1573      }
1574     
1575      Parent::getNotifier(Node()).erase(node);
1576    }
1577
1578    typedef typename Parent::NodesImpl NodesImpl;
1579
1580    NodesImpl nodes;
1581   
1582  public:
1583
1584
1585    /// \brief Constructor of the adaptor.
1586    ///
1587    /// Constructor of the adaptor.
1588    NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1589      Parent::initalize(_graph, nodes);
1590    }
1591
1592    void clear() {
1593      Parent::getNotifier(Edge()).clear();     
1594      Parent::getNotifier(UndirEdge()).clear();     
1595
1596      Parent::edges.clear();
1597      Parent::first_edge = -1;
1598      Parent::first_free_edge = -1;
1599    }
1600   
1601  };
1602
1603  ///@}
1604
1605} //namespace lemon
1606
1607#endif //LEMON_GRAPH_ADAPTOR_H
1608
Note: See TracBrowser for help on using the repository browser.