1 // -*- c++ -*- |
|
2 |
|
3 // Use a DIMACS max flow file as stdin. |
|
4 // sub_graph_wrapper_demo < dimacs_max_flow_file |
|
5 // This program computes a maximum number of edge-disjoint shortest paths |
|
6 // between s and t. |
|
7 |
|
8 #include <iostream> |
|
9 #include <fstream> |
|
10 |
|
11 #include <lemon/smart_graph.h> |
|
12 #include <lemon/dijkstra.h> |
|
13 #include <lemon/maps.h> |
|
14 #include <lemon/graph_wrapper.h> |
|
15 #include <lemon/dimacs.h> |
|
16 #include <lemon/preflow.h> |
|
17 #include <tight_edge_filter_map.h> |
|
18 |
|
19 using namespace lemon; |
|
20 |
|
21 using std::cout; |
|
22 using std::endl; |
|
23 |
|
24 int main() |
|
25 { |
|
26 typedef SmartGraph Graph; |
|
27 |
|
28 typedef Graph::Edge Edge; |
|
29 typedef Graph::Node Node; |
|
30 typedef Graph::EdgeIt EdgeIt; |
|
31 typedef Graph::NodeIt NodeIt; |
|
32 typedef Graph::EdgeMap<int> LengthMap; |
|
33 |
|
34 Graph g; |
|
35 Node s, t; |
|
36 LengthMap length(g); |
|
37 |
|
38 readDimacs(std::cin, g, length, s, t); |
|
39 |
|
40 cout << "edges with lengths (of form id, source--length->target): " << endl; |
|
41 for(EdgeIt e(g); e!=INVALID; ++e) |
|
42 cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" |
|
43 << length[e] << "->" << g.id(g.target(e)) << endl; |
|
44 |
|
45 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; |
|
46 |
|
47 typedef Dijkstra<Graph, LengthMap> Dijkstra; |
|
48 Dijkstra dijkstra(g, length); |
|
49 dijkstra.run(s); |
|
50 |
|
51 // This map returns true exactly for those edges which are |
|
52 // tight w.r.t the length funcion and the potential |
|
53 // given by the dijkstra algorithm. |
|
54 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> |
|
55 TightEdgeFilter; |
|
56 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); |
|
57 |
|
58 // ConstMap<Node, bool> const_true_map(true); |
|
59 // This graph contains exaclty the tight edges. |
|
60 // typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; |
|
61 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW; |
|
62 SubGW gw(g, tight_edge_filter); |
|
63 |
|
64 ConstMap<Edge, int> const_1_map(1); |
|
65 Graph::EdgeMap<int> flow(g, 0); |
|
66 // Max flow between s and t in the graph of tight edges. |
|
67 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > |
|
68 preflow(gw, s, t, const_1_map, flow); |
|
69 preflow.run(); |
|
70 |
|
71 cout << "maximum number of edge-disjoint shortest path: " |
|
72 << preflow.flowValue() << endl; |
|
73 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " |
|
74 << endl; |
|
75 for(EdgeIt e(g); e!=INVALID; ++e) |
|
76 if (flow[e]) |
|
77 cout << " " << g.id(e) << ", " |
|
78 << g.id(g.source(e)) << "--" |
|
79 << length[e] << "->" << g.id(g.target(e)) << endl; |
|
80 } |
|