1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 |
2 |
3 // Use a DIMACS max flow file as stdin. |
3 // Use a DIMACS max flow file as stdin. |
4 // sub_graph_wrapper_demo < dimacs_max_flow_file |
4 // sub_graph_adaptor_demo < dimacs_max_flow_file |
5 // This program computes a maximum number of edge-disjoint shortest paths |
5 // This program computes a maximum number of edge-disjoint shortest paths |
6 // between s and t. |
6 // between s and t. |
7 |
7 |
8 #include <iostream> |
8 #include <iostream> |
9 #include <fstream> |
9 #include <fstream> |
10 |
10 |
11 #include <lemon/smart_graph.h> |
11 #include <lemon/smart_graph.h> |
12 #include <lemon/dijkstra.h> |
12 #include <lemon/dijkstra.h> |
13 #include <lemon/maps.h> |
13 #include <lemon/maps.h> |
14 #include <lemon/graph_wrapper.h> |
14 #include <lemon/graph_adaptor.h> |
15 #include <lemon/dimacs.h> |
15 #include <lemon/dimacs.h> |
16 #include <lemon/preflow.h> |
16 #include <lemon/preflow.h> |
17 #include <tight_edge_filter_map.h> |
17 #include <tight_edge_filter_map.h> |
18 |
18 |
19 using namespace lemon; |
19 using namespace lemon; |
55 TightEdgeFilter; |
55 TightEdgeFilter; |
56 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); |
56 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); |
57 |
57 |
58 // ConstMap<Node, bool> const_true_map(true); |
58 // ConstMap<Node, bool> const_true_map(true); |
59 // This graph contains exaclty the tight edges. |
59 // This graph contains exaclty the tight edges. |
60 // typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; |
60 // typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; |
61 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW; |
61 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW; |
62 SubGW gw(g, tight_edge_filter); |
62 SubGW gw(g, tight_edge_filter); |
63 |
63 |
64 ConstMap<Edge, int> const_1_map(1); |
64 ConstMap<Edge, int> const_1_map(1); |
65 Graph::EdgeMap<int> flow(g, 0); |
65 Graph::EdgeMap<int> flow(g, 0); |
66 // Max flow between s and t in the graph of tight edges. |
66 // Max flow between s and t in the graph of tight edges. |