COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1951:cb7a6e0573bc

Last change on this file since 1951:cb7a6e0573bc was 1951:cb7a6e0573bc, checked in by Mihaly Barasz, 14 years ago

graph_adaptor.h: probably a doxygen bug: in tex formulas there should be

whitespace after the opening and before the closing \f$

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