1.1 --- a/src/demo/sub_graph_wrapper_demo.cc Mon May 02 05:49:33 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,80 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -
1.6 -// Use a DIMACS max flow file as stdin.
1.7 -// sub_graph_wrapper_demo < dimacs_max_flow_file
1.8 -// This program computes a maximum number of edge-disjoint shortest paths
1.9 -// between s and t.
1.10 -
1.11 -#include <iostream>
1.12 -#include <fstream>
1.13 -
1.14 -#include <lemon/smart_graph.h>
1.15 -#include <lemon/dijkstra.h>
1.16 -#include <lemon/maps.h>
1.17 -#include <lemon/graph_wrapper.h>
1.18 -#include <lemon/dimacs.h>
1.19 -#include <lemon/preflow.h>
1.20 -#include <tight_edge_filter_map.h>
1.21 -
1.22 -using namespace lemon;
1.23 -
1.24 -using std::cout;
1.25 -using std::endl;
1.26 -
1.27 -int main()
1.28 -{
1.29 - typedef SmartGraph Graph;
1.30 -
1.31 - typedef Graph::Edge Edge;
1.32 - typedef Graph::Node Node;
1.33 - typedef Graph::EdgeIt EdgeIt;
1.34 - typedef Graph::NodeIt NodeIt;
1.35 - typedef Graph::EdgeMap<int> LengthMap;
1.36 -
1.37 - Graph g;
1.38 - Node s, t;
1.39 - LengthMap length(g);
1.40 -
1.41 - readDimacs(std::cin, g, length, s, t);
1.42 -
1.43 - cout << "edges with lengths (of form id, source--length->target): " << endl;
1.44 - for(EdgeIt e(g); e!=INVALID; ++e)
1.45 - cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--"
1.46 - << length[e] << "->" << g.id(g.target(e)) << endl;
1.47 -
1.48 - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.49 -
1.50 - typedef Dijkstra<Graph, LengthMap> Dijkstra;
1.51 - Dijkstra dijkstra(g, length);
1.52 - dijkstra.run(s);
1.53 -
1.54 - // This map returns true exactly for those edges which are
1.55 - // tight w.r.t the length funcion and the potential
1.56 - // given by the dijkstra algorithm.
1.57 - typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.58 - TightEdgeFilter;
1.59 - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.60 -
1.61 -// ConstMap<Node, bool> const_true_map(true);
1.62 - // This graph contains exaclty the tight edges.
1.63 -// typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
1.64 - typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
1.65 - SubGW gw(g, tight_edge_filter);
1.66 -
1.67 - ConstMap<Edge, int> const_1_map(1);
1.68 - Graph::EdgeMap<int> flow(g, 0);
1.69 - // Max flow between s and t in the graph of tight edges.
1.70 - Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.71 - preflow(gw, s, t, const_1_map, flow);
1.72 - preflow.run();
1.73 -
1.74 - cout << "maximum number of edge-disjoint shortest path: "
1.75 - << preflow.flowValue() << endl;
1.76 - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.77 - << endl;
1.78 - for(EdgeIt e(g); e!=INVALID; ++e)
1.79 - if (flow[e])
1.80 - cout << " " << g.id(e) << ", "
1.81 - << g.id(g.source(e)) << "--"
1.82 - << length[e] << "->" << g.id(g.target(e)) << endl;
1.83 -}