1.1 --- a/doc/Makefile.am Mon May 02 05:49:33 2005 +0000
1.2 +++ b/doc/Makefile.am Wed May 04 13:07:10 2005 +0000
1.3 @@ -8,7 +8,7 @@
1.4 EXTRA_DIST = html mainpage.dox getstart.dox quicktour.dox \
1.5 demoprograms.dox graphs.dox undir_graphs.dox named-param.dox \
1.6 maps.dox coding_style.dox groups.dox namespaces.dox license.dox \
1.7 - developers_interface.dox graph_io.dox dirs.dox gwrappers.dox
1.8 + developers_interface.dox graph_io.dox dirs.dox graph-adaptors.dox
1.9
1.10
1.11 ## all-local: html/index.html
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/doc/graph-adaptors.dox Wed May 04 13:07:10 2005 +0000
2.3 @@ -0,0 +1,80 @@
2.4 +/**
2.5 + @defgroup graph_adaptors Adaptor Classes for Graphs
2.6 + \brief This group contains several adaptor classes for graphs
2.7 + @ingroup graphs
2.8 +
2.9 + The main parts of LEMON are the different graph structures,
2.10 + generic graph algorithms, graph concepts which couple these, and
2.11 + graph adaptors. While the previous notions are more or less clear, the
2.12 + latter one needs further explanation.
2.13 + Graph adaptors are graph classes which serve for considering graph
2.14 + structures in different ways.
2.15 +
2.16 + A short example makes this much
2.17 + clearer.
2.18 + Suppose that we have an instance \c g of a directed graph
2.19 + type say ListGraph and an algorithm
2.20 + \code template<typename Graph> int algorithm(const Graph&); \endcode
2.21 + is needed to run on the reversed oriented graph.
2.22 + It may be expensive (in time or in memory usage) to copy
2.23 + \c g with the reversed orientation.
2.24 + In this case, an adaptor class is used, which
2.25 + (according to LEMON graph concepts) works as a graph.
2.26 + The adaptor uses
2.27 + the original graph structure and graph operations when methods of the
2.28 + reversed oriented graph are called.
2.29 + This means that the adaptor have minor memory usage,
2.30 + and do not perform sophisticated algorithmic actions.
2.31 + The purpose of it is to give a tool for the cases when
2.32 + a graph have to be used in a specific alteration.
2.33 + If this alteration is obtained by a usual construction
2.34 + like filtering the edge-set or considering a new orientation, then
2.35 + an adaptor is worthwhile to use.
2.36 + To come back to the reversed oriented graph, in this situation
2.37 + \code template<typename Graph> class RevGraphAdaptor; \endcode
2.38 + template class can be used.
2.39 + The code looks as follows
2.40 + \code
2.41 + ListGraph g;
2.42 + RevGraphAdaptor<ListGraph> rgw(g);
2.43 + int result=algorithm(rgw);
2.44 + \endcode
2.45 + After running the algorithm, the original graph \c g
2.46 + is untouched.
2.47 + This techniques gives rise to an elegant code, and
2.48 + based on stable graph adaptors, complex algorithms can be
2.49 + implemented easily.
2.50 +
2.51 + In flow, circulation and bipartite matching problems, the residual
2.52 + graph is of particular importance. Combining an adaptor implementing
2.53 + this, shortest path algorithms and minimum mean cycle algorithms,
2.54 + a range of weighted and cardinality optimization algorithms can be
2.55 + obtained.
2.56 + For other examples,
2.57 + the interested user is referred to the detailed documentation of
2.58 + particular adaptors.
2.59 +
2.60 + The behavior of graph adaptors can be very different. Some of them keep
2.61 + capabilities of the original graph while in other cases this would be
2.62 + meaningless. This means that the concepts that they are models of depend
2.63 + on the graph adaptor, and the wrapped graph(s).
2.64 + If an edge of \c rgw is deleted, this is carried out by
2.65 + deleting the corresponding edge of \c g, thus the adaptor modifies the
2.66 + original graph.
2.67 + But for a residual
2.68 + graph, this operation has no sense.
2.69 + Let us stand one more example here to simplify your work.
2.70 + RevGraphAdaptor has constructor
2.71 + \code
2.72 + RevGraphAdaptor(Graph& _g);
2.73 + \endcode
2.74 + This means that in a situation,
2.75 + when a <tt> const ListGraph& </tt> reference to a graph is given,
2.76 + then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
2.77 + \code
2.78 + int algorithm1(const ListGraph& g) {
2.79 + RevGraphAdaptor<const ListGraph> rgw(g);
2.80 + return algorithm2(rgw);
2.81 + }
2.82 + \endcode
2.83 +*/
3.1 --- a/doc/groups.dox Mon May 02 05:49:33 2005 +0000
3.2 +++ b/doc/groups.dox Wed May 04 13:07:10 2005 +0000
3.3 @@ -31,7 +31,7 @@
3.4 the residual graph can be accessed by an other algorithm, or a node-set
3.5 is to be shrunk for an other algorithm.
3.6 LEMON also provides a variety of graphs for these requirements called
3.7 -\ref gwrappers "graph wrappers". Wrappers cannot be used alone but only
3.8 +\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
3.9 in conjunction with other graph representation.
3.10
3.11 You are free to use the graph structure that fit your requirements
4.1 --- a/doc/gwrappers.dox Mon May 02 05:49:33 2005 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,80 +0,0 @@
4.4 -/**
4.5 - @defgroup gwrappers Wrapper Classes for Graphs
4.6 - \brief This group contains several wrapper classes for graphs
4.7 - @ingroup graphs
4.8 -
4.9 - The main parts of LEMON are the different graph structures,
4.10 - generic graph algorithms, graph concepts which couple these, and
4.11 - graph wrappers. While the previous notions are more or less clear, the
4.12 - latter one needs further explanation.
4.13 - Graph wrappers are graph classes which serve for considering graph
4.14 - structures in different ways.
4.15 -
4.16 - A short example makes this much
4.17 - clearer.
4.18 - Suppose that we have an instance \c g of a directed graph
4.19 - type say ListGraph and an algorithm
4.20 - \code template<typename Graph> int algorithm(const Graph&); \endcode
4.21 - is needed to run on the reversed oriented graph.
4.22 - It may be expensive (in time or in memory usage) to copy
4.23 - \c g with the reversed orientation.
4.24 - In this case, a wrapper class is used, which
4.25 - (according to LEMON graph concepts) works as a graph.
4.26 - The wrapper uses
4.27 - the original graph structure and graph operations when methods of the
4.28 - reversed oriented graph are called.
4.29 - This means that the wrapper have minor memory usage,
4.30 - and do not perform sophisticated algorithmic actions.
4.31 - The purpose of it is to give a tool for the cases when
4.32 - a graph have to be used in a specific alteration.
4.33 - If this alteration is obtained by a usual construction
4.34 - like filtering the edge-set or considering a new orientation, then
4.35 - a wrapper is worthwhile to use.
4.36 - To come back to the reversed oriented graph, in this situation
4.37 - \code template<typename Graph> class RevGraphWrapper; \endcode
4.38 - template class can be used.
4.39 - The code looks as follows
4.40 - \code
4.41 - ListGraph g;
4.42 - RevGraphWrapper<ListGraph> rgw(g);
4.43 - int result=algorithm(rgw);
4.44 - \endcode
4.45 - After running the algorithm, the original graph \c g
4.46 - is untouched.
4.47 - This techniques gives rise to an elegant code, and
4.48 - based on stable graph wrappers, complex algorithms can be
4.49 - implemented easily.
4.50 -
4.51 - In flow, circulation and bipartite matching problems, the residual
4.52 - graph is of particular importance. Combining a wrapper implementing
4.53 - this, shortest path algorithms and minimum mean cycle algorithms,
4.54 - a range of weighted and cardinality optimization algorithms can be
4.55 - obtained.
4.56 - For other examples,
4.57 - the interested user is referred to the detailed documentation of
4.58 - particular wrappers.
4.59 -
4.60 - The behavior of graph wrappers can be very different. Some of them keep
4.61 - capabilities of the original graph while in other cases this would be
4.62 - meaningless. This means that the concepts that they are models of depend
4.63 - on the graph wrapper, and the wrapped graph(s).
4.64 - If an edge of \c rgw is deleted, this is carried out by
4.65 - deleting the corresponding edge of \c g, thus the wrapper modifies the
4.66 - original graph.
4.67 - But for a residual
4.68 - graph, this operation has no sense.
4.69 - Let us stand one more example here to simplify your work.
4.70 - RevGraphWrapper has constructor
4.71 - \code
4.72 - RevGraphWrapper(Graph& _g);
4.73 - \endcode
4.74 - This means that in a situation,
4.75 - when a <tt> const ListGraph& </tt> reference to a graph is given,
4.76 - then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
4.77 - \code
4.78 - int algorithm1(const ListGraph& g) {
4.79 - RevGraphWrapper<const ListGraph> rgw(g);
4.80 - return algorithm2(rgw);
4.81 - }
4.82 - \endcode
4.83 -*/
5.1 --- a/src/demo/Makefile.am Mon May 02 05:49:33 2005 +0000
5.2 +++ b/src/demo/Makefile.am Wed May 04 13:07:10 2005 +0000
5.3 @@ -1,14 +1,14 @@
5.4 AM_CPPFLAGS = -I$(top_srcdir)/src
5.5 LDADD = $(top_builddir)/src/lemon/libemon.la
5.6
5.7 -EXTRA_DIST = sub_graph_wrapper_demo.dim
5.8 +EXTRA_DIST = sub_graph_adaptor_demo.dim
5.9
5.10 noinst_PROGRAMS = \
5.11 dim_to_dot \
5.12 dim_to_lgf \
5.13 graph_to_eps_demo \
5.14 min_route \
5.15 - sub_graph_wrapper_demo
5.16 + sub_graph_adaptor_demo
5.17
5.18 if HAVE_GLPK
5.19 noinst_PROGRAMS += lp_demo lp_maxflow_demo
5.20 @@ -27,8 +27,8 @@
5.21
5.22 min_route_SOURCES = min_route.cc
5.23
5.24 -sub_graph_wrapper_demo_SOURCES = \
5.25 - sub_graph_wrapper_demo.cc \
5.26 +sub_graph_adaptor_demo_SOURCES = \
5.27 + sub_graph_adaptor_demo.cc \
5.28 tight_edge_filter_map.h
5.29
5.30 lp_demo_SOURCES = lp_demo.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/demo/sub_graph_adaptor_demo.cc Wed May 04 13:07:10 2005 +0000
6.3 @@ -0,0 +1,80 @@
6.4 +// -*- c++ -*-
6.5 +
6.6 +// Use a DIMACS max flow file as stdin.
6.7 +// sub_graph_adaptor_demo < dimacs_max_flow_file
6.8 +// This program computes a maximum number of edge-disjoint shortest paths
6.9 +// between s and t.
6.10 +
6.11 +#include <iostream>
6.12 +#include <fstream>
6.13 +
6.14 +#include <lemon/smart_graph.h>
6.15 +#include <lemon/dijkstra.h>
6.16 +#include <lemon/maps.h>
6.17 +#include <lemon/graph_adaptor.h>
6.18 +#include <lemon/dimacs.h>
6.19 +#include <lemon/preflow.h>
6.20 +#include <tight_edge_filter_map.h>
6.21 +
6.22 +using namespace lemon;
6.23 +
6.24 +using std::cout;
6.25 +using std::endl;
6.26 +
6.27 +int main()
6.28 +{
6.29 + typedef SmartGraph Graph;
6.30 +
6.31 + typedef Graph::Edge Edge;
6.32 + typedef Graph::Node Node;
6.33 + typedef Graph::EdgeIt EdgeIt;
6.34 + typedef Graph::NodeIt NodeIt;
6.35 + typedef Graph::EdgeMap<int> LengthMap;
6.36 +
6.37 + Graph g;
6.38 + Node s, t;
6.39 + LengthMap length(g);
6.40 +
6.41 + readDimacs(std::cin, g, length, s, t);
6.42 +
6.43 + cout << "edges with lengths (of form id, source--length->target): " << endl;
6.44 + for(EdgeIt e(g); e!=INVALID; ++e)
6.45 + cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--"
6.46 + << length[e] << "->" << g.id(g.target(e)) << endl;
6.47 +
6.48 + cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
6.49 +
6.50 + typedef Dijkstra<Graph, LengthMap> Dijkstra;
6.51 + Dijkstra dijkstra(g, length);
6.52 + dijkstra.run(s);
6.53 +
6.54 + // This map returns true exactly for those edges which are
6.55 + // tight w.r.t the length funcion and the potential
6.56 + // given by the dijkstra algorithm.
6.57 + typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
6.58 + TightEdgeFilter;
6.59 + TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
6.60 +
6.61 +// ConstMap<Node, bool> const_true_map(true);
6.62 + // This graph contains exaclty the tight edges.
6.63 +// typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
6.64 + typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
6.65 + SubGW gw(g, tight_edge_filter);
6.66 +
6.67 + ConstMap<Edge, int> const_1_map(1);
6.68 + Graph::EdgeMap<int> flow(g, 0);
6.69 + // Max flow between s and t in the graph of tight edges.
6.70 + Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
6.71 + preflow(gw, s, t, const_1_map, flow);
6.72 + preflow.run();
6.73 +
6.74 + cout << "maximum number of edge-disjoint shortest path: "
6.75 + << preflow.flowValue() << endl;
6.76 + cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
6.77 + << endl;
6.78 + for(EdgeIt e(g); e!=INVALID; ++e)
6.79 + if (flow[e])
6.80 + cout << " " << g.id(e) << ", "
6.81 + << g.id(g.source(e)) << "--"
6.82 + << length[e] << "->" << g.id(g.target(e)) << endl;
6.83 +}
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/demo/sub_graph_adaptor_demo.dim Wed May 04 13:07:10 2005 +0000
7.3 @@ -0,0 +1,14 @@
7.4 +c LEMON max flow problem
7.5 +p max 7 9
7.6 +n 1 s
7.7 +n 7 t
7.8 +a 1 2 3
7.9 +a 1 3 2
7.10 +a 1 4 1
7.11 +a 2 5 3
7.12 +a 3 5 2
7.13 +a 3 7 5
7.14 +a 3 6 3
7.15 +a 4 6 1
7.16 +a 5 7 2
7.17 +a 6 7 4
8.1 --- a/src/demo/sub_graph_wrapper_demo.cc Mon May 02 05:49:33 2005 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,80 +0,0 @@
8.4 -// -*- c++ -*-
8.5 -
8.6 -// Use a DIMACS max flow file as stdin.
8.7 -// sub_graph_wrapper_demo < dimacs_max_flow_file
8.8 -// This program computes a maximum number of edge-disjoint shortest paths
8.9 -// between s and t.
8.10 -
8.11 -#include <iostream>
8.12 -#include <fstream>
8.13 -
8.14 -#include <lemon/smart_graph.h>
8.15 -#include <lemon/dijkstra.h>
8.16 -#include <lemon/maps.h>
8.17 -#include <lemon/graph_wrapper.h>
8.18 -#include <lemon/dimacs.h>
8.19 -#include <lemon/preflow.h>
8.20 -#include <tight_edge_filter_map.h>
8.21 -
8.22 -using namespace lemon;
8.23 -
8.24 -using std::cout;
8.25 -using std::endl;
8.26 -
8.27 -int main()
8.28 -{
8.29 - typedef SmartGraph Graph;
8.30 -
8.31 - typedef Graph::Edge Edge;
8.32 - typedef Graph::Node Node;
8.33 - typedef Graph::EdgeIt EdgeIt;
8.34 - typedef Graph::NodeIt NodeIt;
8.35 - typedef Graph::EdgeMap<int> LengthMap;
8.36 -
8.37 - Graph g;
8.38 - Node s, t;
8.39 - LengthMap length(g);
8.40 -
8.41 - readDimacs(std::cin, g, length, s, t);
8.42 -
8.43 - cout << "edges with lengths (of form id, source--length->target): " << endl;
8.44 - for(EdgeIt e(g); e!=INVALID; ++e)
8.45 - cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--"
8.46 - << length[e] << "->" << g.id(g.target(e)) << endl;
8.47 -
8.48 - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
8.49 -
8.50 - typedef Dijkstra<Graph, LengthMap> Dijkstra;
8.51 - Dijkstra dijkstra(g, length);
8.52 - dijkstra.run(s);
8.53 -
8.54 - // This map returns true exactly for those edges which are
8.55 - // tight w.r.t the length funcion and the potential
8.56 - // given by the dijkstra algorithm.
8.57 - typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
8.58 - TightEdgeFilter;
8.59 - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
8.60 -
8.61 -// ConstMap<Node, bool> const_true_map(true);
8.62 - // This graph contains exaclty the tight edges.
8.63 -// typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
8.64 - typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
8.65 - SubGW gw(g, tight_edge_filter);
8.66 -
8.67 - ConstMap<Edge, int> const_1_map(1);
8.68 - Graph::EdgeMap<int> flow(g, 0);
8.69 - // Max flow between s and t in the graph of tight edges.
8.70 - Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
8.71 - preflow(gw, s, t, const_1_map, flow);
8.72 - preflow.run();
8.73 -
8.74 - cout << "maximum number of edge-disjoint shortest path: "
8.75 - << preflow.flowValue() << endl;
8.76 - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
8.77 - << endl;
8.78 - for(EdgeIt e(g); e!=INVALID; ++e)
8.79 - if (flow[e])
8.80 - cout << " " << g.id(e) << ", "
8.81 - << g.id(g.source(e)) << "--"
8.82 - << length[e] << "->" << g.id(g.target(e)) << endl;
8.83 -}
9.1 --- a/src/demo/sub_graph_wrapper_demo.dim Mon May 02 05:49:33 2005 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,14 +0,0 @@
9.4 -c LEMON max flow problem
9.5 -p max 7 9
9.6 -n 1 s
9.7 -n 7 t
9.8 -a 1 2 3
9.9 -a 1 3 2
9.10 -a 1 4 1
9.11 -a 2 5 3
9.12 -a 3 5 2
9.13 -a 3 7 5
9.14 -a 3 6 3
9.15 -a 4 6 1
9.16 -a 5 7 2
9.17 -a 6 7 4
10.1 --- a/src/lemon/Makefile.am Mon May 02 05:49:33 2005 +0000
10.2 +++ b/src/lemon/Makefile.am Wed May 04 13:07:10 2005 +0000
10.3 @@ -29,7 +29,7 @@
10.4 error.h \
10.5 fib_heap.h \
10.6 full_graph.h \
10.7 - graph_wrapper.h \
10.8 + graph_adaptor.h \
10.9 graph_utils.h \
10.10 graph_to_eps.h \
10.11 invalid.h \
11.1 --- a/src/lemon/bits/undir_graph_extender.h Mon May 02 05:49:33 2005 +0000
11.2 +++ b/src/lemon/bits/undir_graph_extender.h Wed May 04 13:07:10 2005 +0000
11.3 @@ -38,7 +38,7 @@
11.4 friend class UndirGraphExtender;
11.5
11.6 protected:
11.7 - // FIXME: Marci use opposite logic in his graph wrappers. It would
11.8 + // FIXME: Marci use opposite logic in his graph adaptors. It would
11.9 // be reasonable to syncronize...
11.10 bool forward;
11.11
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/src/lemon/graph_adaptor.h Wed May 04 13:07:10 2005 +0000
12.3 @@ -0,0 +1,1213 @@
12.4 +/* -*- C++ -*-
12.5 + * src/lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
12.6 + *
12.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
12.9 + *
12.10 + * Permission to use, modify and distribute this software is granted
12.11 + * provided that this copyright notice appears in all copies. For
12.12 + * precise terms see the accompanying LICENSE file.
12.13 + *
12.14 + * This software is provided "AS IS" with no warranty of any kind,
12.15 + * express or implied, and with no claim as to its suitability for any
12.16 + * purpose.
12.17 + *
12.18 + */
12.19 +
12.20 +#ifndef LEMON_GRAPH_ADAPTOR_H
12.21 +#define LEMON_GRAPH_ADAPTOR_H
12.22 +
12.23 +///\ingroup graph_adaptors
12.24 +///\file
12.25 +///\brief Several graph adaptors.
12.26 +///
12.27 +///This file contains several useful graph adaptor functions.
12.28 +///
12.29 +///\author Marton Makai
12.30 +
12.31 +#include <lemon/invalid.h>
12.32 +#include <lemon/maps.h>
12.33 +#include <lemon/bits/iterable_graph_extender.h>
12.34 +#include <lemon/bits/undir_graph_extender.h>
12.35 +#include <iostream>
12.36 +
12.37 +namespace lemon {
12.38 +
12.39 + // Graph adaptors
12.40 +
12.41 + /*!
12.42 + \addtogroup graph_adaptors
12.43 + @{
12.44 + */
12.45 +
12.46 + /*!
12.47 + Base type for the Graph Adaptors
12.48 +
12.49 + \warning Graph adaptors are in even more experimental state than the other
12.50 + parts of the lib. Use them at you own risk.
12.51 +
12.52 + This is the base type for most of LEMON graph adaptors.
12.53 + This class implements a trivial graph adaptor i.e. it only wraps the
12.54 + functions and types of the graph. The purpose of this class is to
12.55 + make easier implementing graph adaptors. E.g. if an adaptor is
12.56 + considered which differs from the wrapped graph only in some of its
12.57 + functions or types, then it can be derived from GraphAdaptor, and only the
12.58 + differences should be implemented.
12.59 +
12.60 + \author Marton Makai
12.61 + */
12.62 + template<typename _Graph>
12.63 + class GraphAdaptorBase {
12.64 + public:
12.65 + typedef _Graph Graph;
12.66 + /// \todo Is it needed?
12.67 + typedef Graph BaseGraph;
12.68 + typedef Graph ParentGraph;
12.69 +
12.70 + protected:
12.71 + Graph* graph;
12.72 + GraphAdaptorBase() : graph(0) { }
12.73 + void setGraph(Graph& _graph) { graph=&_graph; }
12.74 +
12.75 + public:
12.76 + GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
12.77 +
12.78 + typedef typename Graph::Node Node;
12.79 + typedef typename Graph::Edge Edge;
12.80 +
12.81 + void first(Node& i) const { graph->first(i); }
12.82 + void first(Edge& i) const { graph->first(i); }
12.83 + void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
12.84 + void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
12.85 +
12.86 + void next(Node& i) const { graph->next(i); }
12.87 + void next(Edge& i) const { graph->next(i); }
12.88 + void nextIn(Edge& i) const { graph->nextIn(i); }
12.89 + void nextOut(Edge& i) const { graph->nextOut(i); }
12.90 +
12.91 + Node source(const Edge& e) const { return graph->source(e); }
12.92 + Node target(const Edge& e) const { return graph->target(e); }
12.93 +
12.94 + int nodeNum() const { return graph->nodeNum(); }
12.95 + int edgeNum() const { return graph->edgeNum(); }
12.96 +
12.97 + Node addNode() const { return Node(graph->addNode()); }
12.98 + Edge addEdge(const Node& source, const Node& target) const {
12.99 + return Edge(graph->addEdge(source, target)); }
12.100 +
12.101 + void erase(const Node& i) const { graph->erase(i); }
12.102 + void erase(const Edge& i) const { graph->erase(i); }
12.103 +
12.104 + void clear() const { graph->clear(); }
12.105 +
12.106 + bool forward(const Edge& e) const { return graph->forward(e); }
12.107 + bool backward(const Edge& e) const { return graph->backward(e); }
12.108 +
12.109 + int id(const Node& v) const { return graph->id(v); }
12.110 + int id(const Edge& e) const { return graph->id(e); }
12.111 +
12.112 + Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
12.113 +
12.114 + template <typename _Value>
12.115 + class NodeMap : public _Graph::template NodeMap<_Value> {
12.116 + public:
12.117 + typedef typename _Graph::template NodeMap<_Value> Parent;
12.118 + NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
12.119 + NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
12.120 + : Parent(*gw.graph, value) { }
12.121 + };
12.122 +
12.123 + template <typename _Value>
12.124 + class EdgeMap : public _Graph::template EdgeMap<_Value> {
12.125 + public:
12.126 + typedef typename _Graph::template EdgeMap<_Value> Parent;
12.127 + EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
12.128 + EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
12.129 + : Parent(*gw.graph, value) { }
12.130 + };
12.131 +
12.132 + };
12.133 +
12.134 + template <typename _Graph>
12.135 + class GraphAdaptor :
12.136 + public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
12.137 + public:
12.138 + typedef _Graph Graph;
12.139 + typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
12.140 + protected:
12.141 + GraphAdaptor() : Parent() { }
12.142 +
12.143 + public:
12.144 + GraphAdaptor(Graph& _graph) { setGraph(_graph); }
12.145 + };
12.146 +
12.147 + template <typename _Graph>
12.148 + class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
12.149 + public:
12.150 + typedef _Graph Graph;
12.151 + typedef GraphAdaptorBase<_Graph> Parent;
12.152 + protected:
12.153 + RevGraphAdaptorBase() : Parent() { }
12.154 + public:
12.155 + typedef typename Parent::Node Node;
12.156 + typedef typename Parent::Edge Edge;
12.157 +
12.158 + // using Parent::first;
12.159 + void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
12.160 + void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
12.161 +
12.162 + // using Parent::next;
12.163 + void nextIn(Edge& i) const { Parent::nextOut(i); }
12.164 + void nextOut(Edge& i) const { Parent::nextIn(i); }
12.165 +
12.166 + Node source(const Edge& e) const { return Parent::target(e); }
12.167 + Node target(const Edge& e) const { return Parent::source(e); }
12.168 + };
12.169 +
12.170 +
12.171 + /// A graph adaptor which reverses the orientation of the edges.
12.172 +
12.173 + ///\warning Graph adaptors are in even more experimental state than the other
12.174 + ///parts of the lib. Use them at you own risk.
12.175 + ///
12.176 + /// Let \f$G=(V, A)\f$ be a directed graph and
12.177 + /// suppose that a graph instange \c g of type
12.178 + /// \c ListGraph implements \f$G\f$.
12.179 + /// \code
12.180 + /// ListGraph g;
12.181 + /// \endcode
12.182 + /// For each directed edge
12.183 + /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
12.184 + /// reversing its orientation.
12.185 + /// Then RevGraphAdaptor implements the graph structure with node-set
12.186 + /// \f$V\f$ and edge-set
12.187 + /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
12.188 + /// reversing the orientation of its edges. The following code shows how
12.189 + /// such an instance can be constructed.
12.190 + /// \code
12.191 + /// RevGraphAdaptor<ListGraph> gw(g);
12.192 + /// \endcode
12.193 + ///\author Marton Makai
12.194 + template<typename _Graph>
12.195 + class RevGraphAdaptor :
12.196 + public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
12.197 + public:
12.198 + typedef _Graph Graph;
12.199 + typedef IterableGraphExtender<
12.200 + RevGraphAdaptorBase<_Graph> > Parent;
12.201 + protected:
12.202 + RevGraphAdaptor() { }
12.203 + public:
12.204 + RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
12.205 + };
12.206 +
12.207 +
12.208 + template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
12.209 + class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
12.210 + public:
12.211 + typedef _Graph Graph;
12.212 + typedef GraphAdaptorBase<_Graph> Parent;
12.213 + protected:
12.214 + NodeFilterMap* node_filter_map;
12.215 + EdgeFilterMap* edge_filter_map;
12.216 + SubGraphAdaptorBase() : Parent(),
12.217 + node_filter_map(0), edge_filter_map(0) { }
12.218 +
12.219 + void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
12.220 + node_filter_map=&_node_filter_map;
12.221 + }
12.222 + void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
12.223 + edge_filter_map=&_edge_filter_map;
12.224 + }
12.225 +
12.226 + public:
12.227 +// SubGraphAdaptorBase(Graph& _graph,
12.228 +// NodeFilterMap& _node_filter_map,
12.229 +// EdgeFilterMap& _edge_filter_map) :
12.230 +// Parent(&_graph),
12.231 +// node_filter_map(&node_filter_map),
12.232 +// edge_filter_map(&edge_filter_map) { }
12.233 +
12.234 + typedef typename Parent::Node Node;
12.235 + typedef typename Parent::Edge Edge;
12.236 +
12.237 + void first(Node& i) const {
12.238 + Parent::first(i);
12.239 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
12.240 + }
12.241 + void first(Edge& i) const {
12.242 + Parent::first(i);
12.243 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
12.244 + }
12.245 + void firstIn(Edge& i, const Node& n) const {
12.246 + Parent::firstIn(i, n);
12.247 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
12.248 + }
12.249 + void firstOut(Edge& i, const Node& n) const {
12.250 + Parent::firstOut(i, n);
12.251 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
12.252 + }
12.253 +
12.254 + void next(Node& i) const {
12.255 + Parent::next(i);
12.256 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
12.257 + }
12.258 + void next(Edge& i) const {
12.259 + Parent::next(i);
12.260 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
12.261 + }
12.262 + void nextIn(Edge& i) const {
12.263 + Parent::nextIn(i);
12.264 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
12.265 + }
12.266 + void nextOut(Edge& i) const {
12.267 + Parent::nextOut(i);
12.268 + while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
12.269 + }
12.270 +
12.271 + /// This function hides \c n in the graph, i.e. the iteration
12.272 + /// jumps over it. This is done by simply setting the value of \c n
12.273 + /// to be false in the corresponding node-map.
12.274 + void hide(const Node& n) const { node_filter_map->set(n, false); }
12.275 +
12.276 + /// This function hides \c e in the graph, i.e. the iteration
12.277 + /// jumps over it. This is done by simply setting the value of \c e
12.278 + /// to be false in the corresponding edge-map.
12.279 + void hide(const Edge& e) const { edge_filter_map->set(e, false); }
12.280 +
12.281 + /// The value of \c n is set to be true in the node-map which stores
12.282 + /// hide information. If \c n was hidden previuosly, then it is shown
12.283 + /// again
12.284 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
12.285 +
12.286 + /// The value of \c e is set to be true in the edge-map which stores
12.287 + /// hide information. If \c e was hidden previuosly, then it is shown
12.288 + /// again
12.289 + void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
12.290 +
12.291 + /// Returns true if \c n is hidden.
12.292 + bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
12.293 +
12.294 + /// Returns true if \c n is hidden.
12.295 + bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
12.296 +
12.297 + /// \warning This is a linear time operation and works only if s
12.298 + /// \c Graph::NodeIt is defined.
12.299 + /// \todo assign tags.
12.300 + int nodeNum() const {
12.301 + int i=0;
12.302 + Node n;
12.303 + for (first(n); n!=INVALID; next(n)) ++i;
12.304 + return i;
12.305 + }
12.306 +
12.307 + /// \warning This is a linear time operation and works only if
12.308 + /// \c Graph::EdgeIt is defined.
12.309 + /// \todo assign tags.
12.310 + int edgeNum() const {
12.311 + int i=0;
12.312 + Edge e;
12.313 + for (first(e); e!=INVALID; next(e)) ++i;
12.314 + return i;
12.315 + }
12.316 +
12.317 +
12.318 + };
12.319 +
12.320 + /*! \brief A graph adaptor for hiding nodes and edges from a graph.
12.321 +
12.322 + \warning Graph adaptors are in even more experimental state than the other
12.323 + parts of the lib. Use them at you own risk.
12.324 +
12.325 + SubGraphAdaptor shows the graph with filtered node-set and
12.326 + edge-set.
12.327 + Let \f$G=(V, A)\f$ be a directed graph
12.328 + and suppose that the graph instance \c g of type ListGraph implements
12.329 + \f$G\f$.
12.330 + Let moreover \f$b_V\f$ and
12.331 + \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
12.332 + SubGraphAdaptor<...>::NodeIt iterates
12.333 + on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
12.334 + SubGraphAdaptor<...>::EdgeIt iterates
12.335 + on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
12.336 + SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
12.337 + only on edges leaving and entering a specific node which have true value.
12.338 +
12.339 + We have to note that this does not mean that an
12.340 + induced subgraph is obtained, the node-iterator cares only the filter
12.341 + on the node-set, and the edge-iterators care only the filter on the
12.342 + edge-set.
12.343 + \code
12.344 + typedef ListGraph Graph;
12.345 + Graph g;
12.346 + typedef Graph::Node Node;
12.347 + typedef Graph::Edge Edge;
12.348 + Node u=g.addNode(); //node of id 0
12.349 + Node v=g.addNode(); //node of id 1
12.350 + Node e=g.addEdge(u, v); //edge of id 0
12.351 + Node f=g.addEdge(v, u); //edge of id 1
12.352 + Graph::NodeMap<bool> nm(g, true);
12.353 + nm.set(u, false);
12.354 + Graph::EdgeMap<bool> em(g, true);
12.355 + em.set(e, false);
12.356 + typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
12.357 + SubGW gw(g, nm, em);
12.358 + for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
12.359 + std::cout << ":-)" << std::endl;
12.360 + for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
12.361 + \endcode
12.362 + The output of the above code is the following.
12.363 + \code
12.364 + 1
12.365 + :-)
12.366 + 1
12.367 + \endcode
12.368 + Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
12.369 + \c Graph::Node that is why \c g.id(n) can be applied.
12.370 +
12.371 + For other examples see also the documentation of NodeSubGraphAdaptor and
12.372 + EdgeSubGraphAdaptor.
12.373 +
12.374 + \author Marton Makai
12.375 + */
12.376 + template<typename _Graph, typename NodeFilterMap,
12.377 + typename EdgeFilterMap>
12.378 + class SubGraphAdaptor :
12.379 + public IterableGraphExtender<
12.380 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
12.381 + public:
12.382 + typedef _Graph Graph;
12.383 + typedef IterableGraphExtender<
12.384 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
12.385 + protected:
12.386 + SubGraphAdaptor() { }
12.387 + public:
12.388 + SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
12.389 + EdgeFilterMap& _edge_filter_map) {
12.390 + setGraph(_graph);
12.391 + setNodeFilterMap(_node_filter_map);
12.392 + setEdgeFilterMap(_edge_filter_map);
12.393 + }
12.394 + };
12.395 +
12.396 +
12.397 +
12.398 + /*! \brief An adaptor for hiding nodes from a graph.
12.399 +
12.400 + \warning Graph adaptors are in even more experimental state than the other
12.401 + parts of the lib. Use them at you own risk.
12.402 +
12.403 + An adaptor for hiding nodes from a graph.
12.404 + This adaptor specializes SubGraphAdaptor in the way that only the node-set
12.405 + can be filtered. Note that this does not mean of considering induced
12.406 + subgraph, the edge-iterators consider the original edge-set.
12.407 + \author Marton Makai
12.408 + */
12.409 + template<typename Graph, typename NodeFilterMap>
12.410 + class NodeSubGraphAdaptor :
12.411 + public SubGraphAdaptor<Graph, NodeFilterMap,
12.412 + ConstMap<typename Graph::Edge,bool> > {
12.413 + public:
12.414 + typedef SubGraphAdaptor<Graph, NodeFilterMap,
12.415 + ConstMap<typename Graph::Edge,bool> > Parent;
12.416 + protected:
12.417 + ConstMap<typename Graph::Edge, bool> const_true_map;
12.418 + public:
12.419 + NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
12.420 + Parent(), const_true_map(true) {
12.421 + Parent::setGraph(_graph);
12.422 + Parent::setNodeFilterMap(_node_filter_map);
12.423 + Parent::setEdgeFilterMap(const_true_map);
12.424 + }
12.425 + };
12.426 +
12.427 +
12.428 + /*! \brief An adaptor for hiding edges from a graph.
12.429 +
12.430 + \warning Graph adaptors are in even more experimental state than the other
12.431 + parts of the lib. Use them at you own risk.
12.432 +
12.433 + An adaptor for hiding edges from a graph.
12.434 + This adaptor specializes SubGraphAdaptor in the way that only the edge-set
12.435 + can be filtered. The usefulness of this adaptor is demonstrated in the
12.436 + problem of searching a maximum number of edge-disjoint shortest paths
12.437 + between
12.438 + two nodes \c s and \c t. Shortest here means being shortest w.r.t.
12.439 + non-negative edge-lengths. Note that
12.440 + the comprehension of the presented solution
12.441 + need's some elementary knowledge from combinatorial optimization.
12.442 +
12.443 + If a single shortest path is to be
12.444 + searched between \c s and \c t, then this can be done easily by
12.445 + applying the Dijkstra algorithm. What happens, if a maximum number of
12.446 + edge-disjoint shortest paths is to be computed. It can be proved that an
12.447 + edge can be in a shortest path if and only if it is tight with respect to
12.448 + the potential function computed by Dijkstra. Moreover, any path containing
12.449 + only such edges is a shortest one. Thus we have to compute a maximum number
12.450 + of edge-disjoint paths between \c s and \c t in the graph which has edge-set
12.451 + all the tight edges. The computation will be demonstrated on the following
12.452 + graph, which is read from a dimacs file.
12.453 +
12.454 + \dot
12.455 + digraph lemon_dot_example {
12.456 + node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
12.457 + n0 [ label="0 (s)" ];
12.458 + n1 [ label="1" ];
12.459 + n2 [ label="2" ];
12.460 + n3 [ label="3" ];
12.461 + n4 [ label="4" ];
12.462 + n5 [ label="5" ];
12.463 + n6 [ label="6 (t)" ];
12.464 + edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
12.465 + n5 -> n6 [ label="9, length:4" ];
12.466 + n4 -> n6 [ label="8, length:2" ];
12.467 + n3 -> n5 [ label="7, length:1" ];
12.468 + n2 -> n5 [ label="6, length:3" ];
12.469 + n2 -> n6 [ label="5, length:5" ];
12.470 + n2 -> n4 [ label="4, length:2" ];
12.471 + n1 -> n4 [ label="3, length:3" ];
12.472 + n0 -> n3 [ label="2, length:1" ];
12.473 + n0 -> n2 [ label="1, length:2" ];
12.474 + n0 -> n1 [ label="0, length:3" ];
12.475 + }
12.476 + \enddot
12.477 +
12.478 + \code
12.479 + Graph g;
12.480 + Node s, t;
12.481 + LengthMap length(g);
12.482 +
12.483 + readDimacs(std::cin, g, length, s, t);
12.484 +
12.485 + cout << "edges with lengths (of form id, source--length->target): " << endl;
12.486 + for(EdgeIt e(g); e!=INVALID; ++e)
12.487 + cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
12.488 + << length[e] << "->" << g.id(g.target(e)) << endl;
12.489 +
12.490 + cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
12.491 + \endcode
12.492 + Next, the potential function is computed with Dijkstra.
12.493 + \code
12.494 + typedef Dijkstra<Graph, LengthMap> Dijkstra;
12.495 + Dijkstra dijkstra(g, length);
12.496 + dijkstra.run(s);
12.497 + \endcode
12.498 + Next, we consrtruct a map which filters the edge-set to the tight edges.
12.499 + \code
12.500 + typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
12.501 + TightEdgeFilter;
12.502 + TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
12.503 +
12.504 + typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
12.505 + SubGW gw(g, tight_edge_filter);
12.506 + \endcode
12.507 + Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
12.508 + with a max flow algorithm Preflow.
12.509 + \code
12.510 + ConstMap<Edge, int> const_1_map(1);
12.511 + Graph::EdgeMap<int> flow(g, 0);
12.512 +
12.513 + Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
12.514 + preflow(gw, s, t, const_1_map, flow);
12.515 + preflow.run();
12.516 + \endcode
12.517 + Last, the output is:
12.518 + \code
12.519 + cout << "maximum number of edge-disjoint shortest path: "
12.520 + << preflow.flowValue() << endl;
12.521 + cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
12.522 + << endl;
12.523 + for(EdgeIt e(g); e!=INVALID; ++e)
12.524 + if (flow[e])
12.525 + cout << " " << g.id(g.source(e)) << "--"
12.526 + << length[e] << "->" << g.id(g.target(e)) << endl;
12.527 + \endcode
12.528 + The program has the following (expected :-)) output:
12.529 + \code
12.530 + edges with lengths (of form id, source--length->target):
12.531 + 9, 5--4->6
12.532 + 8, 4--2->6
12.533 + 7, 3--1->5
12.534 + 6, 2--3->5
12.535 + 5, 2--5->6
12.536 + 4, 2--2->4
12.537 + 3, 1--3->4
12.538 + 2, 0--1->3
12.539 + 1, 0--2->2
12.540 + 0, 0--3->1
12.541 + s: 0 t: 6
12.542 + maximum number of edge-disjoint shortest path: 2
12.543 + edges of the maximum number of edge-disjoint shortest s-t paths:
12.544 + 9, 5--4->6
12.545 + 8, 4--2->6
12.546 + 7, 3--1->5
12.547 + 4, 2--2->4
12.548 + 2, 0--1->3
12.549 + 1, 0--2->2
12.550 + \endcode
12.551 +
12.552 + \author Marton Makai
12.553 + */
12.554 + template<typename Graph, typename EdgeFilterMap>
12.555 + class EdgeSubGraphAdaptor :
12.556 + public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
12.557 + EdgeFilterMap> {
12.558 + public:
12.559 + typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
12.560 + EdgeFilterMap> Parent;
12.561 + protected:
12.562 + ConstMap<typename Graph::Node, bool> const_true_map;
12.563 + public:
12.564 + EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
12.565 + Parent(), const_true_map(true) {
12.566 + Parent::setGraph(_graph);
12.567 + Parent::setNodeFilterMap(const_true_map);
12.568 + Parent::setEdgeFilterMap(_edge_filter_map);
12.569 + }
12.570 + };
12.571 +
12.572 + template <typename _Graph>
12.573 + class UndirGraphAdaptorBase :
12.574 + public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
12.575 + public:
12.576 + typedef _Graph Graph;
12.577 + typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
12.578 + protected:
12.579 + UndirGraphAdaptorBase() : Parent() { }
12.580 + public:
12.581 + typedef typename Parent::UndirEdge UndirEdge;
12.582 + typedef typename Parent::Edge Edge;
12.583 +
12.584 + /// \bug Why cant an edge say that it is forward or not???
12.585 + /// By this, a pointer to the graph have to be stored
12.586 + /// The implementation
12.587 + template <typename T>
12.588 + class EdgeMap {
12.589 + protected:
12.590 + const UndirGraphAdaptorBase<_Graph>* g;
12.591 + template <typename TT> friend class EdgeMap;
12.592 + typename _Graph::template EdgeMap<T> forward_map, backward_map;
12.593 + public:
12.594 + typedef T Value;
12.595 + typedef Edge Key;
12.596 +
12.597 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
12.598 + forward_map(*(g->graph)), backward_map(*(g->graph)) { }
12.599 +
12.600 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
12.601 + forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
12.602 +
12.603 + void set(Edge e, T a) {
12.604 + if (g->forward(e))
12.605 + forward_map.set(e, a);
12.606 + else
12.607 + backward_map.set(e, a);
12.608 + }
12.609 +
12.610 + T operator[](Edge e) const {
12.611 + if (g->forward(e))
12.612 + return forward_map[e];
12.613 + else
12.614 + return backward_map[e];
12.615 + }
12.616 + };
12.617 +
12.618 + template <typename T>
12.619 + class UndirEdgeMap {
12.620 + template <typename TT> friend class UndirEdgeMap;
12.621 + typename _Graph::template EdgeMap<T> map;
12.622 + public:
12.623 + typedef T Value;
12.624 + typedef UndirEdge Key;
12.625 +
12.626 + UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
12.627 + map(*(g.graph)) { }
12.628 +
12.629 + UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
12.630 + map(*(g.graph), a) { }
12.631 +
12.632 + void set(UndirEdge e, T a) {
12.633 + map.set(e, a);
12.634 + }
12.635 +
12.636 + T operator[](UndirEdge e) const {
12.637 + return map[e];
12.638 + }
12.639 + };
12.640 +
12.641 + };
12.642 +
12.643 + /// \brief An undirected graph is made from a directed graph by an adaptor
12.644 + ///
12.645 + /// Undocumented, untested!!!
12.646 + /// If somebody knows nice demo application, let's polulate it.
12.647 + ///
12.648 + /// \author Marton Makai
12.649 + template<typename _Graph>
12.650 + class UndirGraphAdaptor :
12.651 + public IterableUndirGraphExtender<
12.652 + UndirGraphAdaptorBase<_Graph> > {
12.653 + public:
12.654 + typedef _Graph Graph;
12.655 + typedef IterableUndirGraphExtender<
12.656 + UndirGraphAdaptorBase<_Graph> > Parent;
12.657 + protected:
12.658 + UndirGraphAdaptor() { }
12.659 + public:
12.660 + UndirGraphAdaptor(_Graph& _graph) {
12.661 + setGraph(_graph);
12.662 + }
12.663 + };
12.664 +
12.665 +
12.666 + template <typename _Graph,
12.667 + typename ForwardFilterMap, typename BackwardFilterMap>
12.668 + class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
12.669 + public:
12.670 + typedef _Graph Graph;
12.671 + typedef GraphAdaptorBase<_Graph> Parent;
12.672 + protected:
12.673 + ForwardFilterMap* forward_filter;
12.674 + BackwardFilterMap* backward_filter;
12.675 + SubBidirGraphAdaptorBase() : Parent(),
12.676 + forward_filter(0), backward_filter(0) { }
12.677 +
12.678 + void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
12.679 + forward_filter=&_forward_filter;
12.680 + }
12.681 + void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
12.682 + backward_filter=&_backward_filter;
12.683 + }
12.684 +
12.685 + public:
12.686 +// SubGraphAdaptorBase(Graph& _graph,
12.687 +// NodeFilterMap& _node_filter_map,
12.688 +// EdgeFilterMap& _edge_filter_map) :
12.689 +// Parent(&_graph),
12.690 +// node_filter_map(&node_filter_map),
12.691 +// edge_filter_map(&edge_filter_map) { }
12.692 +
12.693 + typedef typename Parent::Node Node;
12.694 + typedef typename _Graph::Edge GraphEdge;
12.695 + template <typename T> class EdgeMap;
12.696 + /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
12.697 + /// _Graph::Edge. It contains an extra bool flag which is true
12.698 + /// if and only if the
12.699 + /// edge is the backward version of the original edge.
12.700 + class Edge : public _Graph::Edge {
12.701 + friend class SubBidirGraphAdaptorBase<
12.702 + Graph, ForwardFilterMap, BackwardFilterMap>;
12.703 + template<typename T> friend class EdgeMap;
12.704 + protected:
12.705 + bool backward; //true, iff backward
12.706 + public:
12.707 + Edge() { }
12.708 + /// \todo =false is needed, or causes problems?
12.709 + /// If \c _backward is false, then we get an edge corresponding to the
12.710 + /// original one, otherwise its oppositely directed pair is obtained.
12.711 + Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
12.712 + _Graph::Edge(e), backward(_backward) { }
12.713 + Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
12.714 + bool operator==(const Edge& v) const {
12.715 + return (this->backward==v.backward &&
12.716 + static_cast<typename _Graph::Edge>(*this)==
12.717 + static_cast<typename _Graph::Edge>(v));
12.718 + }
12.719 + bool operator!=(const Edge& v) const {
12.720 + return (this->backward!=v.backward ||
12.721 + static_cast<typename _Graph::Edge>(*this)!=
12.722 + static_cast<typename _Graph::Edge>(v));
12.723 + }
12.724 + };
12.725 +
12.726 + void first(Node& i) const {
12.727 + Parent::first(i);
12.728 + }
12.729 +
12.730 + void first(Edge& i) const {
12.731 + Parent::first(i);
12.732 + i.backward=false;
12.733 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.734 + !(*forward_filter)[i]) Parent::next(i);
12.735 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
12.736 + Parent::first(i);
12.737 + i.backward=true;
12.738 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.739 + !(*backward_filter)[i]) Parent::next(i);
12.740 + }
12.741 + }
12.742 +
12.743 + void firstIn(Edge& i, const Node& n) const {
12.744 + Parent::firstIn(i, n);
12.745 + i.backward=false;
12.746 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.747 + !(*forward_filter)[i]) Parent::nextIn(i);
12.748 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
12.749 + Parent::firstOut(i, n);
12.750 + i.backward=true;
12.751 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.752 + !(*backward_filter)[i]) Parent::nextOut(i);
12.753 + }
12.754 + }
12.755 +
12.756 + void firstOut(Edge& i, const Node& n) const {
12.757 + Parent::firstOut(i, n);
12.758 + i.backward=false;
12.759 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.760 + !(*forward_filter)[i]) Parent::nextOut(i);
12.761 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
12.762 + Parent::firstIn(i, n);
12.763 + i.backward=true;
12.764 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.765 + !(*backward_filter)[i]) Parent::nextIn(i);
12.766 + }
12.767 + }
12.768 +
12.769 + void next(Node& i) const {
12.770 + Parent::next(i);
12.771 + }
12.772 +
12.773 + void next(Edge& i) const {
12.774 + if (!(i.backward)) {
12.775 + Parent::next(i);
12.776 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.777 + !(*forward_filter)[i]) Parent::next(i);
12.778 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
12.779 + Parent::first(i);
12.780 + i.backward=true;
12.781 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.782 + !(*backward_filter)[i]) Parent::next(i);
12.783 + }
12.784 + } else {
12.785 + Parent::next(i);
12.786 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.787 + !(*backward_filter)[i]) Parent::next(i);
12.788 + }
12.789 + }
12.790 +
12.791 + void nextIn(Edge& i) const {
12.792 + if (!(i.backward)) {
12.793 + Node n=Parent::target(i);
12.794 + Parent::nextIn(i);
12.795 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.796 + !(*forward_filter)[i]) Parent::nextIn(i);
12.797 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
12.798 + Parent::firstOut(i, n);
12.799 + i.backward=true;
12.800 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.801 + !(*backward_filter)[i]) Parent::nextOut(i);
12.802 + }
12.803 + } else {
12.804 + Parent::nextOut(i);
12.805 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.806 + !(*backward_filter)[i]) Parent::nextOut(i);
12.807 + }
12.808 + }
12.809 +
12.810 + void nextOut(Edge& i) const {
12.811 + if (!(i.backward)) {
12.812 + Node n=Parent::source(i);
12.813 + Parent::nextOut(i);
12.814 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.815 + !(*forward_filter)[i]) Parent::nextOut(i);
12.816 + if (*static_cast<GraphEdge*>(&i)==INVALID) {
12.817 + Parent::firstIn(i, n);
12.818 + i.backward=true;
12.819 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.820 + !(*backward_filter)[i]) Parent::nextIn(i);
12.821 + }
12.822 + } else {
12.823 + Parent::nextIn(i);
12.824 + while (*static_cast<GraphEdge*>(&i)!=INVALID &&
12.825 + !(*backward_filter)[i]) Parent::nextIn(i);
12.826 + }
12.827 + }
12.828 +
12.829 + Node source(Edge e) const {
12.830 + return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
12.831 + Node target(Edge e) const {
12.832 + return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
12.833 +
12.834 + /// Gives back the opposite edge.
12.835 + Edge opposite(const Edge& e) const {
12.836 + Edge f=e;
12.837 + f.backward=!f.backward;
12.838 + return f;
12.839 + }
12.840 +
12.841 + /// \warning This is a linear time operation and works only if
12.842 + /// \c Graph::EdgeIt is defined.
12.843 + /// \todo hmm
12.844 + int edgeNum() const {
12.845 + int i=0;
12.846 + Edge e;
12.847 + for (first(e); e!=INVALID; next(e)) ++i;
12.848 + return i;
12.849 + }
12.850 +
12.851 + bool forward(const Edge& e) const { return !e.backward; }
12.852 + bool backward(const Edge& e) const { return e.backward; }
12.853 +
12.854 + template <typename T>
12.855 + /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
12.856 + /// _Graph::EdgeMap one for the forward edges and
12.857 + /// one for the backward edges.
12.858 + class EdgeMap {
12.859 + template <typename TT> friend class EdgeMap;
12.860 + typename _Graph::template EdgeMap<T> forward_map, backward_map;
12.861 + public:
12.862 + typedef T Value;
12.863 + typedef Edge Key;
12.864 +
12.865 + EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
12.866 + ForwardFilterMap, BackwardFilterMap>& g) :
12.867 + forward_map(*(g.graph)), backward_map(*(g.graph)) { }
12.868 +
12.869 + EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
12.870 + ForwardFilterMap, BackwardFilterMap>& g, T a) :
12.871 + forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
12.872 +
12.873 + void set(Edge e, T a) {
12.874 + if (!e.backward)
12.875 + forward_map.set(e, a);
12.876 + else
12.877 + backward_map.set(e, a);
12.878 + }
12.879 +
12.880 +// typename _Graph::template EdgeMap<T>::ConstReference
12.881 +// operator[](Edge e) const {
12.882 +// if (!e.backward)
12.883 +// return forward_map[e];
12.884 +// else
12.885 +// return backward_map[e];
12.886 +// }
12.887 +
12.888 +// typename _Graph::template EdgeMap<T>::Reference
12.889 + T operator[](Edge e) const {
12.890 + if (!e.backward)
12.891 + return forward_map[e];
12.892 + else
12.893 + return backward_map[e];
12.894 + }
12.895 +
12.896 + void update() {
12.897 + forward_map.update();
12.898 + backward_map.update();
12.899 + }
12.900 + };
12.901 +
12.902 + };
12.903 +
12.904 +
12.905 + ///\brief An adaptor for composing a subgraph of a
12.906 + /// bidirected graph made from a directed one.
12.907 + ///
12.908 + /// An adaptor for composing a subgraph of a
12.909 + /// bidirected graph made from a directed one.
12.910 + ///
12.911 + ///\warning Graph adaptors are in even more experimental state than the other
12.912 + ///parts of the lib. Use them at you own risk.
12.913 + ///
12.914 + /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
12.915 + /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
12.916 + /// reversing its orientation. We are given moreover two bool valued
12.917 + /// maps on the edge-set,
12.918 + /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
12.919 + /// SubBidirGraphAdaptor implements the graph structure with node-set
12.920 + /// \f$V\f$ and edge-set
12.921 + /// \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$.
12.922 + /// The purpose of writing + instead of union is because parallel
12.923 + /// edges can arise. (Similarly, antiparallel edges also can arise).
12.924 + /// In other words, a subgraph of the bidirected graph obtained, which
12.925 + /// is given by orienting the edges of the original graph in both directions.
12.926 + /// As the oppositely directed edges are logically different,
12.927 + /// the maps are able to attach different values for them.
12.928 + ///
12.929 + /// An example for such a construction is \c RevGraphAdaptor where the
12.930 + /// forward_filter is everywhere false and the backward_filter is
12.931 + /// everywhere true. We note that for sake of efficiency,
12.932 + /// \c RevGraphAdaptor is implemented in a different way.
12.933 + /// But BidirGraphAdaptor is obtained from
12.934 + /// SubBidirGraphAdaptor by considering everywhere true
12.935 + /// valued maps both for forward_filter and backward_filter.
12.936 + ///
12.937 + /// The most important application of SubBidirGraphAdaptor
12.938 + /// is ResGraphAdaptor, which stands for the residual graph in directed
12.939 + /// flow and circulation problems.
12.940 + /// As adaptors usually, the SubBidirGraphAdaptor implements the
12.941 + /// above mentioned graph structure without its physical storage,
12.942 + /// that is the whole stuff is stored in constant memory.
12.943 + template<typename _Graph,
12.944 + typename ForwardFilterMap, typename BackwardFilterMap>
12.945 + class SubBidirGraphAdaptor :
12.946 + public IterableGraphExtender<
12.947 + SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
12.948 + public:
12.949 + typedef _Graph Graph;
12.950 + typedef IterableGraphExtender<
12.951 + SubBidirGraphAdaptorBase<
12.952 + _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
12.953 + protected:
12.954 + SubBidirGraphAdaptor() { }
12.955 + public:
12.956 + SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
12.957 + BackwardFilterMap& _backward_filter) {
12.958 + setGraph(_graph);
12.959 + setForwardFilterMap(_forward_filter);
12.960 + setBackwardFilterMap(_backward_filter);
12.961 + }
12.962 + };
12.963 +
12.964 +
12.965 +
12.966 + ///\brief An adaptor for composing bidirected graph from a directed one.
12.967 + ///
12.968 + ///\warning Graph adaptors are in even more experimental state than the other
12.969 + ///parts of the lib. Use them at you own risk.
12.970 + ///
12.971 + /// An adaptor for composing bidirected graph from a directed one.
12.972 + /// A bidirected graph is composed over the directed one without physical
12.973 + /// storage. As the oppositely directed edges are logically different ones
12.974 + /// the maps are able to attach different values for them.
12.975 + template<typename Graph>
12.976 + class BidirGraphAdaptor :
12.977 + public SubBidirGraphAdaptor<
12.978 + Graph,
12.979 + ConstMap<typename Graph::Edge, bool>,
12.980 + ConstMap<typename Graph::Edge, bool> > {
12.981 + public:
12.982 + typedef SubBidirGraphAdaptor<
12.983 + Graph,
12.984 + ConstMap<typename Graph::Edge, bool>,
12.985 + ConstMap<typename Graph::Edge, bool> > Parent;
12.986 + protected:
12.987 + ConstMap<typename Graph::Edge, bool> cm;
12.988 +
12.989 + BidirGraphAdaptor() : Parent(), cm(true) {
12.990 + Parent::setForwardFilterMap(cm);
12.991 + Parent::setBackwardFilterMap(cm);
12.992 + }
12.993 + public:
12.994 + BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
12.995 + Parent::setGraph(_graph);
12.996 + Parent::setForwardFilterMap(cm);
12.997 + Parent::setBackwardFilterMap(cm);
12.998 + }
12.999 +
12.1000 + int edgeNum() const {
12.1001 + return 2*this->graph->edgeNum();
12.1002 + }
12.1003 + // KEEP_MAPS(Parent, BidirGraphAdaptor);
12.1004 + };
12.1005 +
12.1006 +
12.1007 + template<typename Graph, typename Number,
12.1008 + typename CapacityMap, typename FlowMap>
12.1009 + class ResForwardFilter {
12.1010 + // const Graph* graph;
12.1011 + const CapacityMap* capacity;
12.1012 + const FlowMap* flow;
12.1013 + public:
12.1014 + ResForwardFilter(/*const Graph& _graph, */
12.1015 + const CapacityMap& _capacity, const FlowMap& _flow) :
12.1016 + /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
12.1017 + ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
12.1018 + void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
12.1019 + void setFlow(const FlowMap& _flow) { flow=&_flow; }
12.1020 + bool operator[](const typename Graph::Edge& e) const {
12.1021 + return (Number((*flow)[e]) < Number((*capacity)[e]));
12.1022 + }
12.1023 + };
12.1024 +
12.1025 + template<typename Graph, typename Number,
12.1026 + typename CapacityMap, typename FlowMap>
12.1027 + class ResBackwardFilter {
12.1028 + const CapacityMap* capacity;
12.1029 + const FlowMap* flow;
12.1030 + public:
12.1031 + ResBackwardFilter(/*const Graph& _graph,*/
12.1032 + const CapacityMap& _capacity, const FlowMap& _flow) :
12.1033 + /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
12.1034 + ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
12.1035 + void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
12.1036 + void setFlow(const FlowMap& _flow) { flow=&_flow; }
12.1037 + bool operator[](const typename Graph::Edge& e) const {
12.1038 + return (Number(0) < Number((*flow)[e]));
12.1039 + }
12.1040 + };
12.1041 +
12.1042 +
12.1043 + /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
12.1044 +
12.1045 + An adaptor for composing the residual graph for directed flow and circulation problems.
12.1046 + Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
12.1047 + number type. Let moreover
12.1048 + \f$f,c:A\to F\f$, be functions on the edge-set.
12.1049 + In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
12.1050 + and \f$c\f$ for a capacity function.
12.1051 + Suppose that a graph instange \c g of type
12.1052 + \c ListGraph implements \f$G\f$.
12.1053 + \code
12.1054 + ListGraph g;
12.1055 + \endcode
12.1056 + Then RevGraphAdaptor implements the graph structure with node-set
12.1057 + \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
12.1058 + \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
12.1059 + \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
12.1060 + i.e. the so called residual graph.
12.1061 + When we take the union \f$A_{forward}\cup A_{backward}\f$,
12.1062 + multilicities are counted, i.e. if an edge is in both
12.1063 + \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
12.1064 + appears twice.
12.1065 + The following code shows how
12.1066 + such an instance can be constructed.
12.1067 + \code
12.1068 + typedef ListGraph Graph;
12.1069 + Graph::EdgeMap<int> f(g);
12.1070 + Graph::EdgeMap<int> c(g);
12.1071 + ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
12.1072 + \endcode
12.1073 + \author Marton Makai
12.1074 + */
12.1075 + template<typename Graph, typename Number,
12.1076 + typename CapacityMap, typename FlowMap>
12.1077 + class ResGraphAdaptor :
12.1078 + public SubBidirGraphAdaptor<
12.1079 + Graph,
12.1080 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
12.1081 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
12.1082 + public:
12.1083 + typedef SubBidirGraphAdaptor<
12.1084 + Graph,
12.1085 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
12.1086 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
12.1087 + protected:
12.1088 + const CapacityMap* capacity;
12.1089 + FlowMap* flow;
12.1090 + ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
12.1091 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
12.1092 + ResGraphAdaptor() : Parent(),
12.1093 + capacity(0), flow(0) { }
12.1094 + void setCapacityMap(const CapacityMap& _capacity) {
12.1095 + capacity=&_capacity;
12.1096 + forward_filter.setCapacity(_capacity);
12.1097 + backward_filter.setCapacity(_capacity);
12.1098 + }
12.1099 + void setFlowMap(FlowMap& _flow) {
12.1100 + flow=&_flow;
12.1101 + forward_filter.setFlow(_flow);
12.1102 + backward_filter.setFlow(_flow);
12.1103 + }
12.1104 + public:
12.1105 + ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
12.1106 + FlowMap& _flow) :
12.1107 + Parent(), capacity(&_capacity), flow(&_flow),
12.1108 + forward_filter(/*_graph,*/ _capacity, _flow),
12.1109 + backward_filter(/*_graph,*/ _capacity, _flow) {
12.1110 + Parent::setGraph(_graph);
12.1111 + Parent::setForwardFilterMap(forward_filter);
12.1112 + Parent::setBackwardFilterMap(backward_filter);
12.1113 + }
12.1114 +
12.1115 + typedef typename Parent::Edge Edge;
12.1116 +
12.1117 + void augment(const Edge& e, Number a) const {
12.1118 + if (Parent::forward(e))
12.1119 + flow->set(e, (*flow)[e]+a);
12.1120 + else
12.1121 + flow->set(e, (*flow)[e]-a);
12.1122 + }
12.1123 +
12.1124 + /// \brief Residual capacity map.
12.1125 + ///
12.1126 + /// In generic residual graphs the residual capacity can be obtained
12.1127 + /// as a map.
12.1128 + class ResCap {
12.1129 + protected:
12.1130 + const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
12.1131 + public:
12.1132 + typedef Number Value;
12.1133 + typedef Edge Key;
12.1134 + ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
12.1135 + _res_graph) : res_graph(&_res_graph) { }
12.1136 + Number operator[](const Edge& e) const {
12.1137 + if (res_graph->forward(e))
12.1138 + return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
12.1139 + else
12.1140 + return (*(res_graph->flow))[e];
12.1141 + }
12.1142 + };
12.1143 +
12.1144 + // KEEP_MAPS(Parent, ResGraphAdaptor);
12.1145 + };
12.1146 +
12.1147 +
12.1148 +
12.1149 + template <typename _Graph, typename FirstOutEdgesMap>
12.1150 + class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
12.1151 + public:
12.1152 + typedef _Graph Graph;
12.1153 + typedef GraphAdaptorBase<_Graph> Parent;
12.1154 + protected:
12.1155 + FirstOutEdgesMap* first_out_edges;
12.1156 + ErasingFirstGraphAdaptorBase() : Parent(),
12.1157 + first_out_edges(0) { }
12.1158 +
12.1159 + void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
12.1160 + first_out_edges=&_first_out_edges;
12.1161 + }
12.1162 +
12.1163 + public:
12.1164 +
12.1165 + typedef typename Parent::Node Node;
12.1166 + typedef typename Parent::Edge Edge;
12.1167 +
12.1168 + void firstOut(Edge& i, const Node& n) const {
12.1169 + i=(*first_out_edges)[n];
12.1170 + }
12.1171 +
12.1172 + void erase(const Edge& e) const {
12.1173 + Node n=source(e);
12.1174 + Edge f=e;
12.1175 + Parent::nextOut(f);
12.1176 + first_out_edges->set(n, f);
12.1177 + }
12.1178 + };
12.1179 +
12.1180 +
12.1181 + /// For blocking flows.
12.1182 +
12.1183 + ///\warning Graph adaptors are in even more experimental state than the other
12.1184 + ///parts of the lib. Use them at you own risk.
12.1185 + ///
12.1186 + /// This graph adaptor is used for on-the-fly
12.1187 + /// Dinits blocking flow computations.
12.1188 + /// For each node, an out-edge is stored which is used when the
12.1189 + /// \code
12.1190 + /// OutEdgeIt& first(OutEdgeIt&, const Node&)
12.1191 + /// \endcode
12.1192 + /// is called.
12.1193 + ///
12.1194 + /// \author Marton Makai
12.1195 + template <typename _Graph, typename FirstOutEdgesMap>
12.1196 + class ErasingFirstGraphAdaptor :
12.1197 + public IterableGraphExtender<
12.1198 + ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
12.1199 + public:
12.1200 + typedef _Graph Graph;
12.1201 + typedef IterableGraphExtender<
12.1202 + ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
12.1203 + ErasingFirstGraphAdaptor(Graph& _graph,
12.1204 + FirstOutEdgesMap& _first_out_edges) {
12.1205 + setGraph(_graph);
12.1206 + setFirstOutEdgesMap(_first_out_edges);
12.1207 + }
12.1208 +
12.1209 + };
12.1210 +
12.1211 + ///@}
12.1212 +
12.1213 +} //namespace lemon
12.1214 +
12.1215 +#endif //LEMON_GRAPH_ADAPTOR_H
12.1216 +
13.1 --- a/src/lemon/graph_wrapper.h Mon May 02 05:49:33 2005 +0000
13.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
13.3 @@ -1,1213 +0,0 @@
13.4 -/* -*- C++ -*-
13.5 - * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
13.6 - *
13.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
13.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
13.9 - *
13.10 - * Permission to use, modify and distribute this software is granted
13.11 - * provided that this copyright notice appears in all copies. For
13.12 - * precise terms see the accompanying LICENSE file.
13.13 - *
13.14 - * This software is provided "AS IS" with no warranty of any kind,
13.15 - * express or implied, and with no claim as to its suitability for any
13.16 - * purpose.
13.17 - *
13.18 - */
13.19 -
13.20 -#ifndef LEMON_GRAPH_WRAPPER_H
13.21 -#define LEMON_GRAPH_WRAPPER_H
13.22 -
13.23 -///\ingroup gwrappers
13.24 -///\file
13.25 -///\brief Several graph wrappers.
13.26 -///
13.27 -///This file contains several useful graph wrapper functions.
13.28 -///
13.29 -///\author Marton Makai
13.30 -
13.31 -#include <lemon/invalid.h>
13.32 -#include <lemon/maps.h>
13.33 -#include <lemon/bits/iterable_graph_extender.h>
13.34 -#include <lemon/bits/undir_graph_extender.h>
13.35 -#include <iostream>
13.36 -
13.37 -namespace lemon {
13.38 -
13.39 - // Graph wrappers
13.40 -
13.41 - /*!
13.42 - \addtogroup gwrappers
13.43 - @{
13.44 - */
13.45 -
13.46 - /*!
13.47 - Base type for the Graph Wrappers
13.48 -
13.49 - \warning Graph wrappers are in even more experimental state than the other
13.50 - parts of the lib. Use them at you own risk.
13.51 -
13.52 - This is the base type for most of LEMON graph wrappers.
13.53 - This class implements a trivial graph wrapper i.e. it only wraps the
13.54 - functions and types of the graph. The purpose of this class is to
13.55 - make easier implementing graph wrappers. E.g. if a wrapper is
13.56 - considered which differs from the wrapped graph only in some of its
13.57 - functions or types, then it can be derived from GraphWrapper, and only the
13.58 - differences should be implemented.
13.59 -
13.60 - \author Marton Makai
13.61 - */
13.62 - template<typename _Graph>
13.63 - class GraphWrapperBase {
13.64 - public:
13.65 - typedef _Graph Graph;
13.66 - /// \todo Is it needed?
13.67 - typedef Graph BaseGraph;
13.68 - typedef Graph ParentGraph;
13.69 -
13.70 - protected:
13.71 - Graph* graph;
13.72 - GraphWrapperBase() : graph(0) { }
13.73 - void setGraph(Graph& _graph) { graph=&_graph; }
13.74 -
13.75 - public:
13.76 - GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
13.77 -
13.78 - typedef typename Graph::Node Node;
13.79 - typedef typename Graph::Edge Edge;
13.80 -
13.81 - void first(Node& i) const { graph->first(i); }
13.82 - void first(Edge& i) const { graph->first(i); }
13.83 - void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
13.84 - void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
13.85 -
13.86 - void next(Node& i) const { graph->next(i); }
13.87 - void next(Edge& i) const { graph->next(i); }
13.88 - void nextIn(Edge& i) const { graph->nextIn(i); }
13.89 - void nextOut(Edge& i) const { graph->nextOut(i); }
13.90 -
13.91 - Node source(const Edge& e) const { return graph->source(e); }
13.92 - Node target(const Edge& e) const { return graph->target(e); }
13.93 -
13.94 - int nodeNum() const { return graph->nodeNum(); }
13.95 - int edgeNum() const { return graph->edgeNum(); }
13.96 -
13.97 - Node addNode() const { return Node(graph->addNode()); }
13.98 - Edge addEdge(const Node& source, const Node& target) const {
13.99 - return Edge(graph->addEdge(source, target)); }
13.100 -
13.101 - void erase(const Node& i) const { graph->erase(i); }
13.102 - void erase(const Edge& i) const { graph->erase(i); }
13.103 -
13.104 - void clear() const { graph->clear(); }
13.105 -
13.106 - bool forward(const Edge& e) const { return graph->forward(e); }
13.107 - bool backward(const Edge& e) const { return graph->backward(e); }
13.108 -
13.109 - int id(const Node& v) const { return graph->id(v); }
13.110 - int id(const Edge& e) const { return graph->id(e); }
13.111 -
13.112 - Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
13.113 -
13.114 - template <typename _Value>
13.115 - class NodeMap : public _Graph::template NodeMap<_Value> {
13.116 - public:
13.117 - typedef typename _Graph::template NodeMap<_Value> Parent;
13.118 - NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
13.119 - NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
13.120 - : Parent(*gw.graph, value) { }
13.121 - };
13.122 -
13.123 - template <typename _Value>
13.124 - class EdgeMap : public _Graph::template EdgeMap<_Value> {
13.125 - public:
13.126 - typedef typename _Graph::template EdgeMap<_Value> Parent;
13.127 - EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
13.128 - EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
13.129 - : Parent(*gw.graph, value) { }
13.130 - };
13.131 -
13.132 - };
13.133 -
13.134 - template <typename _Graph>
13.135 - class GraphWrapper :
13.136 - public IterableGraphExtender<GraphWrapperBase<_Graph> > {
13.137 - public:
13.138 - typedef _Graph Graph;
13.139 - typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
13.140 - protected:
13.141 - GraphWrapper() : Parent() { }
13.142 -
13.143 - public:
13.144 - GraphWrapper(Graph& _graph) { setGraph(_graph); }
13.145 - };
13.146 -
13.147 - template <typename _Graph>
13.148 - class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
13.149 - public:
13.150 - typedef _Graph Graph;
13.151 - typedef GraphWrapperBase<_Graph> Parent;
13.152 - protected:
13.153 - RevGraphWrapperBase() : Parent() { }
13.154 - public:
13.155 - typedef typename Parent::Node Node;
13.156 - typedef typename Parent::Edge Edge;
13.157 -
13.158 - // using Parent::first;
13.159 - void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
13.160 - void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
13.161 -
13.162 - // using Parent::next;
13.163 - void nextIn(Edge& i) const { Parent::nextOut(i); }
13.164 - void nextOut(Edge& i) const { Parent::nextIn(i); }
13.165 -
13.166 - Node source(const Edge& e) const { return Parent::target(e); }
13.167 - Node target(const Edge& e) const { return Parent::source(e); }
13.168 - };
13.169 -
13.170 -
13.171 - /// A graph wrapper which reverses the orientation of the edges.
13.172 -
13.173 - ///\warning Graph wrappers are in even more experimental state than the other
13.174 - ///parts of the lib. Use them at you own risk.
13.175 - ///
13.176 - /// Let \f$G=(V, A)\f$ be a directed graph and
13.177 - /// suppose that a graph instange \c g of type
13.178 - /// \c ListGraph implements \f$G\f$.
13.179 - /// \code
13.180 - /// ListGraph g;
13.181 - /// \endcode
13.182 - /// For each directed edge
13.183 - /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
13.184 - /// reversing its orientation.
13.185 - /// Then RevGraphWrapper implements the graph structure with node-set
13.186 - /// \f$V\f$ and edge-set
13.187 - /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
13.188 - /// reversing the orientation of its edges. The following code shows how
13.189 - /// such an instance can be constructed.
13.190 - /// \code
13.191 - /// RevGraphWrapper<ListGraph> gw(g);
13.192 - /// \endcode
13.193 - ///\author Marton Makai
13.194 - template<typename _Graph>
13.195 - class RevGraphWrapper :
13.196 - public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
13.197 - public:
13.198 - typedef _Graph Graph;
13.199 - typedef IterableGraphExtender<
13.200 - RevGraphWrapperBase<_Graph> > Parent;
13.201 - protected:
13.202 - RevGraphWrapper() { }
13.203 - public:
13.204 - RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
13.205 - };
13.206 -
13.207 -
13.208 - template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
13.209 - class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
13.210 - public:
13.211 - typedef _Graph Graph;
13.212 - typedef GraphWrapperBase<_Graph> Parent;
13.213 - protected:
13.214 - NodeFilterMap* node_filter_map;
13.215 - EdgeFilterMap* edge_filter_map;
13.216 - SubGraphWrapperBase() : Parent(),
13.217 - node_filter_map(0), edge_filter_map(0) { }
13.218 -
13.219 - void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
13.220 - node_filter_map=&_node_filter_map;
13.221 - }
13.222 - void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
13.223 - edge_filter_map=&_edge_filter_map;
13.224 - }
13.225 -
13.226 - public:
13.227 -// SubGraphWrapperBase(Graph& _graph,
13.228 -// NodeFilterMap& _node_filter_map,
13.229 -// EdgeFilterMap& _edge_filter_map) :
13.230 -// Parent(&_graph),
13.231 -// node_filter_map(&node_filter_map),
13.232 -// edge_filter_map(&edge_filter_map) { }
13.233 -
13.234 - typedef typename Parent::Node Node;
13.235 - typedef typename Parent::Edge Edge;
13.236 -
13.237 - void first(Node& i) const {
13.238 - Parent::first(i);
13.239 - while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
13.240 - }
13.241 - void first(Edge& i) const {
13.242 - Parent::first(i);
13.243 - while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
13.244 - }
13.245 - void firstIn(Edge& i, const Node& n) const {
13.246 - Parent::firstIn(i, n);
13.247 - while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
13.248 - }
13.249 - void firstOut(Edge& i, const Node& n) const {
13.250 - Parent::firstOut(i, n);
13.251 - while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
13.252 - }
13.253 -
13.254 - void next(Node& i) const {
13.255 - Parent::next(i);
13.256 - while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
13.257 - }
13.258 - void next(Edge& i) const {
13.259 - Parent::next(i);
13.260 - while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
13.261 - }
13.262 - void nextIn(Edge& i) const {
13.263 - Parent::nextIn(i);
13.264 - while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
13.265 - }
13.266 - void nextOut(Edge& i) const {
13.267 - Parent::nextOut(i);
13.268 - while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
13.269 - }
13.270 -
13.271 - /// This function hides \c n in the graph, i.e. the iteration
13.272 - /// jumps over it. This is done by simply setting the value of \c n
13.273 - /// to be false in the corresponding node-map.
13.274 - void hide(const Node& n) const { node_filter_map->set(n, false); }
13.275 -
13.276 - /// This function hides \c e in the graph, i.e. the iteration
13.277 - /// jumps over it. This is done by simply setting the value of \c e
13.278 - /// to be false in the corresponding edge-map.
13.279 - void hide(const Edge& e) const { edge_filter_map->set(e, false); }
13.280 -
13.281 - /// The value of \c n is set to be true in the node-map which stores
13.282 - /// hide information. If \c n was hidden previuosly, then it is shown
13.283 - /// again
13.284 - void unHide(const Node& n) const { node_filter_map->set(n, true); }
13.285 -
13.286 - /// The value of \c e is set to be true in the edge-map which stores
13.287 - /// hide information. If \c e was hidden previuosly, then it is shown
13.288 - /// again
13.289 - void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
13.290 -
13.291 - /// Returns true if \c n is hidden.
13.292 - bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
13.293 -
13.294 - /// Returns true if \c n is hidden.
13.295 - bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
13.296 -
13.297 - /// \warning This is a linear time operation and works only if s
13.298 - /// \c Graph::NodeIt is defined.
13.299 - /// \todo assign tags.
13.300 - int nodeNum() const {
13.301 - int i=0;
13.302 - Node n;
13.303 - for (first(n); n!=INVALID; next(n)) ++i;
13.304 - return i;
13.305 - }
13.306 -
13.307 - /// \warning This is a linear time operation and works only if
13.308 - /// \c Graph::EdgeIt is defined.
13.309 - /// \todo assign tags.
13.310 - int edgeNum() const {
13.311 - int i=0;
13.312 - Edge e;
13.313 - for (first(e); e!=INVALID; next(e)) ++i;
13.314 - return i;
13.315 - }
13.316 -
13.317 -
13.318 - };
13.319 -
13.320 - /*! \brief A graph wrapper for hiding nodes and edges from a graph.
13.321 -
13.322 - \warning Graph wrappers are in even more experimental state than the other
13.323 - parts of the lib. Use them at you own risk.
13.324 -
13.325 - SubGraphWrapper shows the graph with filtered node-set and
13.326 - edge-set.
13.327 - Let \f$G=(V, A)\f$ be a directed graph
13.328 - and suppose that the graph instance \c g of type ListGraph implements
13.329 - \f$G\f$.
13.330 - Let moreover \f$b_V\f$ and
13.331 - \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
13.332 - SubGraphWrapper<...>::NodeIt iterates
13.333 - on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
13.334 - SubGraphWrapper<...>::EdgeIt iterates
13.335 - on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
13.336 - SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::InEdgeIt iterates
13.337 - only on edges leaving and entering a specific node which have true value.
13.338 -
13.339 - We have to note that this does not mean that an
13.340 - induced subgraph is obtained, the node-iterator cares only the filter
13.341 - on the node-set, and the edge-iterators care only the filter on the
13.342 - edge-set.
13.343 - \code
13.344 - typedef ListGraph Graph;
13.345 - Graph g;
13.346 - typedef Graph::Node Node;
13.347 - typedef Graph::Edge Edge;
13.348 - Node u=g.addNode(); //node of id 0
13.349 - Node v=g.addNode(); //node of id 1
13.350 - Node e=g.addEdge(u, v); //edge of id 0
13.351 - Node f=g.addEdge(v, u); //edge of id 1
13.352 - Graph::NodeMap<bool> nm(g, true);
13.353 - nm.set(u, false);
13.354 - Graph::EdgeMap<bool> em(g, true);
13.355 - em.set(e, false);
13.356 - typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
13.357 - SubGW gw(g, nm, em);
13.358 - for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
13.359 - std::cout << ":-)" << std::endl;
13.360 - for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
13.361 - \endcode
13.362 - The output of the above code is the following.
13.363 - \code
13.364 - 1
13.365 - :-)
13.366 - 1
13.367 - \endcode
13.368 - Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
13.369 - \c Graph::Node that is why \c g.id(n) can be applied.
13.370 -
13.371 - For other examples see also the documentation of NodeSubGraphWrapper and
13.372 - EdgeSubGraphWrapper.
13.373 -
13.374 - \author Marton Makai
13.375 - */
13.376 - template<typename _Graph, typename NodeFilterMap,
13.377 - typename EdgeFilterMap>
13.378 - class SubGraphWrapper :
13.379 - public IterableGraphExtender<
13.380 - SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
13.381 - public:
13.382 - typedef _Graph Graph;
13.383 - typedef IterableGraphExtender<
13.384 - SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
13.385 - protected:
13.386 - SubGraphWrapper() { }
13.387 - public:
13.388 - SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
13.389 - EdgeFilterMap& _edge_filter_map) {
13.390 - setGraph(_graph);
13.391 - setNodeFilterMap(_node_filter_map);
13.392 - setEdgeFilterMap(_edge_filter_map);
13.393 - }
13.394 - };
13.395 -
13.396 -
13.397 -
13.398 - /*! \brief A wrapper for hiding nodes from a graph.
13.399 -
13.400 - \warning Graph wrappers are in even more experimental state than the other
13.401 - parts of the lib. Use them at you own risk.
13.402 -
13.403 - A wrapper for hiding nodes from a graph.
13.404 - This wrapper specializes SubGraphWrapper in the way that only the node-set
13.405 - can be filtered. Note that this does not mean of considering induced
13.406 - subgraph, the edge-iterators consider the original edge-set.
13.407 - \author Marton Makai
13.408 - */
13.409 - template<typename Graph, typename NodeFilterMap>
13.410 - class NodeSubGraphWrapper :
13.411 - public SubGraphWrapper<Graph, NodeFilterMap,
13.412 - ConstMap<typename Graph::Edge,bool> > {
13.413 - public:
13.414 - typedef SubGraphWrapper<Graph, NodeFilterMap,
13.415 - ConstMap<typename Graph::Edge,bool> > Parent;
13.416 - protected:
13.417 - ConstMap<typename Graph::Edge, bool> const_true_map;
13.418 - public:
13.419 - NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
13.420 - Parent(), const_true_map(true) {
13.421 - Parent::setGraph(_graph);
13.422 - Parent::setNodeFilterMap(_node_filter_map);
13.423 - Parent::setEdgeFilterMap(const_true_map);
13.424 - }
13.425 - };
13.426 -
13.427 -
13.428 - /*! \brief A wrapper for hiding edges from a graph.
13.429 -
13.430 - \warning Graph wrappers are in even more experimental state than the other
13.431 - parts of the lib. Use them at you own risk.
13.432 -
13.433 - A wrapper for hiding edges from a graph.
13.434 - This wrapper specializes SubGraphWrapper in the way that only the edge-set
13.435 - can be filtered. The usefulness of this wrapper is demonstrated in the
13.436 - problem of searching a maximum number of edge-disjoint shortest paths
13.437 - between
13.438 - two nodes \c s and \c t. Shortest here means being shortest w.r.t.
13.439 - non-negative edge-lengths. Note that
13.440 - the comprehension of the presented solution
13.441 - need's some elementary knowledge from combinatorial optimization.
13.442 -
13.443 - If a single shortest path is to be
13.444 - searched between \c s and \c t, then this can be done easily by
13.445 - applying the Dijkstra algorithm. What happens, if a maximum number of
13.446 - edge-disjoint shortest paths is to be computed. It can be proved that an
13.447 - edge can be in a shortest path if and only if it is tight with respect to
13.448 - the potential function computed by Dijkstra. Moreover, any path containing
13.449 - only such edges is a shortest one. Thus we have to compute a maximum number
13.450 - of edge-disjoint paths between \c s and \c t in the graph which has edge-set
13.451 - all the tight edges. The computation will be demonstrated on the following
13.452 - graph, which is read from a dimacs file.
13.453 -
13.454 - \dot
13.455 - digraph lemon_dot_example {
13.456 - node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
13.457 - n0 [ label="0 (s)" ];
13.458 - n1 [ label="1" ];
13.459 - n2 [ label="2" ];
13.460 - n3 [ label="3" ];
13.461 - n4 [ label="4" ];
13.462 - n5 [ label="5" ];
13.463 - n6 [ label="6 (t)" ];
13.464 - edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
13.465 - n5 -> n6 [ label="9, length:4" ];
13.466 - n4 -> n6 [ label="8, length:2" ];
13.467 - n3 -> n5 [ label="7, length:1" ];
13.468 - n2 -> n5 [ label="6, length:3" ];
13.469 - n2 -> n6 [ label="5, length:5" ];
13.470 - n2 -> n4 [ label="4, length:2" ];
13.471 - n1 -> n4 [ label="3, length:3" ];
13.472 - n0 -> n3 [ label="2, length:1" ];
13.473 - n0 -> n2 [ label="1, length:2" ];
13.474 - n0 -> n1 [ label="0, length:3" ];
13.475 - }
13.476 - \enddot
13.477 -
13.478 - \code
13.479 - Graph g;
13.480 - Node s, t;
13.481 - LengthMap length(g);
13.482 -
13.483 - readDimacs(std::cin, g, length, s, t);
13.484 -
13.485 - cout << "edges with lengths (of form id, source--length->target): " << endl;
13.486 - for(EdgeIt e(g); e!=INVALID; ++e)
13.487 - cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
13.488 - << length[e] << "->" << g.id(g.target(e)) << endl;
13.489 -
13.490 - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
13.491 - \endcode
13.492 - Next, the potential function is computed with Dijkstra.
13.493 - \code
13.494 - typedef Dijkstra<Graph, LengthMap> Dijkstra;
13.495 - Dijkstra dijkstra(g, length);
13.496 - dijkstra.run(s);
13.497 - \endcode
13.498 - Next, we consrtruct a map which filters the edge-set to the tight edges.
13.499 - \code
13.500 - typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
13.501 - TightEdgeFilter;
13.502 - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
13.503 -
13.504 - typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
13.505 - SubGW gw(g, tight_edge_filter);
13.506 - \endcode
13.507 - Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
13.508 - with a max flow algorithm Preflow.
13.509 - \code
13.510 - ConstMap<Edge, int> const_1_map(1);
13.511 - Graph::EdgeMap<int> flow(g, 0);
13.512 -
13.513 - Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
13.514 - preflow(gw, s, t, const_1_map, flow);
13.515 - preflow.run();
13.516 - \endcode
13.517 - Last, the output is:
13.518 - \code
13.519 - cout << "maximum number of edge-disjoint shortest path: "
13.520 - << preflow.flowValue() << endl;
13.521 - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
13.522 - << endl;
13.523 - for(EdgeIt e(g); e!=INVALID; ++e)
13.524 - if (flow[e])
13.525 - cout << " " << g.id(g.source(e)) << "--"
13.526 - << length[e] << "->" << g.id(g.target(e)) << endl;
13.527 - \endcode
13.528 - The program has the following (expected :-)) output:
13.529 - \code
13.530 - edges with lengths (of form id, source--length->target):
13.531 - 9, 5--4->6
13.532 - 8, 4--2->6
13.533 - 7, 3--1->5
13.534 - 6, 2--3->5
13.535 - 5, 2--5->6
13.536 - 4, 2--2->4
13.537 - 3, 1--3->4
13.538 - 2, 0--1->3
13.539 - 1, 0--2->2
13.540 - 0, 0--3->1
13.541 - s: 0 t: 6
13.542 - maximum number of edge-disjoint shortest path: 2
13.543 - edges of the maximum number of edge-disjoint shortest s-t paths:
13.544 - 9, 5--4->6
13.545 - 8, 4--2->6
13.546 - 7, 3--1->5
13.547 - 4, 2--2->4
13.548 - 2, 0--1->3
13.549 - 1, 0--2->2
13.550 - \endcode
13.551 -
13.552 - \author Marton Makai
13.553 - */
13.554 - template<typename Graph, typename EdgeFilterMap>
13.555 - class EdgeSubGraphWrapper :
13.556 - public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
13.557 - EdgeFilterMap> {
13.558 - public:
13.559 - typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
13.560 - EdgeFilterMap> Parent;
13.561 - protected:
13.562 - ConstMap<typename Graph::Node, bool> const_true_map;
13.563 - public:
13.564 - EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
13.565 - Parent(), const_true_map(true) {
13.566 - Parent::setGraph(_graph);
13.567 - Parent::setNodeFilterMap(const_true_map);
13.568 - Parent::setEdgeFilterMap(_edge_filter_map);
13.569 - }
13.570 - };
13.571 -
13.572 - template <typename _Graph>
13.573 - class UndirGraphWrapperBase :
13.574 - public UndirGraphExtender<GraphWrapperBase<_Graph> > {
13.575 - public:
13.576 - typedef _Graph Graph;
13.577 - typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
13.578 - protected:
13.579 - UndirGraphWrapperBase() : Parent() { }
13.580 - public:
13.581 - typedef typename Parent::UndirEdge UndirEdge;
13.582 - typedef typename Parent::Edge Edge;
13.583 -
13.584 - /// \bug Why cant an edge say that it is forward or not???
13.585 - /// By this, a pointer to the graph have to be stored
13.586 - /// The implementation
13.587 - template <typename T>
13.588 - class EdgeMap {
13.589 - protected:
13.590 - const UndirGraphWrapperBase<_Graph>* g;
13.591 - template <typename TT> friend class EdgeMap;
13.592 - typename _Graph::template EdgeMap<T> forward_map, backward_map;
13.593 - public:
13.594 - typedef T Value;
13.595 - typedef Edge Key;
13.596 -
13.597 - EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g),
13.598 - forward_map(*(g->graph)), backward_map(*(g->graph)) { }
13.599 -
13.600 - EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g),
13.601 - forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
13.602 -
13.603 - void set(Edge e, T a) {
13.604 - if (g->forward(e))
13.605 - forward_map.set(e, a);
13.606 - else
13.607 - backward_map.set(e, a);
13.608 - }
13.609 -
13.610 - T operator[](Edge e) const {
13.611 - if (g->forward(e))
13.612 - return forward_map[e];
13.613 - else
13.614 - return backward_map[e];
13.615 - }
13.616 - };
13.617 -
13.618 - template <typename T>
13.619 - class UndirEdgeMap {
13.620 - template <typename TT> friend class UndirEdgeMap;
13.621 - typename _Graph::template EdgeMap<T> map;
13.622 - public:
13.623 - typedef T Value;
13.624 - typedef UndirEdge Key;
13.625 -
13.626 - UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) :
13.627 - map(*(g.graph)) { }
13.628 -
13.629 - UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) :
13.630 - map(*(g.graph), a) { }
13.631 -
13.632 - void set(UndirEdge e, T a) {
13.633 - map.set(e, a);
13.634 - }
13.635 -
13.636 - T operator[](UndirEdge e) const {
13.637 - return map[e];
13.638 - }
13.639 - };
13.640 -
13.641 - };
13.642 -
13.643 - /// \brief An undirected graph is made from a directed graph by a wrapper
13.644 - ///
13.645 - /// Undocumented, untested!!!
13.646 - /// If somebody knows nice demo application, let's polulate it.
13.647 - ///
13.648 - /// \author Marton Makai
13.649 - template<typename _Graph>
13.650 - class UndirGraphWrapper :
13.651 - public IterableUndirGraphExtender<
13.652 - UndirGraphWrapperBase<_Graph> > {
13.653 - public:
13.654 - typedef _Graph Graph;
13.655 - typedef IterableUndirGraphExtender<
13.656 - UndirGraphWrapperBase<_Graph> > Parent;
13.657 - protected:
13.658 - UndirGraphWrapper() { }
13.659 - public:
13.660 - UndirGraphWrapper(_Graph& _graph) {
13.661 - setGraph(_graph);
13.662 - }
13.663 - };
13.664 -
13.665 -
13.666 - template <typename _Graph,
13.667 - typename ForwardFilterMap, typename BackwardFilterMap>
13.668 - class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
13.669 - public:
13.670 - typedef _Graph Graph;
13.671 - typedef GraphWrapperBase<_Graph> Parent;
13.672 - protected:
13.673 - ForwardFilterMap* forward_filter;
13.674 - BackwardFilterMap* backward_filter;
13.675 - SubBidirGraphWrapperBase() : Parent(),
13.676 - forward_filter(0), backward_filter(0) { }
13.677 -
13.678 - void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
13.679 - forward_filter=&_forward_filter;
13.680 - }
13.681 - void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
13.682 - backward_filter=&_backward_filter;
13.683 - }
13.684 -
13.685 - public:
13.686 -// SubGraphWrapperBase(Graph& _graph,
13.687 -// NodeFilterMap& _node_filter_map,
13.688 -// EdgeFilterMap& _edge_filter_map) :
13.689 -// Parent(&_graph),
13.690 -// node_filter_map(&node_filter_map),
13.691 -// edge_filter_map(&edge_filter_map) { }
13.692 -
13.693 - typedef typename Parent::Node Node;
13.694 - typedef typename _Graph::Edge GraphEdge;
13.695 - template <typename T> class EdgeMap;
13.696 - /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
13.697 - /// _Graph::Edge. It contains an extra bool flag which is true
13.698 - /// if and only if the
13.699 - /// edge is the backward version of the original edge.
13.700 - class Edge : public _Graph::Edge {
13.701 - friend class SubBidirGraphWrapperBase<
13.702 - Graph, ForwardFilterMap, BackwardFilterMap>;
13.703 - template<typename T> friend class EdgeMap;
13.704 - protected:
13.705 - bool backward; //true, iff backward
13.706 - public:
13.707 - Edge() { }
13.708 - /// \todo =false is needed, or causes problems?
13.709 - /// If \c _backward is false, then we get an edge corresponding to the
13.710 - /// original one, otherwise its oppositely directed pair is obtained.
13.711 - Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
13.712 - _Graph::Edge(e), backward(_backward) { }
13.713 - Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
13.714 - bool operator==(const Edge& v) const {
13.715 - return (this->backward==v.backward &&
13.716 - static_cast<typename _Graph::Edge>(*this)==
13.717 - static_cast<typename _Graph::Edge>(v));
13.718 - }
13.719 - bool operator!=(const Edge& v) const {
13.720 - return (this->backward!=v.backward ||
13.721 - static_cast<typename _Graph::Edge>(*this)!=
13.722 - static_cast<typename _Graph::Edge>(v));
13.723 - }
13.724 - };
13.725 -
13.726 - void first(Node& i) const {
13.727 - Parent::first(i);
13.728 - }
13.729 -
13.730 - void first(Edge& i) const {
13.731 - Parent::first(i);
13.732 - i.backward=false;
13.733 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.734 - !(*forward_filter)[i]) Parent::next(i);
13.735 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
13.736 - Parent::first(i);
13.737 - i.backward=true;
13.738 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.739 - !(*backward_filter)[i]) Parent::next(i);
13.740 - }
13.741 - }
13.742 -
13.743 - void firstIn(Edge& i, const Node& n) const {
13.744 - Parent::firstIn(i, n);
13.745 - i.backward=false;
13.746 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.747 - !(*forward_filter)[i]) Parent::nextIn(i);
13.748 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
13.749 - Parent::firstOut(i, n);
13.750 - i.backward=true;
13.751 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.752 - !(*backward_filter)[i]) Parent::nextOut(i);
13.753 - }
13.754 - }
13.755 -
13.756 - void firstOut(Edge& i, const Node& n) const {
13.757 - Parent::firstOut(i, n);
13.758 - i.backward=false;
13.759 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.760 - !(*forward_filter)[i]) Parent::nextOut(i);
13.761 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
13.762 - Parent::firstIn(i, n);
13.763 - i.backward=true;
13.764 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.765 - !(*backward_filter)[i]) Parent::nextIn(i);
13.766 - }
13.767 - }
13.768 -
13.769 - void next(Node& i) const {
13.770 - Parent::next(i);
13.771 - }
13.772 -
13.773 - void next(Edge& i) const {
13.774 - if (!(i.backward)) {
13.775 - Parent::next(i);
13.776 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.777 - !(*forward_filter)[i]) Parent::next(i);
13.778 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
13.779 - Parent::first(i);
13.780 - i.backward=true;
13.781 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.782 - !(*backward_filter)[i]) Parent::next(i);
13.783 - }
13.784 - } else {
13.785 - Parent::next(i);
13.786 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.787 - !(*backward_filter)[i]) Parent::next(i);
13.788 - }
13.789 - }
13.790 -
13.791 - void nextIn(Edge& i) const {
13.792 - if (!(i.backward)) {
13.793 - Node n=Parent::target(i);
13.794 - Parent::nextIn(i);
13.795 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.796 - !(*forward_filter)[i]) Parent::nextIn(i);
13.797 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
13.798 - Parent::firstOut(i, n);
13.799 - i.backward=true;
13.800 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.801 - !(*backward_filter)[i]) Parent::nextOut(i);
13.802 - }
13.803 - } else {
13.804 - Parent::nextOut(i);
13.805 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.806 - !(*backward_filter)[i]) Parent::nextOut(i);
13.807 - }
13.808 - }
13.809 -
13.810 - void nextOut(Edge& i) const {
13.811 - if (!(i.backward)) {
13.812 - Node n=Parent::source(i);
13.813 - Parent::nextOut(i);
13.814 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.815 - !(*forward_filter)[i]) Parent::nextOut(i);
13.816 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
13.817 - Parent::firstIn(i, n);
13.818 - i.backward=true;
13.819 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.820 - !(*backward_filter)[i]) Parent::nextIn(i);
13.821 - }
13.822 - } else {
13.823 - Parent::nextIn(i);
13.824 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
13.825 - !(*backward_filter)[i]) Parent::nextIn(i);
13.826 - }
13.827 - }
13.828 -
13.829 - Node source(Edge e) const {
13.830 - return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
13.831 - Node target(Edge e) const {
13.832 - return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
13.833 -
13.834 - /// Gives back the opposite edge.
13.835 - Edge opposite(const Edge& e) const {
13.836 - Edge f=e;
13.837 - f.backward=!f.backward;
13.838 - return f;
13.839 - }
13.840 -
13.841 - /// \warning This is a linear time operation and works only if
13.842 - /// \c Graph::EdgeIt is defined.
13.843 - /// \todo hmm
13.844 - int edgeNum() const {
13.845 - int i=0;
13.846 - Edge e;
13.847 - for (first(e); e!=INVALID; next(e)) ++i;
13.848 - return i;
13.849 - }
13.850 -
13.851 - bool forward(const Edge& e) const { return !e.backward; }
13.852 - bool backward(const Edge& e) const { return e.backward; }
13.853 -
13.854 - template <typename T>
13.855 - /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
13.856 - /// _Graph::EdgeMap one for the forward edges and
13.857 - /// one for the backward edges.
13.858 - class EdgeMap {
13.859 - template <typename TT> friend class EdgeMap;
13.860 - typename _Graph::template EdgeMap<T> forward_map, backward_map;
13.861 - public:
13.862 - typedef T Value;
13.863 - typedef Edge Key;
13.864 -
13.865 - EdgeMap(const SubBidirGraphWrapperBase<_Graph,
13.866 - ForwardFilterMap, BackwardFilterMap>& g) :
13.867 - forward_map(*(g.graph)), backward_map(*(g.graph)) { }
13.868 -
13.869 - EdgeMap(const SubBidirGraphWrapperBase<_Graph,
13.870 - ForwardFilterMap, BackwardFilterMap>& g, T a) :
13.871 - forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
13.872 -
13.873 - void set(Edge e, T a) {
13.874 - if (!e.backward)
13.875 - forward_map.set(e, a);
13.876 - else
13.877 - backward_map.set(e, a);
13.878 - }
13.879 -
13.880 -// typename _Graph::template EdgeMap<T>::ConstReference
13.881 -// operator[](Edge e) const {
13.882 -// if (!e.backward)
13.883 -// return forward_map[e];
13.884 -// else
13.885 -// return backward_map[e];
13.886 -// }
13.887 -
13.888 -// typename _Graph::template EdgeMap<T>::Reference
13.889 - T operator[](Edge e) const {
13.890 - if (!e.backward)
13.891 - return forward_map[e];
13.892 - else
13.893 - return backward_map[e];
13.894 - }
13.895 -
13.896 - void update() {
13.897 - forward_map.update();
13.898 - backward_map.update();
13.899 - }
13.900 - };
13.901 -
13.902 - };
13.903 -
13.904 -
13.905 - ///\brief A wrapper for composing a subgraph of a
13.906 - /// bidirected graph made from a directed one.
13.907 - ///
13.908 - /// A wrapper for composing a subgraph of a
13.909 - /// bidirected graph made from a directed one.
13.910 - ///
13.911 - ///\warning Graph wrappers are in even more experimental state than the other
13.912 - ///parts of the lib. Use them at you own risk.
13.913 - ///
13.914 - /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
13.915 - /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
13.916 - /// reversing its orientation. We are given moreover two bool valued
13.917 - /// maps on the edge-set,
13.918 - /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
13.919 - /// SubBidirGraphWrapper implements the graph structure with node-set
13.920 - /// \f$V\f$ and edge-set
13.921 - /// \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$.
13.922 - /// The purpose of writing + instead of union is because parallel
13.923 - /// edges can arise. (Similarly, antiparallel edges also can arise).
13.924 - /// In other words, a subgraph of the bidirected graph obtained, which
13.925 - /// is given by orienting the edges of the original graph in both directions.
13.926 - /// As the oppositely directed edges are logically different,
13.927 - /// the maps are able to attach different values for them.
13.928 - ///
13.929 - /// An example for such a construction is \c RevGraphWrapper where the
13.930 - /// forward_filter is everywhere false and the backward_filter is
13.931 - /// everywhere true. We note that for sake of efficiency,
13.932 - /// \c RevGraphWrapper is implemented in a different way.
13.933 - /// But BidirGraphWrapper is obtained from
13.934 - /// SubBidirGraphWrapper by considering everywhere true
13.935 - /// valued maps both for forward_filter and backward_filter.
13.936 - ///
13.937 - /// The most important application of SubBidirGraphWrapper
13.938 - /// is ResGraphWrapper, which stands for the residual graph in directed
13.939 - /// flow and circulation problems.
13.940 - /// As wrappers usually, the SubBidirGraphWrapper implements the
13.941 - /// above mentioned graph structure without its physical storage,
13.942 - /// that is the whole stuff is stored in constant memory.
13.943 - template<typename _Graph,
13.944 - typename ForwardFilterMap, typename BackwardFilterMap>
13.945 - class SubBidirGraphWrapper :
13.946 - public IterableGraphExtender<
13.947 - SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
13.948 - public:
13.949 - typedef _Graph Graph;
13.950 - typedef IterableGraphExtender<
13.951 - SubBidirGraphWrapperBase<
13.952 - _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
13.953 - protected:
13.954 - SubBidirGraphWrapper() { }
13.955 - public:
13.956 - SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
13.957 - BackwardFilterMap& _backward_filter) {
13.958 - setGraph(_graph);
13.959 - setForwardFilterMap(_forward_filter);
13.960 - setBackwardFilterMap(_backward_filter);
13.961 - }
13.962 - };
13.963 -
13.964 -
13.965 -
13.966 - ///\brief A wrapper for composing bidirected graph from a directed one.
13.967 - ///
13.968 - ///\warning Graph wrappers are in even more experimental state than the other
13.969 - ///parts of the lib. Use them at you own risk.
13.970 - ///
13.971 - /// A wrapper for composing bidirected graph from a directed one.
13.972 - /// A bidirected graph is composed over the directed one without physical
13.973 - /// storage. As the oppositely directed edges are logically different ones
13.974 - /// the maps are able to attach different values for them.
13.975 - template<typename Graph>
13.976 - class BidirGraphWrapper :
13.977 - public SubBidirGraphWrapper<
13.978 - Graph,
13.979 - ConstMap<typename Graph::Edge, bool>,
13.980 - ConstMap<typename Graph::Edge, bool> > {
13.981 - public:
13.982 - typedef SubBidirGraphWrapper<
13.983 - Graph,
13.984 - ConstMap<typename Graph::Edge, bool>,
13.985 - ConstMap<typename Graph::Edge, bool> > Parent;
13.986 - protected:
13.987 - ConstMap<typename Graph::Edge, bool> cm;
13.988 -
13.989 - BidirGraphWrapper() : Parent(), cm(true) {
13.990 - Parent::setForwardFilterMap(cm);
13.991 - Parent::setBackwardFilterMap(cm);
13.992 - }
13.993 - public:
13.994 - BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
13.995 - Parent::setGraph(_graph);
13.996 - Parent::setForwardFilterMap(cm);
13.997 - Parent::setBackwardFilterMap(cm);
13.998 - }
13.999 -
13.1000 - int edgeNum() const {
13.1001 - return 2*this->graph->edgeNum();
13.1002 - }
13.1003 - // KEEP_MAPS(Parent, BidirGraphWrapper);
13.1004 - };
13.1005 -
13.1006 -
13.1007 - template<typename Graph, typename Number,
13.1008 - typename CapacityMap, typename FlowMap>
13.1009 - class ResForwardFilter {
13.1010 - // const Graph* graph;
13.1011 - const CapacityMap* capacity;
13.1012 - const FlowMap* flow;
13.1013 - public:
13.1014 - ResForwardFilter(/*const Graph& _graph, */
13.1015 - const CapacityMap& _capacity, const FlowMap& _flow) :
13.1016 - /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
13.1017 - ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
13.1018 - void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
13.1019 - void setFlow(const FlowMap& _flow) { flow=&_flow; }
13.1020 - bool operator[](const typename Graph::Edge& e) const {
13.1021 - return (Number((*flow)[e]) < Number((*capacity)[e]));
13.1022 - }
13.1023 - };
13.1024 -
13.1025 - template<typename Graph, typename Number,
13.1026 - typename CapacityMap, typename FlowMap>
13.1027 - class ResBackwardFilter {
13.1028 - const CapacityMap* capacity;
13.1029 - const FlowMap* flow;
13.1030 - public:
13.1031 - ResBackwardFilter(/*const Graph& _graph,*/
13.1032 - const CapacityMap& _capacity, const FlowMap& _flow) :
13.1033 - /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
13.1034 - ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
13.1035 - void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
13.1036 - void setFlow(const FlowMap& _flow) { flow=&_flow; }
13.1037 - bool operator[](const typename Graph::Edge& e) const {
13.1038 - return (Number(0) < Number((*flow)[e]));
13.1039 - }
13.1040 - };
13.1041 -
13.1042 -
13.1043 - /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.
13.1044 -
13.1045 - A wrapper for composing the residual graph for directed flow and circulation problems.
13.1046 - Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
13.1047 - number type. Let moreover
13.1048 - \f$f,c:A\to F\f$, be functions on the edge-set.
13.1049 - In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow
13.1050 - and \f$c\f$ for a capacity function.
13.1051 - Suppose that a graph instange \c g of type
13.1052 - \c ListGraph implements \f$G\f$.
13.1053 - \code
13.1054 - ListGraph g;
13.1055 - \endcode
13.1056 - Then RevGraphWrapper implements the graph structure with node-set
13.1057 - \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
13.1058 - \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
13.1059 - \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
13.1060 - i.e. the so called residual graph.
13.1061 - When we take the union \f$A_{forward}\cup A_{backward}\f$,
13.1062 - multilicities are counted, i.e. if an edge is in both
13.1063 - \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it
13.1064 - appears twice.
13.1065 - The following code shows how
13.1066 - such an instance can be constructed.
13.1067 - \code
13.1068 - typedef ListGraph Graph;
13.1069 - Graph::EdgeMap<int> f(g);
13.1070 - Graph::EdgeMap<int> c(g);
13.1071 - ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
13.1072 - \endcode
13.1073 - \author Marton Makai
13.1074 - */
13.1075 - template<typename Graph, typename Number,
13.1076 - typename CapacityMap, typename FlowMap>
13.1077 - class ResGraphWrapper :
13.1078 - public SubBidirGraphWrapper<
13.1079 - Graph,
13.1080 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
13.1081 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
13.1082 - public:
13.1083 - typedef SubBidirGraphWrapper<
13.1084 - Graph,
13.1085 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
13.1086 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
13.1087 - protected:
13.1088 - const CapacityMap* capacity;
13.1089 - FlowMap* flow;
13.1090 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
13.1091 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
13.1092 - ResGraphWrapper() : Parent(),
13.1093 - capacity(0), flow(0) { }
13.1094 - void setCapacityMap(const CapacityMap& _capacity) {
13.1095 - capacity=&_capacity;
13.1096 - forward_filter.setCapacity(_capacity);
13.1097 - backward_filter.setCapacity(_capacity);
13.1098 - }
13.1099 - void setFlowMap(FlowMap& _flow) {
13.1100 - flow=&_flow;
13.1101 - forward_filter.setFlow(_flow);
13.1102 - backward_filter.setFlow(_flow);
13.1103 - }
13.1104 - public:
13.1105 - ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
13.1106 - FlowMap& _flow) :
13.1107 - Parent(), capacity(&_capacity), flow(&_flow),
13.1108 - forward_filter(/*_graph,*/ _capacity, _flow),
13.1109 - backward_filter(/*_graph,*/ _capacity, _flow) {
13.1110 - Parent::setGraph(_graph);
13.1111 - Parent::setForwardFilterMap(forward_filter);
13.1112 - Parent::setBackwardFilterMap(backward_filter);
13.1113 - }
13.1114 -
13.1115 - typedef typename Parent::Edge Edge;
13.1116 -
13.1117 - void augment(const Edge& e, Number a) const {
13.1118 - if (Parent::forward(e))
13.1119 - flow->set(e, (*flow)[e]+a);
13.1120 - else
13.1121 - flow->set(e, (*flow)[e]-a);
13.1122 - }
13.1123 -
13.1124 - /// \brief Residual capacity map.
13.1125 - ///
13.1126 - /// In generic residual graphs the residual capacity can be obtained
13.1127 - /// as a map.
13.1128 - class ResCap {
13.1129 - protected:
13.1130 - const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
13.1131 - public:
13.1132 - typedef Number Value;
13.1133 - typedef Edge Key;
13.1134 - ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
13.1135 - _res_graph) : res_graph(&_res_graph) { }
13.1136 - Number operator[](const Edge& e) const {
13.1137 - if (res_graph->forward(e))
13.1138 - return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
13.1139 - else
13.1140 - return (*(res_graph->flow))[e];
13.1141 - }
13.1142 - };
13.1143 -
13.1144 - // KEEP_MAPS(Parent, ResGraphWrapper);
13.1145 - };
13.1146 -
13.1147 -
13.1148 -
13.1149 - template <typename _Graph, typename FirstOutEdgesMap>
13.1150 - class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
13.1151 - public:
13.1152 - typedef _Graph Graph;
13.1153 - typedef GraphWrapperBase<_Graph> Parent;
13.1154 - protected:
13.1155 - FirstOutEdgesMap* first_out_edges;
13.1156 - ErasingFirstGraphWrapperBase() : Parent(),
13.1157 - first_out_edges(0) { }
13.1158 -
13.1159 - void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
13.1160 - first_out_edges=&_first_out_edges;
13.1161 - }
13.1162 -
13.1163 - public:
13.1164 -
13.1165 - typedef typename Parent::Node Node;
13.1166 - typedef typename Parent::Edge Edge;
13.1167 -
13.1168 - void firstOut(Edge& i, const Node& n) const {
13.1169 - i=(*first_out_edges)[n];
13.1170 - }
13.1171 -
13.1172 - void erase(const Edge& e) const {
13.1173 - Node n=source(e);
13.1174 - Edge f=e;
13.1175 - Parent::nextOut(f);
13.1176 - first_out_edges->set(n, f);
13.1177 - }
13.1178 - };
13.1179 -
13.1180 -
13.1181 - /// For blocking flows.
13.1182 -
13.1183 - ///\warning Graph wrappers are in even more experimental state than the other
13.1184 - ///parts of the lib. Use them at you own risk.
13.1185 - ///
13.1186 - /// This graph wrapper is used for on-the-fly
13.1187 - /// Dinits blocking flow computations.
13.1188 - /// For each node, an out-edge is stored which is used when the
13.1189 - /// \code
13.1190 - /// OutEdgeIt& first(OutEdgeIt&, const Node&)
13.1191 - /// \endcode
13.1192 - /// is called.
13.1193 - ///
13.1194 - /// \author Marton Makai
13.1195 - template <typename _Graph, typename FirstOutEdgesMap>
13.1196 - class ErasingFirstGraphWrapper :
13.1197 - public IterableGraphExtender<
13.1198 - ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
13.1199 - public:
13.1200 - typedef _Graph Graph;
13.1201 - typedef IterableGraphExtender<
13.1202 - ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
13.1203 - ErasingFirstGraphWrapper(Graph& _graph,
13.1204 - FirstOutEdgesMap& _first_out_edges) {
13.1205 - setGraph(_graph);
13.1206 - setFirstOutEdgesMap(_first_out_edges);
13.1207 - }
13.1208 -
13.1209 - };
13.1210 -
13.1211 - ///@}
13.1212 -
13.1213 -} //namespace lemon
13.1214 -
13.1215 -#endif //LEMON_GRAPH_WRAPPER_H
13.1216 -
14.1 --- a/src/lemon/min_cost_flow.h Mon May 02 05:49:33 2005 +0000
14.2 +++ b/src/lemon/min_cost_flow.h Wed May 04 13:07:10 2005 +0000
14.3 @@ -23,7 +23,7 @@
14.4
14.5
14.6 #include <lemon/dijkstra.h>
14.7 -#include <lemon/graph_wrapper.h>
14.8 +#include <lemon/graph_adaptor.h>
14.9 #include <lemon/maps.h>
14.10 #include <vector>
14.11
14.12 @@ -68,7 +68,7 @@
14.13 typedef typename Graph::OutEdgeIt OutEdgeIt;
14.14 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
14.15
14.16 - typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
14.17 + typedef ResGraphAdaptor<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
14.18 typedef typename ResGW::Edge ResGraphEdge;
14.19
14.20 protected:
15.1 --- a/src/test/Makefile.am Mon May 02 05:49:33 2005 +0000
15.2 +++ b/src/test/Makefile.am Wed May 04 13:07:10 2005 +0000
15.3 @@ -16,7 +16,7 @@
15.4 dfs_test \
15.5 dijkstra_test \
15.6 graph_test \
15.7 - graph_wrapper_test \
15.8 + graph_adaptor_test \
15.9 graph_utils_test \
15.10 kruskal_test \
15.11 max_matching_test \
15.12 @@ -49,7 +49,7 @@
15.13 dijkstra_test_SOURCES = dijkstra_test.cc
15.14 graph_test_SOURCES = graph_test.cc
15.15 graph_utils_test_SOURCES = graph_utils_test.cc
15.16 -graph_wrapper_test_SOURCES = graph_wrapper_test.cc
15.17 +graph_adaptor_test_SOURCES = graph_adaptor_test.cc
15.18 kruskal_test_SOURCES = kruskal_test.cc
15.19 maps_test_SOURCES = maps_test.cc
15.20 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
16.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
16.2 +++ b/src/test/graph_adaptor_test.cc Wed May 04 13:07:10 2005 +0000
16.3 @@ -0,0 +1,75 @@
16.4 +/* -*- C++ -*-
16.5 + * src/test/graph_adaptor_test.cc - Part of LEMON, a generic C++ optimization library
16.6 + *
16.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
16.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
16.9 + *
16.10 + * Permission to use, modify and distribute this software is granted
16.11 + * provided that this copyright notice appears in all copies. For
16.12 + * precise terms see the accompanying LICENSE file.
16.13 + *
16.14 + * This software is provided "AS IS" with no warranty of any kind,
16.15 + * express or implied, and with no claim as to its suitability for any
16.16 + * purpose.
16.17 + *
16.18 + */
16.19 +
16.20 +#include<iostream>
16.21 +#include<lemon/concept_check.h>
16.22 +
16.23 +#include<lemon/smart_graph.h>
16.24 +#include<lemon/concept/graph.h>
16.25 +#include<lemon/concept/undir_graph.h>
16.26 +
16.27 +#include<lemon/list_graph.h>
16.28 +#include<lemon/full_graph.h>
16.29 +#include<lemon/graph_adaptor.h>
16.30 +
16.31 +#include"test/test_tools.h"
16.32 +#include"test/graph_test.h"
16.33 +
16.34 +/**
16.35 +\file
16.36 +This test makes consistency checks of graph adaptors.
16.37 +
16.38 +\todo More extensive tests are needed
16.39 +*/
16.40 +
16.41 +using namespace lemon;
16.42 +using namespace lemon::concept;
16.43 +
16.44 +
16.45 +
16.46 +int main()
16.47 +{
16.48 + {
16.49 + typedef StaticGraph Graph;
16.50 + checkConcept<StaticGraph, GraphAdaptor<Graph> >();
16.51 +
16.52 + checkConcept<StaticGraph, RevGraphAdaptor<Graph> >();
16.53 +
16.54 + checkConcept<StaticGraph, SubGraphAdaptor<Graph,
16.55 + Graph::NodeMap<bool> , Graph::EdgeMap<bool> > >();
16.56 + checkConcept<StaticGraph, NodeSubGraphAdaptor<Graph,
16.57 + Graph::NodeMap<bool> > >();
16.58 + checkConcept<StaticGraph, EdgeSubGraphAdaptor<Graph,
16.59 + Graph::EdgeMap<bool> > >();
16.60 +
16.61 + checkConcept<StaticGraph, SubBidirGraphAdaptor<Graph,
16.62 + Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > >();
16.63 + // checkConcept<StaticGraph, BidirGraph<Graph> >();
16.64 + checkConcept<StaticGraph, ResGraphAdaptor<Graph, int,
16.65 + Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
16.66 +
16.67 + checkConcept<StaticGraph, ErasingFirstGraphAdaptor<Graph,
16.68 + Graph::NodeMap<Graph::Edge> > >();
16.69 +
16.70 + /// \bug why does not compile with StaticGraph
16.71 + checkConcept<BaseIterableUndirGraphConcept, UndirGraphAdaptor<ListGraph> >();
16.72 + checkConcept<IterableUndirGraphConcept, UndirGraphAdaptor<ListGraph> >();
16.73 + checkConcept<MappableUndirGraphConcept, UndirGraphAdaptor<ListGraph> >();
16.74 + }
16.75 + std::cout << __FILE__ ": All tests passed.\n";
16.76 +
16.77 + return 0;
16.78 +}
17.1 --- a/src/test/graph_wrapper_test.cc Mon May 02 05:49:33 2005 +0000
17.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
17.3 @@ -1,75 +0,0 @@
17.4 -/* -*- C++ -*-
17.5 - * src/test/graph_wrapper_test.cc - Part of LEMON, a generic C++ optimization library
17.6 - *
17.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
17.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
17.9 - *
17.10 - * Permission to use, modify and distribute this software is granted
17.11 - * provided that this copyright notice appears in all copies. For
17.12 - * precise terms see the accompanying LICENSE file.
17.13 - *
17.14 - * This software is provided "AS IS" with no warranty of any kind,
17.15 - * express or implied, and with no claim as to its suitability for any
17.16 - * purpose.
17.17 - *
17.18 - */
17.19 -
17.20 -#include<iostream>
17.21 -#include<lemon/concept_check.h>
17.22 -
17.23 -#include<lemon/smart_graph.h>
17.24 -#include<lemon/concept/graph.h>
17.25 -#include<lemon/concept/undir_graph.h>
17.26 -
17.27 -#include<lemon/list_graph.h>
17.28 -#include<lemon/full_graph.h>
17.29 -#include<lemon/graph_wrapper.h>
17.30 -
17.31 -#include"test/test_tools.h"
17.32 -#include"test/graph_test.h"
17.33 -
17.34 -/**
17.35 -\file
17.36 -This test makes consistency checks of graph wrappers.
17.37 -
17.38 -\todo More extensive tests are needed
17.39 -*/
17.40 -
17.41 -using namespace lemon;
17.42 -using namespace lemon::concept;
17.43 -
17.44 -
17.45 -
17.46 -int main()
17.47 -{
17.48 - {
17.49 - typedef StaticGraph Graph;
17.50 - checkConcept<StaticGraph, GraphWrapper<Graph> >();
17.51 -
17.52 - checkConcept<StaticGraph, RevGraphWrapper<Graph> >();
17.53 -
17.54 - checkConcept<StaticGraph, SubGraphWrapper<Graph,
17.55 - Graph::NodeMap<bool> , Graph::EdgeMap<bool> > >();
17.56 - checkConcept<StaticGraph, NodeSubGraphWrapper<Graph,
17.57 - Graph::NodeMap<bool> > >();
17.58 - checkConcept<StaticGraph, EdgeSubGraphWrapper<Graph,
17.59 - Graph::EdgeMap<bool> > >();
17.60 -
17.61 - checkConcept<StaticGraph, SubBidirGraphWrapper<Graph,
17.62 - Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > >();
17.63 - // checkConcept<StaticGraph, BidirGraph<Graph> >();
17.64 - checkConcept<StaticGraph, ResGraphWrapper<Graph, int,
17.65 - Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
17.66 -
17.67 - checkConcept<StaticGraph, ErasingFirstGraphWrapper<Graph,
17.68 - Graph::NodeMap<Graph::Edge> > >();
17.69 -
17.70 - /// \bug why does not compile with StaticGraph
17.71 - checkConcept<BaseIterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
17.72 - checkConcept<IterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
17.73 - checkConcept<MappableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
17.74 - }
17.75 - std::cout << __FILE__ ": All tests passed.\n";
17.76 -
17.77 - return 0;
17.78 -}