COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1538:777834118f73

Last change on this file since 1538:777834118f73 was 1538:777834118f73, checked in by Balazs Dezso, 19 years ago

NewUndirEdgeSetAdaptor? class
some doc
some bug fix

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