diff -r ade3cdb9b45d -r 1b7c88fbb950 src/lemon/graph_wrapper.h --- a/src/lemon/graph_wrapper.h Fri Oct 01 10:08:43 2004 +0000 +++ b/src/lemon/graph_wrapper.h Fri Oct 01 11:31:03 2004 +0000 @@ -368,115 +368,9 @@ Note that \c n is of type \c SubGW::NodeIt, but it can be converted to \c Graph::Node that is why \c g.id(n) can be applied. - Consider now a mathematically more invloved problem, where the application - of SubGraphWrapper is reasonable sure enough. If a shortest path is to be - searched between two nodes \c s and \c t, then this can be done easily by - applying the Dijkstra algorithm class. What happens, if a maximum number of - edge-disjoint shortest paths is to be computed. It can be proved that an - edge can be in a shortest path if and only if it is tight with respect to - the potential function computed by Dijkstra. Moreover, any path containing - only such edges is a shortest one. Thus we have to compute a maximum number - of edge-disjoint path between \c s and \c t in the graph which has edge-set - all the tight edges. The computation will be demonstrated on the following - graph, which is read from a dimacs file. - - \dot - digraph lemon_dot_example { - node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; - n0 [ label="0 (s)" ]; - n1 [ label="1" ]; - n2 [ label="2" ]; - n3 [ label="3" ]; - n4 [ label="4" ]; - n5 [ label="5" ]; - n6 [ label="6 (t)" ]; - edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; - n5 -> n6 [ label="9, length:4" ]; - n4 -> n6 [ label="8, length:2" ]; - n3 -> n5 [ label="7, length:1" ]; - n2 -> n5 [ label="6, length:3" ]; - n2 -> n6 [ label="5, length:5" ]; - n2 -> n4 [ label="4, length:2" ]; - n1 -> n4 [ label="3, length:3" ]; - n0 -> n3 [ label="2, length:1" ]; - n0 -> n2 [ label="1, length:2" ]; - n0 -> n1 [ label="0, length:3" ]; - } - \enddot + For other examples see also the documentation of NodeSubGraphWrapper and + EdgeSubGraphWrapper. - \code - Graph g; - Node s, t; - LengthMap length(g); - - readDimacs(std::cin, g, length, s, t); - - cout << "edges with lengths (of form id, tail--length->head): " << endl; - for(EdgeIt e(g); e!=INVALID; ++e) - cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" - << length[e] << "->" << g.id(g.head(e)) << endl; - - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; - \endcode - Next, the potential function is computed with Dijkstra. - \code - typedef Dijkstra Dijkstra; - Dijkstra dijkstra(g, length); - dijkstra.run(s); - \endcode - Next, we consrtruct a map which filters the edge-set to the tight edges. - \code - typedef TightEdgeFilterMap - TightEdgeFilter; - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); - - typedef EdgeSubGraphWrapper SubGW; - SubGW gw(g, tight_edge_filter); - \endcode - Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed - with a max flow algorithm Preflow. - \code - ConstMap const_1_map(1); - Graph::EdgeMap flow(g, 0); - - Preflow, Graph::EdgeMap > - preflow(gw, s, t, const_1_map, flow); - preflow.run(); - \endcode - Last, the output is: - \code - cout << "maximum number of edge-disjoint shortest path: " - << preflow.flowValue() << endl; - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " - << endl; - for(EdgeIt e(g); e!=INVALID; ++e) - if (flow[e]) - cout << " " << g.id(g.tail(e)) << "--" - << length[e] << "->" << g.id(g.head(e)) << endl; - \endcode - The program has the following (expected :-)) output: - \code - edges with lengths (of form id, tail--length->head): - 9, 5--4->6 - 8, 4--2->6 - 7, 3--1->5 - 6, 2--3->5 - 5, 2--5->6 - 4, 2--2->4 - 3, 1--3->4 - 2, 0--1->3 - 1, 0--2->2 - 0, 0--3->1 - s: 0 t: 6 - maximum number of edge-disjoint shortest path: 2 - edges of the maximum number of edge-disjoint shortest s-t paths: - 9, 5--4->6 - 8, 4--2->6 - 7, 3--1->5 - 4, 2--2->4 - 2, 0--1->3 - 1, 0--2->2 - \endcode \author Marton Makai */ template + class NodeSubGraphWrapper : + public SubGraphWrapper > { + public: + typedef SubGraphWrapper > Parent; + protected: + ConstMap const_true_map; + public: + NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : + Parent(), const_true_map(true) { + Parent::setGraph(_graph); + Parent::setNodeFilterMap(_node_filter_map); + Parent::setEdgeFilterMap(const_true_map); + } + }; + + /*! \brief A wrapper for hiding edges from a graph. \warning Graph wrappers are in even more experimental state than the other @@ -677,7 +601,123 @@ A wrapper for hiding edges from a graph. This wrapper specializes SubGraphWrapper in the way that only the edge-set - can be filtered. + can be filtered. The usefulness of this wrapper is demonstrated in the + problem of searching a maximum number of edge-disjoint shortest paths + between + two nodes \c s and \c t. Shortest here means being shortest w.r.t. + non-negative edge-lengths. Note that + the comprehension of the presented solution + need's some knowledge from elementary combinatorial optimization. + + If a single shortest path is to be + searched between two nodes \c s and \c t, then this can be done easily by + applying the Dijkstra algorithm class. What happens, if a maximum number of + edge-disjoint shortest paths is to be computed. It can be proved that an + edge can be in a shortest path if and only if it is tight with respect to + the potential function computed by Dijkstra. Moreover, any path containing + only such edges is a shortest one. Thus we have to compute a maximum number + of edge-disjoint paths between \c s and \c t in the graph which has edge-set + all the tight edges. The computation will be demonstrated on the following + graph, which is read from a dimacs file. + + \dot + digraph lemon_dot_example { + node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; + n0 [ label="0 (s)" ]; + n1 [ label="1" ]; + n2 [ label="2" ]; + n3 [ label="3" ]; + n4 [ label="4" ]; + n5 [ label="5" ]; + n6 [ label="6 (t)" ]; + edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; + n5 -> n6 [ label="9, length:4" ]; + n4 -> n6 [ label="8, length:2" ]; + n3 -> n5 [ label="7, length:1" ]; + n2 -> n5 [ label="6, length:3" ]; + n2 -> n6 [ label="5, length:5" ]; + n2 -> n4 [ label="4, length:2" ]; + n1 -> n4 [ label="3, length:3" ]; + n0 -> n3 [ label="2, length:1" ]; + n0 -> n2 [ label="1, length:2" ]; + n0 -> n1 [ label="0, length:3" ]; + } + \enddot + + \code + Graph g; + Node s, t; + LengthMap length(g); + + readDimacs(std::cin, g, length, s, t); + + cout << "edges with lengths (of form id, tail--length->head): " << endl; + for(EdgeIt e(g); e!=INVALID; ++e) + cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" + << length[e] << "->" << g.id(g.head(e)) << endl; + + cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; + \endcode + Next, the potential function is computed with Dijkstra. + \code + typedef Dijkstra Dijkstra; + Dijkstra dijkstra(g, length); + dijkstra.run(s); + \endcode + Next, we consrtruct a map which filters the edge-set to the tight edges. + \code + typedef TightEdgeFilterMap + TightEdgeFilter; + TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); + + typedef EdgeSubGraphWrapper SubGW; + SubGW gw(g, tight_edge_filter); + \endcode + Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed + with a max flow algorithm Preflow. + \code + ConstMap const_1_map(1); + Graph::EdgeMap flow(g, 0); + + Preflow, Graph::EdgeMap > + preflow(gw, s, t, const_1_map, flow); + preflow.run(); + \endcode + Last, the output is: + \code + cout << "maximum number of edge-disjoint shortest path: " + << preflow.flowValue() << endl; + cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " + << endl; + for(EdgeIt e(g); e!=INVALID; ++e) + if (flow[e]) + cout << " " << g.id(g.tail(e)) << "--" + << length[e] << "->" << g.id(g.head(e)) << endl; + \endcode + The program has the following (expected :-)) output: + \code + edges with lengths (of form id, tail--length->head): + 9, 5--4->6 + 8, 4--2->6 + 7, 3--1->5 + 6, 2--3->5 + 5, 2--5->6 + 4, 2--2->4 + 3, 1--3->4 + 2, 0--1->3 + 1, 0--2->2 + 0, 0--3->1 + s: 0 t: 6 + maximum number of edge-disjoint shortest path: 2 + edges of the maximum number of edge-disjoint shortest s-t paths: + 9, 5--4->6 + 8, 4--2->6 + 7, 3--1->5 + 4, 2--2->4 + 2, 0--1->3 + 1, 0--2->2 + \endcode + \author Marton Makai */ template