1.1 --- a/src/lemon/graph_wrapper.h Fri Oct 01 10:08:43 2004 +0000
1.2 +++ b/src/lemon/graph_wrapper.h Fri Oct 01 11:31:03 2004 +0000
1.3 @@ -368,115 +368,9 @@
1.4 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
1.5 \c Graph::Node that is why \c g.id(n) can be applied.
1.6
1.7 - Consider now a mathematically more invloved problem, where the application
1.8 - of SubGraphWrapper is reasonable sure enough. If a shortest path is to be
1.9 - searched between two nodes \c s and \c t, then this can be done easily by
1.10 - applying the Dijkstra algorithm class. What happens, if a maximum number of
1.11 - edge-disjoint shortest paths is to be computed. It can be proved that an
1.12 - edge can be in a shortest path if and only if it is tight with respect to
1.13 - the potential function computed by Dijkstra. Moreover, any path containing
1.14 - only such edges is a shortest one. Thus we have to compute a maximum number
1.15 - of edge-disjoint path between \c s and \c t in the graph which has edge-set
1.16 - all the tight edges. The computation will be demonstrated on the following
1.17 - graph, which is read from a dimacs file.
1.18 -
1.19 - \dot
1.20 - digraph lemon_dot_example {
1.21 - node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.22 - n0 [ label="0 (s)" ];
1.23 - n1 [ label="1" ];
1.24 - n2 [ label="2" ];
1.25 - n3 [ label="3" ];
1.26 - n4 [ label="4" ];
1.27 - n5 [ label="5" ];
1.28 - n6 [ label="6 (t)" ];
1.29 - edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.30 - n5 -> n6 [ label="9, length:4" ];
1.31 - n4 -> n6 [ label="8, length:2" ];
1.32 - n3 -> n5 [ label="7, length:1" ];
1.33 - n2 -> n5 [ label="6, length:3" ];
1.34 - n2 -> n6 [ label="5, length:5" ];
1.35 - n2 -> n4 [ label="4, length:2" ];
1.36 - n1 -> n4 [ label="3, length:3" ];
1.37 - n0 -> n3 [ label="2, length:1" ];
1.38 - n0 -> n2 [ label="1, length:2" ];
1.39 - n0 -> n1 [ label="0, length:3" ];
1.40 - }
1.41 - \enddot
1.42 + For other examples see also the documentation of NodeSubGraphWrapper and
1.43 + EdgeSubGraphWrapper.
1.44
1.45 - \code
1.46 - Graph g;
1.47 - Node s, t;
1.48 - LengthMap length(g);
1.49 -
1.50 - readDimacs(std::cin, g, length, s, t);
1.51 -
1.52 - cout << "edges with lengths (of form id, tail--length->head): " << endl;
1.53 - for(EdgeIt e(g); e!=INVALID; ++e)
1.54 - cout << g.id(e) << ", " << g.id(g.tail(e)) << "--"
1.55 - << length[e] << "->" << g.id(g.head(e)) << endl;
1.56 -
1.57 - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.58 - \endcode
1.59 - Next, the potential function is computed with Dijkstra.
1.60 - \code
1.61 - typedef Dijkstra<Graph, LengthMap> Dijkstra;
1.62 - Dijkstra dijkstra(g, length);
1.63 - dijkstra.run(s);
1.64 - \endcode
1.65 - Next, we consrtruct a map which filters the edge-set to the tight edges.
1.66 - \code
1.67 - typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.68 - TightEdgeFilter;
1.69 - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.70 -
1.71 - typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
1.72 - SubGW gw(g, tight_edge_filter);
1.73 - \endcode
1.74 - Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
1.75 - with a max flow algorithm Preflow.
1.76 - \code
1.77 - ConstMap<Edge, int> const_1_map(1);
1.78 - Graph::EdgeMap<int> flow(g, 0);
1.79 -
1.80 - Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.81 - preflow(gw, s, t, const_1_map, flow);
1.82 - preflow.run();
1.83 - \endcode
1.84 - Last, the output is:
1.85 - \code
1.86 - cout << "maximum number of edge-disjoint shortest path: "
1.87 - << preflow.flowValue() << endl;
1.88 - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.89 - << endl;
1.90 - for(EdgeIt e(g); e!=INVALID; ++e)
1.91 - if (flow[e])
1.92 - cout << " " << g.id(g.tail(e)) << "--"
1.93 - << length[e] << "->" << g.id(g.head(e)) << endl;
1.94 - \endcode
1.95 - The program has the following (expected :-)) output:
1.96 - \code
1.97 - edges with lengths (of form id, tail--length->head):
1.98 - 9, 5--4->6
1.99 - 8, 4--2->6
1.100 - 7, 3--1->5
1.101 - 6, 2--3->5
1.102 - 5, 2--5->6
1.103 - 4, 2--2->4
1.104 - 3, 1--3->4
1.105 - 2, 0--1->3
1.106 - 1, 0--2->2
1.107 - 0, 0--3->1
1.108 - s: 0 t: 6
1.109 - maximum number of edge-disjoint shortest path: 2
1.110 - edges of the maximum number of edge-disjoint shortest s-t paths:
1.111 - 9, 5--4->6
1.112 - 8, 4--2->6
1.113 - 7, 3--1->5
1.114 - 4, 2--2->4
1.115 - 2, 0--1->3
1.116 - 1, 0--2->2
1.117 - \endcode
1.118 \author Marton Makai
1.119 */
1.120 template<typename Graph, typename NodeFilterMap,
1.121 @@ -670,6 +564,36 @@
1.122 };
1.123
1.124
1.125 + /*! \brief A wrapper for hiding nodes from a graph.
1.126 +
1.127 + \warning Graph wrappers are in even more experimental state than the other
1.128 + parts of the lib. Use them at you own risk.
1.129 +
1.130 + A wrapper for hiding nodes from a graph.
1.131 + This wrapper specializes SubGraphWrapper in the way that only the node-set
1.132 + can be filtered. Note that this does not mean of considering induced
1.133 + subgraph, the edge-iterators consider the original edge-set.
1.134 + \author Marton Makai
1.135 + */
1.136 + template<typename Graph, typename NodeFilterMap>
1.137 + class NodeSubGraphWrapper :
1.138 + public SubGraphWrapper<Graph, NodeFilterMap,
1.139 + ConstMap<typename Graph::Edge,bool> > {
1.140 + public:
1.141 + typedef SubGraphWrapper<Graph, NodeFilterMap,
1.142 + ConstMap<typename Graph::Edge,bool> > Parent;
1.143 + protected:
1.144 + ConstMap<typename Graph::Edge, bool> const_true_map;
1.145 + public:
1.146 + NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
1.147 + Parent(), const_true_map(true) {
1.148 + Parent::setGraph(_graph);
1.149 + Parent::setNodeFilterMap(_node_filter_map);
1.150 + Parent::setEdgeFilterMap(const_true_map);
1.151 + }
1.152 + };
1.153 +
1.154 +
1.155 /*! \brief A wrapper for hiding edges from a graph.
1.156
1.157 \warning Graph wrappers are in even more experimental state than the other
1.158 @@ -677,7 +601,123 @@
1.159
1.160 A wrapper for hiding edges from a graph.
1.161 This wrapper specializes SubGraphWrapper in the way that only the edge-set
1.162 - can be filtered.
1.163 + can be filtered. The usefulness of this wrapper is demonstrated in the
1.164 + problem of searching a maximum number of edge-disjoint shortest paths
1.165 + between
1.166 + two nodes \c s and \c t. Shortest here means being shortest w.r.t.
1.167 + non-negative edge-lengths. Note that
1.168 + the comprehension of the presented solution
1.169 + need's some knowledge from elementary combinatorial optimization.
1.170 +
1.171 + If a single shortest path is to be
1.172 + searched between two nodes \c s and \c t, then this can be done easily by
1.173 + applying the Dijkstra algorithm class. What happens, if a maximum number of
1.174 + edge-disjoint shortest paths is to be computed. It can be proved that an
1.175 + edge can be in a shortest path if and only if it is tight with respect to
1.176 + the potential function computed by Dijkstra. Moreover, any path containing
1.177 + only such edges is a shortest one. Thus we have to compute a maximum number
1.178 + of edge-disjoint paths between \c s and \c t in the graph which has edge-set
1.179 + all the tight edges. The computation will be demonstrated on the following
1.180 + graph, which is read from a dimacs file.
1.181 +
1.182 + \dot
1.183 + digraph lemon_dot_example {
1.184 + node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.185 + n0 [ label="0 (s)" ];
1.186 + n1 [ label="1" ];
1.187 + n2 [ label="2" ];
1.188 + n3 [ label="3" ];
1.189 + n4 [ label="4" ];
1.190 + n5 [ label="5" ];
1.191 + n6 [ label="6 (t)" ];
1.192 + edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.193 + n5 -> n6 [ label="9, length:4" ];
1.194 + n4 -> n6 [ label="8, length:2" ];
1.195 + n3 -> n5 [ label="7, length:1" ];
1.196 + n2 -> n5 [ label="6, length:3" ];
1.197 + n2 -> n6 [ label="5, length:5" ];
1.198 + n2 -> n4 [ label="4, length:2" ];
1.199 + n1 -> n4 [ label="3, length:3" ];
1.200 + n0 -> n3 [ label="2, length:1" ];
1.201 + n0 -> n2 [ label="1, length:2" ];
1.202 + n0 -> n1 [ label="0, length:3" ];
1.203 + }
1.204 + \enddot
1.205 +
1.206 + \code
1.207 + Graph g;
1.208 + Node s, t;
1.209 + LengthMap length(g);
1.210 +
1.211 + readDimacs(std::cin, g, length, s, t);
1.212 +
1.213 + cout << "edges with lengths (of form id, tail--length->head): " << endl;
1.214 + for(EdgeIt e(g); e!=INVALID; ++e)
1.215 + cout << g.id(e) << ", " << g.id(g.tail(e)) << "--"
1.216 + << length[e] << "->" << g.id(g.head(e)) << endl;
1.217 +
1.218 + cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.219 + \endcode
1.220 + Next, the potential function is computed with Dijkstra.
1.221 + \code
1.222 + typedef Dijkstra<Graph, LengthMap> Dijkstra;
1.223 + Dijkstra dijkstra(g, length);
1.224 + dijkstra.run(s);
1.225 + \endcode
1.226 + Next, we consrtruct a map which filters the edge-set to the tight edges.
1.227 + \code
1.228 + typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.229 + TightEdgeFilter;
1.230 + TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.231 +
1.232 + typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
1.233 + SubGW gw(g, tight_edge_filter);
1.234 + \endcode
1.235 + Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
1.236 + with a max flow algorithm Preflow.
1.237 + \code
1.238 + ConstMap<Edge, int> const_1_map(1);
1.239 + Graph::EdgeMap<int> flow(g, 0);
1.240 +
1.241 + Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.242 + preflow(gw, s, t, const_1_map, flow);
1.243 + preflow.run();
1.244 + \endcode
1.245 + Last, the output is:
1.246 + \code
1.247 + cout << "maximum number of edge-disjoint shortest path: "
1.248 + << preflow.flowValue() << endl;
1.249 + cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.250 + << endl;
1.251 + for(EdgeIt e(g); e!=INVALID; ++e)
1.252 + if (flow[e])
1.253 + cout << " " << g.id(g.tail(e)) << "--"
1.254 + << length[e] << "->" << g.id(g.head(e)) << endl;
1.255 + \endcode
1.256 + The program has the following (expected :-)) output:
1.257 + \code
1.258 + edges with lengths (of form id, tail--length->head):
1.259 + 9, 5--4->6
1.260 + 8, 4--2->6
1.261 + 7, 3--1->5
1.262 + 6, 2--3->5
1.263 + 5, 2--5->6
1.264 + 4, 2--2->4
1.265 + 3, 1--3->4
1.266 + 2, 0--1->3
1.267 + 1, 0--2->2
1.268 + 0, 0--3->1
1.269 + s: 0 t: 6
1.270 + maximum number of edge-disjoint shortest path: 2
1.271 + edges of the maximum number of edge-disjoint shortest s-t paths:
1.272 + 9, 5--4->6
1.273 + 8, 4--2->6
1.274 + 7, 3--1->5
1.275 + 4, 2--2->4
1.276 + 2, 0--1->3
1.277 + 1, 0--2->2
1.278 + \endcode
1.279 +
1.280 \author Marton Makai
1.281 */
1.282 template<typename Graph, typename EdgeFilterMap>