diff -r d8475431bbbb -r 8e85e6bbefdf src/demo/sub_graph_adaptor_demo.cc --- a/src/demo/sub_graph_adaptor_demo.cc Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -// -*- c++ -*- - -// Use a DIMACS max flow file as stdin. -// sub_graph_adaptor_demo < dimacs_max_flow_file -// This program computes a maximum number of edge-disjoint shortest paths -// between s and t. - -#include -#include - -#include -#include -#include -#include -#include -#include -#include - -using namespace lemon; - -using std::cout; -using std::endl; - -int main() -{ - typedef SmartGraph Graph; - - typedef Graph::Edge Edge; - typedef Graph::Node Node; - typedef Graph::EdgeIt EdgeIt; - typedef Graph::NodeIt NodeIt; - typedef Graph::EdgeMap LengthMap; - - Graph g; - Node s, t; - LengthMap length(g); - - readDimacs(std::cin, g, length, s, t); - - cout << "edges with lengths (of form id, source--length->target): " << endl; - for(EdgeIt e(g); e!=INVALID; ++e) - cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" - << length[e] << "->" << g.id(g.target(e)) << endl; - - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; - - typedef Dijkstra Dijkstra; - Dijkstra dijkstra(g, length); - dijkstra.run(s); - - // This map returns true exactly for those edges which are - // tight w.r.t the length funcion and the potential - // given by the dijkstra algorithm. - typedef TightEdgeFilterMap - TightEdgeFilter; - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); - -// ConstMap const_true_map(true); - // This graph contains exaclty the tight edges. -// typedef SubGraphAdaptor, TightEdgeFilter> SubGW; - typedef EdgeSubGraphAdaptor SubGW; - SubGW gw(g, tight_edge_filter); - - ConstMap const_1_map(1); - Graph::EdgeMap flow(g, 0); - // Max flow between s and t in the graph of tight edges. - Preflow, Graph::EdgeMap > - preflow(gw, s, t, const_1_map, flow); - preflow.run(); - - 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(e) << ", " - << g.id(g.source(e)) << "--" - << length[e] << "->" << g.id(g.target(e)) << endl; -}