COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1980:a954b780e3ab

Last change on this file since 1980:a954b780e3ab was 1980:a954b780e3ab, checked in by Balazs Dezso, 14 years ago

Renaming to be convient to the naming of the adaptors
Concept checking of the ugraph adaptors

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