COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1697:4c593a4096da

Last change on this file since 1697:4c593a4096da was 1697:4c593a4096da, checked in by Balazs Dezso, 14 years ago

Preliminary SplitGraphAdaptor?
And some other improvments

File size: 61.7 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    typedef Graph ParentGraph;
69
70  protected:
71    Graph* graph;
72    GraphAdaptorBase() : graph(0) { }
73    void setGraph(Graph& _graph) { graph=&_graph; }
74
75  public:
76    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
77 
78    typedef typename Graph::Node Node;
79    typedef typename Graph::Edge Edge;
80   
81    void first(Node& i) const { graph->first(i); }
82    void first(Edge& i) const { graph->first(i); }
83    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
84    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
85
86    void next(Node& i) const { graph->next(i); }
87    void next(Edge& i) const { graph->next(i); }
88    void nextIn(Edge& i) const { graph->nextIn(i); }
89    void nextOut(Edge& i) const { graph->nextOut(i); }
90
91    Node source(const Edge& e) const { return graph->source(e); }
92    Node target(const Edge& e) const { return graph->target(e); }
93
94    typedef NodeNumTagIndicator<Graph> NodeNumTag;
95    int nodeNum() const { return graph->nodeNum(); }
96   
97    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
98    int edgeNum() const { return graph->edgeNum(); }
99
100    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
101    Edge findEdge(const Node& source, const Node& target,
102                  const Edge& prev = INVALID) {
103      return graph->findEdge(source, target, prev);
104    }
105 
106    Node addNode() const {
107      return Node(graph->addNode());
108    }
109
110    Edge addEdge(const Node& source, const Node& target) const {
111      return Edge(graph->addEdge(source, target));
112    }
113
114    void erase(const Node& i) const { graph->erase(i); }
115    void erase(const Edge& i) const { graph->erase(i); }
116 
117    void clear() const { graph->clear(); }
118   
119    int id(const Node& v) const { return graph->id(v); }
120    int id(const Edge& e) const { return graph->id(e); }
121   
122    Edge oppositeNode(const Edge& e) const {
123      return Edge(graph->opposite(e));
124    }
125
126    template <typename _Value>
127    class NodeMap : public _Graph::template NodeMap<_Value> {
128    public:
129      typedef typename _Graph::template NodeMap<_Value> Parent;
130      NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
131      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
132      : Parent(*gw.graph, value) { }
133    };
134
135    template <typename _Value>
136    class EdgeMap : public _Graph::template EdgeMap<_Value> {
137    public:
138      typedef typename _Graph::template EdgeMap<_Value> Parent;
139      EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
140      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
141      : Parent(*gw.graph, value) { }
142    };
143
144  };
145
146  template <typename _Graph>
147  class GraphAdaptor :
148    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
149  public:
150    typedef _Graph Graph;
151    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
152  protected:
153    GraphAdaptor() : Parent() { }
154
155  public:
156    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
157  };
158
159  template <typename _Graph>
160  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
161  public:
162    typedef _Graph Graph;
163    typedef GraphAdaptorBase<_Graph> Parent;
164  protected:
165    RevGraphAdaptorBase() : Parent() { }
166  public:
167    typedef typename Parent::Node Node;
168    typedef typename Parent::Edge Edge;
169
170    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
171    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
172
173    void nextIn(Edge& i) const { Parent::nextOut(i); }
174    void nextOut(Edge& i) const { Parent::nextIn(i); }
175
176    Node source(const Edge& e) const { return Parent::target(e); }
177    Node target(const Edge& e) const { return Parent::source(e); }
178  };
179   
180
181  /// A graph adaptor which reverses the orientation of the edges.
182
183  ///\warning Graph adaptors are in even more experimental state than the other
184  ///parts of the lib. Use them at you own risk.
185  ///
186  /// Let \f$G=(V, A)\f$ be a directed graph and
187  /// suppose that a graph instange \c g of type
188  /// \c ListGraph implements \f$G\f$.
189  /// \code
190  /// ListGraph g;
191  /// \endcode
192  /// For each directed edge
193  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
194  /// reversing its orientation.
195  /// Then RevGraphAdaptor implements the graph structure with node-set
196  /// \f$V\f$ and edge-set
197  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
198  /// reversing the orientation of its edges. The following code shows how
199  /// such an instance can be constructed.
200  /// \code
201  /// RevGraphAdaptor<ListGraph> gw(g);
202  /// \endcode
203  ///\author Marton Makai
204  template<typename _Graph>
205  class RevGraphAdaptor :
206    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
207  public:
208    typedef _Graph Graph;
209    typedef IterableGraphExtender<
210      RevGraphAdaptorBase<_Graph> > Parent;
211  protected:
212    RevGraphAdaptor() { }
213  public:
214    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
215  };
216
217 
218  template <typename _Graph, typename NodeFilterMap,
219            typename EdgeFilterMap, bool checked = true>
220  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
221  public:
222    typedef _Graph Graph;
223    typedef GraphAdaptorBase<_Graph> Parent;
224  protected:
225    NodeFilterMap* node_filter_map;
226    EdgeFilterMap* edge_filter_map;
227    SubGraphAdaptorBase() : Parent(),
228                            node_filter_map(0), edge_filter_map(0) { }
229
230    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
231      node_filter_map=&_node_filter_map;
232    }
233    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
234      edge_filter_map=&_edge_filter_map;
235    }
236
237  public:
238
239    typedef typename Parent::Node Node;
240    typedef typename Parent::Edge Edge;
241
242    void first(Node& i) const {
243      Parent::first(i);
244      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
245    }
246
247    void first(Edge& i) const {
248      Parent::first(i);
249      while (i!=INVALID && (!(*edge_filter_map)[i]
250             || !(*node_filter_map)[Parent::source(i)]
251             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
252    }
253
254    void firstIn(Edge& i, const Node& n) const {
255      Parent::firstIn(i, n);
256      while (i!=INVALID && (!(*edge_filter_map)[i]
257             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
258    }
259
260    void firstOut(Edge& i, const Node& n) const {
261      Parent::firstOut(i, n);
262      while (i!=INVALID && (!(*edge_filter_map)[i]
263             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
264    }
265
266    void next(Node& i) const {
267      Parent::next(i);
268      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
269    }
270
271    void next(Edge& i) const {
272      Parent::next(i);
273      while (i!=INVALID && (!(*edge_filter_map)[i]
274             || !(*node_filter_map)[Parent::source(i)]
275             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
276    }
277
278    void nextIn(Edge& i) const {
279      Parent::nextIn(i);
280      while (i!=INVALID && (!(*edge_filter_map)[i]
281             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
282    }
283
284    void nextOut(Edge& i) const {
285      Parent::nextOut(i);
286      while (i!=INVALID && (!(*edge_filter_map)[i]
287             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
288    }
289
290    /// This function hides \c n in the graph, i.e. the iteration
291    /// jumps over it. This is done by simply setting the value of \c n 
292    /// to be false in the corresponding node-map.
293    void hide(const Node& n) const { node_filter_map->set(n, false); }
294
295    /// This function hides \c e in the graph, i.e. the iteration
296    /// jumps over it. This is done by simply setting the value of \c e 
297    /// to be false in the corresponding edge-map.
298    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
299
300    /// The value of \c n is set to be true in the node-map which stores
301    /// hide information. If \c n was hidden previuosly, then it is shown
302    /// again
303     void unHide(const Node& n) const { node_filter_map->set(n, true); }
304
305    /// The value of \c e is set to be true in the edge-map which stores
306    /// hide information. If \c e was hidden previuosly, then it is shown
307    /// again
308    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
309
310    /// Returns true if \c n is hidden.
311    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
312
313    /// Returns true if \c n is hidden.
314    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
315
316    typedef False NodeNumTag;
317    typedef False EdgeNumTag;
318  };
319
320  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
321  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
322    : public GraphAdaptorBase<_Graph> {
323  public:
324    typedef _Graph Graph;
325    typedef GraphAdaptorBase<_Graph> Parent;
326  protected:
327    NodeFilterMap* node_filter_map;
328    EdgeFilterMap* edge_filter_map;
329    SubGraphAdaptorBase() : Parent(),
330                            node_filter_map(0), edge_filter_map(0) { }
331
332    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
333      node_filter_map=&_node_filter_map;
334    }
335    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
336      edge_filter_map=&_edge_filter_map;
337    }
338
339  public:
340
341    typedef typename Parent::Node Node;
342    typedef typename Parent::Edge Edge;
343
344    void first(Node& i) const {
345      Parent::first(i);
346      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
347    }
348
349    void first(Edge& i) const {
350      Parent::first(i);
351      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
352    }
353
354    void firstIn(Edge& i, const Node& n) const {
355      Parent::firstIn(i, n);
356      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
357    }
358
359    void firstOut(Edge& i, const Node& n) const {
360      Parent::firstOut(i, n);
361      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
362    }
363
364    void next(Node& i) const {
365      Parent::next(i);
366      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
367    }
368    void next(Edge& i) const {
369      Parent::next(i);
370      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
371    }
372    void nextIn(Edge& i) const {
373      Parent::nextIn(i);
374      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
375    }
376
377    void nextOut(Edge& i) const {
378      Parent::nextOut(i);
379      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
380    }
381
382    /// This function hides \c n in the graph, i.e. the iteration
383    /// jumps over it. This is done by simply setting the value of \c n 
384    /// to be false in the corresponding node-map.
385    void hide(const Node& n) const { node_filter_map->set(n, false); }
386
387    /// This function hides \c e in the graph, i.e. the iteration
388    /// jumps over it. This is done by simply setting the value of \c e 
389    /// to be false in the corresponding edge-map.
390    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
391
392    /// The value of \c n is set to be true in the node-map which stores
393    /// hide information. If \c n was hidden previuosly, then it is shown
394    /// again
395     void unHide(const Node& n) const { node_filter_map->set(n, true); }
396
397    /// The value of \c e is set to be true in the edge-map which stores
398    /// hide information. If \c e was hidden previuosly, then it is shown
399    /// again
400    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
401
402    /// Returns true if \c n is hidden.
403    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
404
405    /// Returns true if \c n is hidden.
406    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
407
408    typedef False NodeNumTag;
409    typedef False EdgeNumTag;
410  };
411
412  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
413   
414  \warning Graph adaptors are in even more experimental state than the other
415  parts of the lib. Use them at you own risk.
416 
417  SubGraphAdaptor shows the graph with filtered node-set and
418  edge-set. If the \c checked parameter is true then it filters the edgeset
419  to do not get invalid edges without source or target.
420  Let \f$G=(V, A)\f$ be a directed graph
421  and suppose that the graph instance \c g of type ListGraph implements
422  \f$G\f$.
423  Let moreover \f$b_V\f$ and
424  \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
425  SubGraphAdaptor<...>::NodeIt iterates
426  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
427  SubGraphAdaptor<...>::EdgeIt iterates
428  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
429  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
430  only on edges leaving and entering a specific node which have true value.
431
432  If the \c checked template parameter is false then we have to note that
433  the node-iterator cares only the filter on the node-set, and the
434  edge-iterator cares only the filter on the edge-set. This way the edge-map
435  should filter all edges which's source or target is filtered by the
436  node-filter.
437  \code
438  typedef ListGraph Graph;
439  Graph g;
440  typedef Graph::Node Node;
441  typedef Graph::Edge Edge;
442  Node u=g.addNode(); //node of id 0
443  Node v=g.addNode(); //node of id 1
444  Node e=g.addEdge(u, v); //edge of id 0
445  Node f=g.addEdge(v, u); //edge of id 1
446  Graph::NodeMap<bool> nm(g, true);
447  nm.set(u, false);
448  Graph::EdgeMap<bool> em(g, true);
449  em.set(e, false);
450  typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
451  SubGW gw(g, nm, em);
452  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
453  std::cout << ":-)" << std::endl;
454  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
455  \endcode
456  The output of the above code is the following.
457  \code
458  1
459  :-)
460  1
461  \endcode
462  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
463  \c Graph::Node that is why \c g.id(n) can be applied.
464
465  For other examples see also the documentation of NodeSubGraphAdaptor and
466  EdgeSubGraphAdaptor.
467
468  \author Marton Makai
469  */
470  template<typename _Graph, typename NodeFilterMap,
471           typename EdgeFilterMap, bool checked = true>
472  class SubGraphAdaptor :
473    public IterableGraphExtender<
474    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
475  public:
476    typedef _Graph Graph;
477    typedef IterableGraphExtender<
478      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
479  protected:
480    SubGraphAdaptor() { }
481  public:
482    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
483                    EdgeFilterMap& _edge_filter_map) {
484      setGraph(_graph);
485      setNodeFilterMap(_node_filter_map);
486      setEdgeFilterMap(_edge_filter_map);
487    }
488  };
489
490
491
492  /*! \brief An adaptor for hiding nodes from a graph.
493
494  \warning Graph adaptors are in even more experimental state than the other
495  parts of the lib. Use them at you own risk.
496 
497  An adaptor for hiding nodes from a graph.
498  This adaptor specializes SubGraphAdaptor in the way that only the node-set
499  can be filtered. In usual case the checked parameter is true, we get the
500  induced subgraph. But if the checked parameter is false then we can only
501  filter only isolated nodes.
502  \author Marton Makai
503  */
504  template<typename Graph, typename NodeFilterMap, bool checked = true>
505  class NodeSubGraphAdaptor :
506    public SubGraphAdaptor<Graph, NodeFilterMap,
507                           ConstMap<typename Graph::Edge,bool>, checked> {
508  public:
509    typedef SubGraphAdaptor<Graph, NodeFilterMap,
510                            ConstMap<typename Graph::Edge,bool> > Parent;
511  protected:
512    ConstMap<typename Graph::Edge, bool> const_true_map;
513  public:
514    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
515      Parent(), const_true_map(true) {
516      Parent::setGraph(_graph);
517      Parent::setNodeFilterMap(_node_filter_map);
518      Parent::setEdgeFilterMap(const_true_map);
519    }
520  };
521
522
523  /*! \brief An adaptor for hiding edges from a graph.
524
525  \warning Graph adaptors are in even more experimental state than the other
526  parts of the lib. Use them at you own risk.
527 
528  An adaptor for hiding edges from a graph.
529  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
530  can be filtered. The usefulness of this adaptor is demonstrated in the
531  problem of searching a maximum number of edge-disjoint shortest paths
532  between
533  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
534  non-negative edge-lengths. Note that
535  the comprehension of the presented solution
536  need's some elementary knowledge from combinatorial optimization.
537
538  If a single shortest path is to be
539  searched between \c s and \c t, then this can be done easily by
540  applying the Dijkstra algorithm. What happens, if a maximum number of
541  edge-disjoint shortest paths is to be computed. It can be proved that an
542  edge can be in a shortest path if and only if it is tight with respect to
543  the potential function computed by Dijkstra. Moreover, any path containing
544  only such edges is a shortest one. Thus we have to compute a maximum number
545  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
546  all the tight edges. The computation will be demonstrated on the following
547  graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
548  The full source code is available in \ref sub_graph_adaptor_demo.cc.
549  If you are interested in more demo programs, you can use
550  \ref dim_to_dot.cc to generate .dot files from dimacs files.
551  The .dot file of the following figure was generated by 
552  the demo program \ref dim_to_dot.cc.
553
554  \dot
555  digraph lemon_dot_example {
556  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
557  n0 [ label="0 (s)" ];
558  n1 [ label="1" ];
559  n2 [ label="2" ];
560  n3 [ label="3" ];
561  n4 [ label="4" ];
562  n5 [ label="5" ];
563  n6 [ label="6 (t)" ];
564  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
565  n5 ->  n6 [ label="9, length:4" ];
566  n4 ->  n6 [ label="8, length:2" ];
567  n3 ->  n5 [ label="7, length:1" ];
568  n2 ->  n5 [ label="6, length:3" ];
569  n2 ->  n6 [ label="5, length:5" ];
570  n2 ->  n4 [ label="4, length:2" ];
571  n1 ->  n4 [ label="3, length:3" ];
572  n0 ->  n3 [ label="2, length:1" ];
573  n0 ->  n2 [ label="1, length:2" ];
574  n0 ->  n1 [ label="0, length:3" ];
575  }
576  \enddot
577
578  \code
579  Graph g;
580  Node s, t;
581  LengthMap length(g);
582
583  readDimacs(std::cin, g, length, s, t);
584
585  cout << "edges with lengths (of form id, source--length->target): " << endl;
586  for(EdgeIt e(g); e!=INVALID; ++e)
587    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
588         << length[e] << "->" << g.id(g.target(e)) << endl;
589
590  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
591  \endcode
592  Next, the potential function is computed with Dijkstra.
593  \code
594  typedef Dijkstra<Graph, LengthMap> Dijkstra;
595  Dijkstra dijkstra(g, length);
596  dijkstra.run(s);
597  \endcode
598  Next, we consrtruct a map which filters the edge-set to the tight edges.
599  \code
600  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
601    TightEdgeFilter;
602  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
603 
604  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
605  SubGW gw(g, tight_edge_filter);
606  \endcode
607  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
608  with a max flow algorithm Preflow.
609  \code
610  ConstMap<Edge, int> const_1_map(1);
611  Graph::EdgeMap<int> flow(g, 0);
612
613  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
614    preflow(gw, s, t, const_1_map, flow);
615  preflow.run();
616  \endcode
617  Last, the output is:
618  \code 
619  cout << "maximum number of edge-disjoint shortest path: "
620       << preflow.flowValue() << endl;
621  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
622       << endl;
623  for(EdgeIt e(g); e!=INVALID; ++e)
624    if (flow[e])
625      cout << " " << g.id(g.source(e)) << "--"
626           << length[e] << "->" << g.id(g.target(e)) << endl;
627  \endcode
628  The program has the following (expected :-)) output:
629  \code
630  edges with lengths (of form id, source--length->target):
631   9, 5--4->6
632   8, 4--2->6
633   7, 3--1->5
634   6, 2--3->5
635   5, 2--5->6
636   4, 2--2->4
637   3, 1--3->4
638   2, 0--1->3
639   1, 0--2->2
640   0, 0--3->1
641  s: 0 t: 6
642  maximum number of edge-disjoint shortest path: 2
643  edges of the maximum number of edge-disjoint shortest s-t paths:
644   9, 5--4->6
645   8, 4--2->6
646   7, 3--1->5
647   4, 2--2->4
648   2, 0--1->3
649   1, 0--2->2
650  \endcode
651
652  \author Marton Makai
653  */
654  template<typename Graph, typename EdgeFilterMap>
655  class EdgeSubGraphAdaptor :
656    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
657                           EdgeFilterMap, false> {
658  public:
659    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
660                            EdgeFilterMap, false> Parent;
661  protected:
662    ConstMap<typename Graph::Node, bool> const_true_map;
663  public:
664    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
665      Parent(), const_true_map(true) {
666      Parent::setGraph(_graph);
667      Parent::setNodeFilterMap(const_true_map);
668      Parent::setEdgeFilterMap(_edge_filter_map);
669    }
670  };
671
672  template <typename _Graph>
673  class UndirGraphAdaptorBase :
674    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
675  public:
676    typedef _Graph Graph;
677    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
678  protected:
679    UndirGraphAdaptorBase() : Parent() { }
680  public:
681    typedef typename Parent::UndirEdge UndirEdge;
682    typedef typename Parent::Edge Edge;
683   
684    template <typename T>
685    class EdgeMap {
686    protected:
687      const UndirGraphAdaptorBase<_Graph>* g;
688      template <typename TT> friend class EdgeMap;
689      typename _Graph::template EdgeMap<T> forward_map, backward_map;
690    public:
691      typedef T Value;
692      typedef Edge Key;
693     
694      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
695        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
696
697      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
698        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
699     
700      void set(Edge e, T a) {
701        if (g->direction(e))
702          forward_map.set(e, a);
703        else
704          backward_map.set(e, a);
705      }
706
707      T operator[](Edge e) const {
708        if (g->direction(e))
709          return forward_map[e];
710        else
711          return backward_map[e];
712      }
713    };
714       
715    template <typename T>
716    class UndirEdgeMap {
717      template <typename TT> friend class UndirEdgeMap;
718      typename _Graph::template EdgeMap<T> map;
719    public:
720      typedef T Value;
721      typedef UndirEdge Key;
722     
723      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
724        map(*(g.graph)) { }
725
726      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
727        map(*(g.graph), a) { }
728     
729      void set(UndirEdge e, T a) {
730        map.set(e, a);
731      }
732
733      T operator[](UndirEdge e) const {
734        return map[e];
735      }
736    };
737     
738  };
739
740  /// \brief An undirected graph is made from a directed graph by an adaptor
741  ///
742  /// Undocumented, untested!!!
743  /// If somebody knows nice demo application, let's polulate it.
744  ///
745  /// \author Marton Makai
746  template<typename _Graph>
747  class UndirGraphAdaptor :
748    public IterableUndirGraphExtender<
749    UndirGraphAdaptorBase<_Graph> > {
750  public:
751    typedef _Graph Graph;
752    typedef IterableUndirGraphExtender<
753      UndirGraphAdaptorBase<_Graph> > Parent;
754  protected:
755    UndirGraphAdaptor() { }
756  public:
757    UndirGraphAdaptor(_Graph& _graph) {
758      setGraph(_graph);
759    }
760  };
761
762 
763  template <typename _Graph,
764            typename ForwardFilterMap, typename BackwardFilterMap>
765  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
766  public:
767    typedef _Graph Graph;
768    typedef GraphAdaptorBase<_Graph> Parent;
769  protected:
770    ForwardFilterMap* forward_filter;
771    BackwardFilterMap* backward_filter;
772    SubBidirGraphAdaptorBase() : Parent(),
773                                 forward_filter(0), backward_filter(0) { }
774
775    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
776      forward_filter=&_forward_filter;
777    }
778    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
779      backward_filter=&_backward_filter;
780    }
781
782  public:
783//     SubGraphAdaptorBase(Graph& _graph,
784//                      NodeFilterMap& _node_filter_map,
785//                      EdgeFilterMap& _edge_filter_map) :
786//       Parent(&_graph),
787//       node_filter_map(&node_filter_map),
788//       edge_filter_map(&edge_filter_map) { }
789
790    typedef typename Parent::Node Node;
791    typedef typename _Graph::Edge GraphEdge;
792    template <typename T> class EdgeMap;
793    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
794    /// _Graph::Edge. It contains an extra bool flag which is true
795    /// if and only if the
796    /// edge is the backward version of the original edge.
797    class Edge : public _Graph::Edge {
798      friend class SubBidirGraphAdaptorBase<
799        Graph, ForwardFilterMap, BackwardFilterMap>;
800      template<typename T> friend class EdgeMap;
801    protected:
802      bool backward; //true, iff backward
803    public:
804      Edge() { }
805      /// \todo =false is needed, or causes problems?
806      /// If \c _backward is false, then we get an edge corresponding to the
807      /// original one, otherwise its oppositely directed pair is obtained.
808      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
809        _Graph::Edge(e), backward(_backward) { }
810      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
811      bool operator==(const Edge& v) const {
812        return (this->backward==v.backward &&
813                static_cast<typename _Graph::Edge>(*this)==
814                static_cast<typename _Graph::Edge>(v));
815      }
816      bool operator!=(const Edge& v) const {
817        return (this->backward!=v.backward ||
818                static_cast<typename _Graph::Edge>(*this)!=
819                static_cast<typename _Graph::Edge>(v));
820      }
821    };
822
823    void first(Node& i) const {
824      Parent::first(i);
825    }
826
827    void first(Edge& i) const {
828      Parent::first(i);
829      i.backward=false;
830      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
831             !(*forward_filter)[i]) Parent::next(i);
832      if (*static_cast<GraphEdge*>(&i)==INVALID) {
833        Parent::first(i);
834        i.backward=true;
835        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
836               !(*backward_filter)[i]) Parent::next(i);
837      }
838    }
839
840    void firstIn(Edge& i, const Node& n) const {
841      Parent::firstIn(i, n);
842      i.backward=false;
843      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
844             !(*forward_filter)[i]) Parent::nextIn(i);
845      if (*static_cast<GraphEdge*>(&i)==INVALID) {
846        Parent::firstOut(i, n);
847        i.backward=true;
848        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
849               !(*backward_filter)[i]) Parent::nextOut(i);
850      }
851    }
852
853    void firstOut(Edge& i, const Node& n) const {
854      Parent::firstOut(i, n);
855      i.backward=false;
856      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
857             !(*forward_filter)[i]) Parent::nextOut(i);
858      if (*static_cast<GraphEdge*>(&i)==INVALID) {
859        Parent::firstIn(i, n);
860        i.backward=true;
861        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
862               !(*backward_filter)[i]) Parent::nextIn(i);
863      }
864    }
865
866    void next(Node& i) const {
867      Parent::next(i);
868    }
869
870    void next(Edge& i) const {
871      if (!(i.backward)) {
872        Parent::next(i);
873        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
874               !(*forward_filter)[i]) Parent::next(i);
875        if (*static_cast<GraphEdge*>(&i)==INVALID) {
876          Parent::first(i);
877          i.backward=true;
878          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
879                 !(*backward_filter)[i]) Parent::next(i);
880        }
881      } else {
882        Parent::next(i);
883        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
884               !(*backward_filter)[i]) Parent::next(i);
885      }
886    }
887
888    void nextIn(Edge& i) const {
889      if (!(i.backward)) {
890        Node n=Parent::target(i);
891        Parent::nextIn(i);
892        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
893               !(*forward_filter)[i]) Parent::nextIn(i);
894        if (*static_cast<GraphEdge*>(&i)==INVALID) {
895          Parent::firstOut(i, n);
896          i.backward=true;
897          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
898                 !(*backward_filter)[i]) Parent::nextOut(i);
899        }
900      } else {
901        Parent::nextOut(i);
902        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
903               !(*backward_filter)[i]) Parent::nextOut(i);
904      }
905    }
906
907    void nextOut(Edge& i) const {
908      if (!(i.backward)) {
909        Node n=Parent::source(i);
910        Parent::nextOut(i);
911        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
912               !(*forward_filter)[i]) Parent::nextOut(i);
913        if (*static_cast<GraphEdge*>(&i)==INVALID) {
914          Parent::firstIn(i, n);
915          i.backward=true;
916          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
917                 !(*backward_filter)[i]) Parent::nextIn(i);
918        }
919      } else {
920        Parent::nextIn(i);
921        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
922               !(*backward_filter)[i]) Parent::nextIn(i);
923      }
924    }
925
926    Node source(Edge e) const {
927      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
928    Node target(Edge e) const {
929      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
930
931    /// Gives back the opposite edge.
932    Edge opposite(const Edge& e) const {
933      Edge f=e;
934      f.backward=!f.backward;
935      return f;
936    }
937
938    /// \warning This is a linear time operation and works only if
939    /// \c Graph::EdgeIt is defined.
940    /// \todo hmm
941    int edgeNum() const {
942      int i=0;
943      Edge e;
944      for (first(e); e!=INVALID; next(e)) ++i;
945      return i;
946    }
947
948    bool forward(const Edge& e) const { return !e.backward; }
949    bool backward(const Edge& e) const { return e.backward; }
950
951    template <typename T>
952    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
953    /// _Graph::EdgeMap one for the forward edges and
954    /// one for the backward edges.
955    class EdgeMap {
956      template <typename TT> friend class EdgeMap;
957      typename _Graph::template EdgeMap<T> forward_map, backward_map;
958    public:
959      typedef T Value;
960      typedef Edge Key;
961
962      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
963              ForwardFilterMap, BackwardFilterMap>& g) :
964        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
965
966      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
967              ForwardFilterMap, BackwardFilterMap>& g, T a) :
968        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
969     
970      void set(Edge e, T a) {
971        if (!e.backward)
972          forward_map.set(e, a);
973        else
974          backward_map.set(e, a);
975      }
976
977//       typename _Graph::template EdgeMap<T>::ConstReference
978//       operator[](Edge e) const {
979//      if (!e.backward)
980//        return forward_map[e];
981//      else
982//        return backward_map[e];
983//       }
984
985//      typename _Graph::template EdgeMap<T>::Reference
986      T operator[](Edge e) const {
987        if (!e.backward)
988          return forward_map[e];
989        else
990          return backward_map[e];
991      }
992
993      void update() {
994        forward_map.update();
995        backward_map.update();
996      }
997    };
998
999  };
1000
1001
1002  ///\brief An adaptor for composing a subgraph of a
1003  /// bidirected graph made from a directed one.
1004  ///
1005  /// An adaptor for composing a subgraph of a
1006  /// bidirected graph made from a directed one.
1007  ///
1008  ///\warning Graph adaptors are in even more experimental state than the other
1009  ///parts of the lib. Use them at you own risk.
1010  ///
1011  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1012  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1013  /// reversing its orientation. We are given moreover two bool valued
1014  /// maps on the edge-set,
1015  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1016  /// SubBidirGraphAdaptor implements the graph structure with node-set
1017  /// \f$V\f$ and edge-set
1018  /// \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$.
1019  /// The purpose of writing + instead of union is because parallel
1020  /// edges can arise. (Similarly, antiparallel edges also can arise).
1021  /// In other words, a subgraph of the bidirected graph obtained, which
1022  /// is given by orienting the edges of the original graph in both directions.
1023  /// As the oppositely directed edges are logically different,
1024  /// the maps are able to attach different values for them.
1025  ///
1026  /// An example for such a construction is \c RevGraphAdaptor where the
1027  /// forward_filter is everywhere false and the backward_filter is
1028  /// everywhere true. We note that for sake of efficiency,
1029  /// \c RevGraphAdaptor is implemented in a different way.
1030  /// But BidirGraphAdaptor is obtained from
1031  /// SubBidirGraphAdaptor by considering everywhere true
1032  /// valued maps both for forward_filter and backward_filter.
1033  ///
1034  /// The most important application of SubBidirGraphAdaptor
1035  /// is ResGraphAdaptor, which stands for the residual graph in directed
1036  /// flow and circulation problems.
1037  /// As adaptors usually, the SubBidirGraphAdaptor implements the
1038  /// above mentioned graph structure without its physical storage,
1039  /// that is the whole stuff is stored in constant memory.
1040  template<typename _Graph,
1041           typename ForwardFilterMap, typename BackwardFilterMap>
1042  class SubBidirGraphAdaptor :
1043    public IterableGraphExtender<
1044    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1045  public:
1046    typedef _Graph Graph;
1047    typedef IterableGraphExtender<
1048      SubBidirGraphAdaptorBase<
1049      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1050  protected:
1051    SubBidirGraphAdaptor() { }
1052  public:
1053    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1054                         BackwardFilterMap& _backward_filter) {
1055      setGraph(_graph);
1056      setForwardFilterMap(_forward_filter);
1057      setBackwardFilterMap(_backward_filter);
1058    }
1059  };
1060
1061
1062
1063  ///\brief An adaptor for composing bidirected graph from a directed one.
1064  ///
1065  ///\warning Graph adaptors are in even more experimental state than the other
1066  ///parts of the lib. Use them at you own risk.
1067  ///
1068  /// An adaptor for composing bidirected graph from a directed one.
1069  /// A bidirected graph is composed over the directed one without physical
1070  /// storage. As the oppositely directed edges are logically different ones
1071  /// the maps are able to attach different values for them.
1072  template<typename Graph>
1073  class BidirGraphAdaptor :
1074    public SubBidirGraphAdaptor<
1075    Graph,
1076    ConstMap<typename Graph::Edge, bool>,
1077    ConstMap<typename Graph::Edge, bool> > {
1078  public:
1079    typedef  SubBidirGraphAdaptor<
1080      Graph,
1081      ConstMap<typename Graph::Edge, bool>,
1082      ConstMap<typename Graph::Edge, bool> > Parent;
1083  protected:
1084    ConstMap<typename Graph::Edge, bool> cm;
1085
1086    BidirGraphAdaptor() : Parent(), cm(true) {
1087      Parent::setForwardFilterMap(cm);
1088      Parent::setBackwardFilterMap(cm);
1089    }
1090  public:
1091    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1092      Parent::setGraph(_graph);
1093      Parent::setForwardFilterMap(cm);
1094      Parent::setBackwardFilterMap(cm);
1095    }
1096
1097    int edgeNum() const {
1098      return 2*this->graph->edgeNum();
1099    }
1100  };
1101
1102
1103  template<typename Graph, typename Number,
1104           typename CapacityMap, typename FlowMap>
1105  class ResForwardFilter {
1106    //    const Graph* graph;
1107    const CapacityMap* capacity;
1108    const FlowMap* flow;
1109  public:
1110    ResForwardFilter(/*const Graph& _graph, */
1111                     const CapacityMap& _capacity, const FlowMap& _flow) :
1112      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1113    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1114    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1115    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1116    bool operator[](const typename Graph::Edge& e) const {
1117      return (Number((*flow)[e]) < Number((*capacity)[e]));
1118    }
1119  };
1120
1121  template<typename Graph, typename Number,
1122           typename CapacityMap, typename FlowMap>
1123  class ResBackwardFilter {
1124    const CapacityMap* capacity;
1125    const FlowMap* flow;
1126  public:
1127    ResBackwardFilter(/*const Graph& _graph,*/
1128                      const CapacityMap& _capacity, const FlowMap& _flow) :
1129      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1130    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1131    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1132    void setFlow(const FlowMap& _flow) { flow=&_flow; }
1133    bool operator[](const typename Graph::Edge& e) const {
1134      return (Number(0) < Number((*flow)[e]));
1135    }
1136  };
1137
1138 
1139  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1140
1141  An adaptor for composing the residual graph for directed flow and circulation problems.
1142  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1143  number type. Let moreover
1144  \f$f,c:A\to F\f$, be functions on the edge-set.
1145  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1146  and \f$c\f$ for a capacity function.   
1147  Suppose that a graph instange \c g of type
1148  \c ListGraph implements \f$G\f$.
1149  \code
1150  ListGraph g;
1151  \endcode
1152  Then RevGraphAdaptor implements the graph structure with node-set
1153  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1154  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1155  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1156  i.e. the so called residual graph.
1157  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1158  multilicities are counted, i.e. if an edge is in both
1159  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1160  appears twice.
1161  The following code shows how
1162  such an instance can be constructed.
1163  \code
1164  typedef ListGraph Graph;
1165  Graph::EdgeMap<int> f(g);
1166  Graph::EdgeMap<int> c(g);
1167  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1168  \endcode
1169  \author Marton Makai
1170  */
1171  template<typename Graph, typename Number,
1172           typename CapacityMap, typename FlowMap>
1173  class ResGraphAdaptor :
1174    public SubBidirGraphAdaptor<
1175    Graph,
1176    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1177    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1178  public:
1179    typedef SubBidirGraphAdaptor<
1180      Graph,
1181      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1182      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1183  protected:
1184    const CapacityMap* capacity;
1185    FlowMap* flow;
1186    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1187    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1188    ResGraphAdaptor() : Parent(),
1189                        capacity(0), flow(0) { }
1190    void setCapacityMap(const CapacityMap& _capacity) {
1191      capacity=&_capacity;
1192      forward_filter.setCapacity(_capacity);
1193      backward_filter.setCapacity(_capacity);
1194    }
1195    void setFlowMap(FlowMap& _flow) {
1196      flow=&_flow;
1197      forward_filter.setFlow(_flow);
1198      backward_filter.setFlow(_flow);
1199    }
1200  public:
1201    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1202                       FlowMap& _flow) :
1203      Parent(), capacity(&_capacity), flow(&_flow),
1204      forward_filter(/*_graph,*/ _capacity, _flow),
1205      backward_filter(/*_graph,*/ _capacity, _flow) {
1206      Parent::setGraph(_graph);
1207      Parent::setForwardFilterMap(forward_filter);
1208      Parent::setBackwardFilterMap(backward_filter);
1209    }
1210
1211    typedef typename Parent::Edge Edge;
1212
1213    void augment(const Edge& e, Number a) const {
1214      if (Parent::forward(e)) 
1215        flow->set(e, (*flow)[e]+a);
1216      else 
1217        flow->set(e, (*flow)[e]-a);
1218    }
1219
1220    /// \brief Residual capacity map.
1221    ///
1222    /// In generic residual graphs the residual capacity can be obtained
1223    /// as a map.
1224    class ResCap {
1225    protected:
1226      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1227    public:
1228      typedef Number Value;
1229      typedef Edge Key;
1230      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1231             _res_graph) : res_graph(&_res_graph) { }
1232      Number operator[](const Edge& e) const {
1233        if (res_graph->forward(e))
1234          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1235        else
1236          return (*(res_graph->flow))[e];
1237      }
1238    };
1239
1240    //    KEEP_MAPS(Parent, ResGraphAdaptor);
1241  };
1242
1243
1244
1245  template <typename _Graph, typename FirstOutEdgesMap>
1246  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1247  public:
1248    typedef _Graph Graph;
1249    typedef GraphAdaptorBase<_Graph> Parent;
1250  protected:
1251    FirstOutEdgesMap* first_out_edges;
1252    ErasingFirstGraphAdaptorBase() : Parent(),
1253                                     first_out_edges(0) { }
1254
1255    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1256      first_out_edges=&_first_out_edges;
1257    }
1258
1259  public:
1260
1261    typedef typename Parent::Node Node;
1262    typedef typename Parent::Edge Edge;
1263
1264    void firstOut(Edge& i, const Node& n) const {
1265      i=(*first_out_edges)[n];
1266    }
1267
1268    void erase(const Edge& e) const {
1269      Node n=source(e);
1270      Edge f=e;
1271      Parent::nextOut(f);
1272      first_out_edges->set(n, f);
1273    }   
1274  };
1275
1276
1277  /// For blocking flows.
1278
1279  ///\warning Graph adaptors are in even more experimental state than the other
1280  ///parts of the lib. Use them at you own risk.
1281  ///
1282  /// This graph adaptor is used for on-the-fly
1283  /// Dinits blocking flow computations.
1284  /// For each node, an out-edge is stored which is used when the
1285  /// \code
1286  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1287  /// \endcode
1288  /// is called.
1289  ///
1290  /// \author Marton Makai
1291  template <typename _Graph, typename FirstOutEdgesMap>
1292  class ErasingFirstGraphAdaptor :
1293    public IterableGraphExtender<
1294    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1295  public:
1296    typedef _Graph Graph;
1297    typedef IterableGraphExtender<
1298      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1299    ErasingFirstGraphAdaptor(Graph& _graph,
1300                             FirstOutEdgesMap& _first_out_edges) {
1301      setGraph(_graph);
1302      setFirstOutEdgesMap(_first_out_edges);
1303    }
1304
1305  };
1306
1307  template <typename _Graph>
1308  class SplitGraphAdaptorBase
1309    : public GraphAdaptorBase<_Graph> {
1310  public:
1311    typedef GraphAdaptorBase<_Graph> Parent;
1312
1313    class Node;
1314    class Edge;
1315    template <typename T> class NodeMap;
1316    template <typename T> class EdgeMap;
1317   
1318
1319    class Node : public Parent::Node {
1320      friend class SplitGraphAdaptorBase;
1321      template <typename T> friend class NodeMap;
1322      typedef typename Parent::Node NodeParent;
1323    private:
1324
1325      bool entry;
1326      Node(typename Parent::Node _node, bool _entry)
1327        : Parent::Node(_node), entry(_entry) {}
1328     
1329    public:
1330      Node() {}
1331      Node(Invalid) : NodeParent(INVALID), entry(true) {}
1332
1333      bool operator==(const Node& node) const {
1334        return NodeParent::operator==(node) && entry == node.entry;
1335      }
1336     
1337      bool operator!=(const Node& node) const {
1338        return !(*this == node);
1339      }
1340     
1341      bool operator<(const Node& node) const {
1342        return NodeParent::operator<(node) ||
1343          (NodeParent::operator==(node) && entry < node.entry);
1344      }
1345    };
1346
1347    /// \todo May we want VARIANT/union type
1348    class Edge : public Parent::Edge {
1349      friend class SplitGraphAdaptorBase;
1350      template <typename T> friend class EdgeMap;
1351    private:
1352      typedef typename Parent::Edge EdgeParent;
1353      typedef typename Parent::Node NodeParent;
1354      NodeParent bind;
1355
1356      Edge(const EdgeParent& edge, const NodeParent& node)
1357        : EdgeParent(edge), bind(node) {}
1358    public:
1359      Edge() {}
1360      Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1361
1362      bool operator==(const Edge& edge) const {
1363        return EdgeParent::operator==(edge) && bind == edge.bind;
1364      }
1365     
1366      bool operator!=(const Edge& edge) const {
1367        return !(*this == edge);
1368      }
1369     
1370      bool operator<(const Edge& edge) const {
1371        return EdgeParent::operator<(edge) ||
1372          (EdgeParent::operator==(edge) && bind < edge.bind);
1373      }
1374    };
1375
1376    void first(Node& node) const {
1377      Parent::first(node);
1378      node.entry = true;
1379    }
1380
1381    void next(Node& node) const {
1382      if (node.entry) {
1383        node.entry = false;
1384      } else {
1385        node.entry = true;
1386        Parent::next(node);
1387      }
1388    }
1389
1390    void first(Edge& edge) const {
1391      Parent::first(edge);
1392      if ((typename Parent::Edge&)edge == INVALID) {
1393        Parent::first(edge.bind);
1394      } else {
1395        edge.bind = INVALID;
1396      }
1397    }
1398
1399    void next(Edge& edge) const {
1400      if ((typename Parent::Edge&)edge != INVALID) {
1401        Parent::next(edge);
1402        if ((typename Parent::Edge&)edge == INVALID) {
1403          Parent::first(edge.bind);
1404        }
1405      } else {
1406        Parent::next(edge.bind);
1407      }     
1408    }
1409
1410    void firstIn(Edge& edge, const Node& node) const {
1411      if (node.entry) {
1412        Parent::firstIn(edge, node);
1413        edge.bind = INVALID;
1414      } else {
1415        (typename Parent::Edge&)edge = INVALID;
1416        edge.bind = node;
1417      }
1418    }
1419
1420    void nextIn(Edge& edge) const {
1421      if ((typename Parent::Edge&)edge != INVALID) {
1422        Parent::nextIn(edge);
1423      } else {
1424        edge.bind = INVALID;
1425      }     
1426    }
1427
1428    void firstOut(Edge& edge, const Node& node) const {
1429      if (!node.entry) {
1430        Parent::firstOut(edge, node);
1431        edge.bind = INVALID;
1432      } else {
1433        (typename Parent::Edge&)edge = INVALID;
1434        edge.bind = node;
1435      }
1436    }
1437
1438    void nextOut(Edge& edge) const {
1439      if ((typename Parent::Edge&)edge != INVALID) {
1440        Parent::nextOut(edge);
1441      } else {
1442        edge.bind = INVALID;
1443      }
1444    }
1445
1446    Node source(const Edge& edge) const {
1447      if ((typename Parent::Edge&)edge != INVALID) {
1448        return Node(Parent::source(edge), false);
1449      } else {
1450        return Node(edge.bind, true);
1451      }
1452    }
1453
1454    Node target(const Edge& edge) const {
1455      if ((typename Parent::Edge&)edge != INVALID) {
1456        return Node(Parent::target(edge), true);
1457      } else {
1458        return Node(edge.bind, false);
1459      }
1460    }
1461
1462    static bool entryNode(const Node& node) {
1463      return node.entry;
1464    }
1465
1466    static bool exitNode(const Node& node) {
1467      return !node.entry;
1468    }
1469
1470    static Node getEntry(const typename Parent::Node& node) {
1471      return Node(node, true);
1472    }
1473
1474    static Node getExit(const typename Parent::Node& node) {
1475      return Node(node, false);
1476    }
1477
1478    static bool originalEdge(const Edge& edge) {
1479      return (typename Parent::Edge&)edge != INVALID;
1480    }
1481
1482    static bool bindingEdge(const Edge& edge) {
1483      return edge.bind != INVALID;
1484    }
1485
1486    static Node getBindedNode(const Edge& edge) {
1487      return edge.bind;
1488    }
1489
1490    int nodeNum() const {
1491      return Parent::nodeNum() * 2;
1492    }
1493
1494    typedef CompileTimeAnd<typename Parent::NodeNumTag,
1495                           typename Parent::EdgeNumTag> EdgeNumTag;
1496   
1497    int edgeNum() const {
1498      return Parent::edgeNum() + Parent::nodeNum();
1499    }
1500
1501    Edge findEdge(const Node& source, const Node& target,
1502                  const Edge& prev = INVALID) const {
1503      if (exitNode(source) && entryNode(target)) {
1504        return Parent::findEdge(source, target, prev);
1505      } else {
1506        if (prev == INVALID && entryNode(source) && exitNode(target) &&
1507            (typename Parent::Node&)source == (typename Parent::Node&)target) {
1508          return Edge(INVALID, source);
1509        } else {
1510          return INVALID;
1511        }
1512      }
1513    }
1514   
1515    template <typename T>
1516    class NodeMap : public MapBase<Node, T> {
1517      typedef typename Parent::template NodeMap<T> NodeImpl;
1518    public:
1519      NodeMap(const SplitGraphAdaptorBase& _graph)
1520        : entry(_graph), exit(_graph) {}
1521      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1522        : entry(_graph, t), exit(_graph, t) {}
1523     
1524      void set(const Node& key, const T& val) {
1525        if (key.entry) { entry.set(key, val); }
1526        else {exit.set(key, val); }
1527      }
1528     
1529      typename ReferenceMapTraits<NodeImpl>::Reference
1530      operator[](const Node& key) {
1531        if (key.entry) { return entry[key]; }
1532        else { return exit[key]; }
1533      }
1534
1535      T operator[](const Node& key) const {
1536        if (key.entry) { return entry[key]; }
1537        else { return exit[key]; }
1538      }
1539
1540    private:
1541      NodeImpl entry, exit;
1542    };
1543
1544    template <typename T>
1545    class EdgeMap : public MapBase<Edge, T> {
1546      typedef typename Parent::template NodeMap<T> NodeImpl;
1547      typedef typename Parent::template EdgeMap<T> EdgeImpl;
1548    public:
1549      EdgeMap(const SplitGraphAdaptorBase& _graph)
1550        : bind(_graph), orig(_graph) {}
1551      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1552        : bind(_graph, t), orig(_graph, t) {}
1553     
1554      void set(const Edge& key, const T& val) {
1555        if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1556        else {bind.set(key.bind, val); }
1557      }
1558     
1559      typename ReferenceMapTraits<EdgeImpl>::Reference
1560      operator[](const Edge& key) {
1561        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1562        else {return bind[key.bind]; }
1563      }
1564
1565      T operator[](const Edge& key) const {
1566        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1567        else {return bind[key.bind]; }
1568      }
1569
1570    private:
1571      typename Parent::template NodeMap<T> bind;
1572      typename Parent::template EdgeMap<T> orig;
1573    };
1574
1575    template <typename EntryMap, typename ExitMap>
1576    class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1577    public:
1578      typedef MapBase<Node, typename EntryMap::Value> Parent;
1579
1580      typedef typename Parent::Key Key;
1581      typedef typename Parent::Value Value;
1582
1583      CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1584        : entryMap(_entryMap), exitMap(_exitMap) {}
1585
1586      Value& operator[](const Key& key) {
1587        if (key.entry) {
1588          return entryMap[key];
1589        } else {
1590          return exitMap[key];
1591        }
1592      }
1593
1594      Value operator[](const Key& key) const {
1595        if (key.entry) {
1596          return entryMap[key];
1597        } else {
1598          return exitMap[key];
1599        }
1600      }
1601
1602      void set(const Key& key, const Value& value) {
1603        if (key.entry) {
1604          entryMap.set(key, value);
1605        } else {
1606          exitMap.set(key, value);
1607        }
1608      }
1609     
1610    private:
1611     
1612      EntryMap& entryMap;
1613      ExitMap& exitMap;
1614     
1615    };
1616
1617    template <typename EdgeMap, typename NodeMap>
1618    class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
1619    public:
1620      typedef MapBase<Edge, typename EdgeMap::Value> Parent;
1621
1622      typedef typename Parent::Key Key;
1623      typedef typename Parent::Value Value;
1624
1625      CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
1626        : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
1627
1628      void set(const Edge& edge, const Value& val) {
1629        if (SplitGraphAdaptorBase::originalEdge(edge)) {
1630          edgeMap.set(edge, val);
1631        } else {
1632          nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
1633        }
1634      }
1635
1636      Value operator[](const Key& edge) const {
1637        if (SplitGraphAdaptorBase::originalEdge(edge)) {
1638          return edgeMap[edge];
1639        } else {
1640          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1641        }
1642      }     
1643
1644      Value& operator[](const Key& edge) {
1645        if (SplitGraphAdaptorBase::originalEdge(edge)) {
1646          return edgeMap[edge];
1647        } else {
1648          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1649        }
1650      }     
1651     
1652    private:
1653      EdgeMap& edgeMap;
1654      NodeMap& nodeMap;
1655    };
1656
1657  };
1658
1659  template <typename _Graph>
1660  class SplitGraphAdaptor
1661    : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
1662  public:
1663    typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1664
1665    SplitGraphAdaptor(_Graph& graph) {
1666      Parent::setGraph(graph);
1667    }
1668
1669
1670  };
1671
1672  template <typename _Graph>
1673  class NewEdgeSetAdaptorBase {
1674  public:
1675
1676    typedef _Graph Graph;
1677    typedef typename Graph::Node Node;
1678    typedef typename Graph::NodeIt NodeIt;
1679
1680  protected:
1681
1682    struct NodeT {
1683      int first_out, first_in;
1684      NodeT() : first_out(-1), first_in(-1) {}
1685    };
1686   
1687    class NodesImpl : protected Graph::template NodeMap<NodeT> {
1688
1689      typedef typename Graph::template NodeMap<NodeT> Parent;
1690      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1691
1692      Adaptor& adaptor;
1693
1694    public:
1695
1696      NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1697        : Parent(_graph), adaptor(_adaptor) {}
1698
1699      virtual ~NodesImpl() {}
1700
1701      virtual void build() {
1702        Parent::build();
1703      }
1704
1705      virtual void clear() {
1706        adaptor._clear();
1707        Parent::clear();
1708      }
1709     
1710      virtual void add(const Node& node) {
1711        Parent::add(node);
1712        adaptor._add(node);
1713      }
1714     
1715      virtual void erase(const Node& node) {
1716        adaptor._erase(node);
1717        Parent::erase(node);
1718      }
1719
1720      NodeT& operator[](const Node& node) {
1721        return Parent::operator[](node);
1722      }
1723
1724      const NodeT& operator[](const Node& node) const {
1725        return Parent::operator[](node);
1726      }
1727     
1728    };
1729
1730    NodesImpl* nodes;
1731
1732    struct EdgeT {
1733      Node source, target;
1734      int next_out, next_in;
1735      int prev_out, prev_in;
1736      EdgeT() : prev_out(-1), prev_in(-1) {}
1737    };
1738
1739    std::vector<EdgeT> edges;
1740
1741    int first_edge;
1742    int first_free_edge;
1743
1744    virtual void _clear() = 0;
1745    virtual void _add(const Node& node) = 0;
1746    virtual void _erase(const Node& node) = 0;
1747   
1748    const Graph* graph;
1749
1750    void initalize(const Graph& _graph, NodesImpl& _nodes) {
1751      graph = &_graph;
1752      nodes = &_nodes;
1753    }
1754   
1755  public:
1756
1757    class Edge {
1758      friend class NewEdgeSetAdaptorBase<Graph>;
1759    protected:
1760      Edge(int _id) : id(_id) {}
1761      int id;
1762    public:
1763      Edge() {}
1764      Edge(Invalid) : id(-1) {}
1765      bool operator==(const Edge& edge) const { return id == edge.id; }
1766      bool operator!=(const Edge& edge) const { return id != edge.id; }
1767      bool operator<(const Edge& edge) const { return id < edge.id; }
1768    };
1769
1770    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1771    virtual ~NewEdgeSetAdaptorBase() {}
1772
1773    Edge addEdge(const Node& source, const Node& target) {
1774      int n;
1775      if (first_free_edge == -1) {
1776        n = edges.size();
1777        edges.push_back(EdgeT());
1778      } else {
1779        n = first_free_edge;
1780        first_free_edge = edges[first_free_edge].next_in;
1781      }
1782      edges[n].next_in = (*nodes)[target].first_in;
1783      (*nodes)[target].first_in = n;
1784      edges[n].next_out = (*nodes)[source].first_out;
1785      (*nodes)[source].first_out = n;
1786      edges[n].source = source;
1787      edges[n].target = target;
1788      return Edge(n);
1789    }
1790
1791    void erase(const Edge& edge) {
1792      int n = edge.id;
1793      if (edges[n].prev_in != -1) {
1794        edges[edges[n].prev_in].next_in = edges[n].next_in;
1795      } else {
1796        (*nodes)[edges[n].target].first_in = edges[n].next_in;
1797      }
1798      if (edges[n].next_in != -1) {
1799        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1800      }
1801
1802      if (edges[n].prev_out != -1) {
1803        edges[edges[n].prev_out].next_out = edges[n].next_out;
1804      } else {
1805        (*nodes)[edges[n].source].first_out = edges[n].next_out;
1806      }
1807      if (edges[n].next_out != -1) {
1808        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1809      }
1810           
1811    }
1812
1813    void first(Node& node) const {
1814      graph->first(node);
1815    }
1816
1817    void next(Node& node) const {
1818      graph->next(node);
1819    }
1820
1821    void first(Edge& edge) const {
1822      Node node;
1823      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1824           next(node));
1825      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1826    }
1827
1828    void next(Edge& edge) const {
1829      if (edges[edge.id].next_in != -1) {
1830        edge.id = edges[edge.id].next_in;
1831      } else {
1832        Node node = edges[edge.id].target;
1833        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1834             next(node));
1835        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1836      }     
1837    }
1838
1839    void firstOut(Edge& edge, const Node& node) const {
1840      edge.id = (*nodes)[node].first_out;   
1841    }
1842   
1843    void nextOut(Edge& edge) const {
1844      edge.id = edges[edge.id].next_out;       
1845    }
1846
1847    void firstIn(Edge& edge, const Node& node) const {
1848      edge.id = (*nodes)[node].first_in;         
1849    }
1850
1851    void nextIn(Edge& edge) const {
1852      edge.id = edges[edge.id].next_in;   
1853    }
1854
1855    int id(const Node& node) const { return graph->id(node); }
1856    int id(const Edge& edge) const { return edge.id; }
1857
1858    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
1859    Edge fromId(int id, Edge) const { return Edge(id); }
1860
1861    int maxId(Node) const { return graph->maxId(Node()); };
1862    int maxId(Edge) const { return edges.size() - 1; }
1863
1864    Node source(const Edge& edge) const { return edges[edge.id].source;}
1865    Node target(const Edge& edge) const { return edges[edge.id].target;}
1866
1867  };
1868
1869
1870  /// \brief Graph adaptor using a node set of another graph and an
1871  /// own edge set.
1872  ///
1873  /// This structure can be used to establish another graph over a node set
1874  /// of an existing one. The node iterator will go through the nodes of the
1875  /// original graph.
1876  ///
1877  /// \param _Graph The type of the graph which shares its node set with
1878  /// this class. Its interface must conform to the \ref concept::StaticGraph
1879  /// "StaticGraph" concept.
1880  ///
1881  /// In the edge extension and removing it conforms to the
1882  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1883  template <typename _Graph>
1884  class NewEdgeSetAdaptor :
1885    public ErasableGraphExtender<
1886    ClearableGraphExtender<
1887    ExtendableGraphExtender<
1888    MappableGraphExtender<
1889    IterableGraphExtender<
1890    AlterableGraphExtender<
1891    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1892
1893  public:
1894
1895    typedef ErasableGraphExtender<
1896      ClearableGraphExtender<
1897      ExtendableGraphExtender<
1898      MappableGraphExtender<
1899      IterableGraphExtender<
1900      AlterableGraphExtender<
1901      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1902   
1903
1904    typedef typename Parent::Node Node;
1905    typedef typename Parent::Edge Edge;
1906
1907  private:
1908
1909    virtual void _clear() {
1910      Parent::edges.clear();
1911      Parent::first_edge = -1;
1912      Parent::first_free_edge = -1;
1913      Parent::getNotifier(Edge()).clear();
1914      Parent::getNotifier(Node()).clear();
1915    }
1916
1917    virtual void _add(const Node& node) {
1918      Parent::getNotifier(Node()).add(node);
1919    }
1920
1921    virtual void _erase(const Node& node) {
1922      Edge edge;
1923      Parent::firstOut(edge, node);
1924      while (edge != INVALID) {
1925        Parent::erase(edge);
1926        Parent::firstOut(edge, node);
1927      }
1928
1929      Parent::firstIn(edge, node);
1930      while (edge != INVALID) {
1931        Parent::erase(edge);
1932        Parent::firstIn(edge, node);
1933      }
1934     
1935      Parent::getNotifier(Node()).erase(node);
1936    }
1937
1938
1939    typedef typename Parent::NodesImpl NodesImpl;
1940
1941    NodesImpl nodes;
1942   
1943  public:
1944
1945    /// \brief Constructor of the adaptor.
1946    ///
1947    /// Constructor of the adaptor.
1948    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1949      Parent::initalize(_graph, nodes);
1950    }
1951
1952    void clear() {
1953      Parent::getNotifier(Edge()).clear();     
1954
1955      Parent::edges.clear();
1956      Parent::first_edge = -1;
1957      Parent::first_free_edge = -1;
1958    }
1959   
1960  };
1961
1962  /// \brief Graph adaptor using a node set of another graph and an
1963  /// own undir edge set.
1964  ///
1965  /// This structure can be used to establish another undirected graph over
1966  /// a node set of an existing one. The node iterator will go through the
1967  /// nodes of the original graph.
1968  ///
1969  /// \param _Graph The type of the graph which shares its node set with
1970  /// this class. Its interface must conform to the \ref concept::StaticGraph
1971  /// "StaticGraph" concept.
1972  ///
1973  /// In the edge extension and removing it conforms to the
1974  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1975  template <typename _Graph>
1976  class NewUndirEdgeSetAdaptor :
1977    public ErasableUndirGraphExtender<
1978    ClearableUndirGraphExtender<
1979    ExtendableUndirGraphExtender<
1980    MappableUndirGraphExtender<
1981    IterableUndirGraphExtender<
1982    AlterableUndirGraphExtender<
1983    UndirGraphExtender<
1984    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1985
1986  public:
1987
1988    typedef ErasableUndirGraphExtender<
1989      ClearableUndirGraphExtender<
1990      ExtendableUndirGraphExtender<
1991      MappableUndirGraphExtender<
1992      IterableUndirGraphExtender<
1993      AlterableUndirGraphExtender<
1994      UndirGraphExtender<
1995      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1996   
1997
1998    typedef typename Parent::Node Node;
1999    typedef typename Parent::Edge Edge;
2000    typedef typename Parent::UndirEdge UndirEdge;
2001
2002  private:
2003
2004    virtual void _clear() {
2005      Parent::edges.clear();
2006      Parent::first_edge = -1;
2007      Parent::first_free_edge = -1;
2008      Parent::getNotifier(Edge()).clear();
2009      Parent::getNotifier(Node()).clear();
2010    }
2011
2012    virtual void _add(const Node& node) {
2013      Parent::getNotifier(Node()).add(node);
2014    }
2015
2016    virtual void _erase(const Node& node) {
2017      Edge edge;
2018      Parent::firstOut(edge, node);
2019      while (edge != INVALID) {
2020        Parent::erase(edge);
2021        Parent::firstOut(edge, node);
2022      }
2023
2024      Parent::firstIn(edge, node);
2025      while (edge != INVALID) {
2026        Parent::erase(edge);
2027        Parent::firstIn(edge, node);
2028      }
2029     
2030      Parent::getNotifier(Node()).erase(node);
2031    }
2032
2033    typedef typename Parent::NodesImpl NodesImpl;
2034
2035    NodesImpl nodes;
2036   
2037  public:
2038
2039
2040    /// \brief Constructor of the adaptor.
2041    ///
2042    /// Constructor of the adaptor.
2043    NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
2044      Parent::initalize(_graph, nodes);
2045    }
2046
2047    void clear() {
2048      Parent::getNotifier(Edge()).clear();     
2049      Parent::getNotifier(UndirEdge()).clear();     
2050
2051      Parent::edges.clear();
2052      Parent::first_edge = -1;
2053      Parent::first_free_edge = -1;
2054    }
2055   
2056  };
2057
2058  ///@}
2059
2060} //namespace lemon
2061
2062#endif //LEMON_GRAPH_ADAPTOR_H
2063
Note: See TracBrowser for help on using the repository browser.