1 | // -*- c++ -*- |
---|

2 | |
---|

3 | // Use a DIMACS max flow file as stdin. |
---|

4 | // sub_graph_wrapper_demo < dimacs_max_flow_file |
---|

5 | |
---|

6 | #include <iostream> |
---|

7 | #include <fstream> |
---|

8 | |
---|

9 | #include <hugo/smart_graph.h> |
---|

10 | #include <hugo/dijkstra.h> |
---|

11 | #include <hugo/maps.h> |
---|

12 | #include <hugo/graph_wrapper.h> |
---|

13 | #include <hugo/dimacs.h> |
---|

14 | #include <hugo/preflow.h> |
---|

15 | #include <tight_edge_filter_map.h> |
---|

16 | |
---|

17 | using namespace hugo; |
---|

18 | |
---|

19 | using std::cout; |
---|

20 | using std::endl; |
---|

21 | |
---|

22 | int main() |
---|

23 | { |
---|

24 | typedef SmartGraph Graph; |
---|

25 | |
---|

26 | typedef Graph::Edge Edge; |
---|

27 | typedef Graph::Node Node; |
---|

28 | typedef Graph::EdgeIt EdgeIt; |
---|

29 | typedef Graph::NodeIt NodeIt; |
---|

30 | typedef Graph::EdgeMap<int> LengthMap; |
---|

31 | |
---|

32 | Graph g; |
---|

33 | Node s, t; |
---|

34 | LengthMap length(g); |
---|

35 | |
---|

36 | readDimacs(std::cin, g, length, s, t); |
---|

37 | |
---|

38 | cout << "edges with lengths (of form tail--length->head): " << endl; |
---|

39 | for(EdgeIt e(g); e!=INVALID; ++e) |
---|

40 | cout << " " << g.id(g.tail(e)) << "--" |
---|

41 | << length[e] << "->" << g.id(g.head(e)) << endl; |
---|

42 | |
---|

43 | cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; |
---|

44 | |
---|

45 | typedef Dijkstra<Graph, LengthMap> Dijkstra; |
---|

46 | Dijkstra dijkstra(g, length); |
---|

47 | dijkstra.run(s); |
---|

48 | |
---|

49 | typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> |
---|

50 | TightEdgeFilter; |
---|

51 | TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); |
---|

52 | |
---|

53 | ConstMap<Node, bool> const_true_map(true); |
---|

54 | typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; |
---|

55 | SubGW gw(g, const_true_map, tight_edge_filter); |
---|

56 | |
---|

57 | ConstMap<Edge, int> const_1_map(1); |
---|

58 | Graph::EdgeMap<int> flow(g, 0); |
---|

59 | Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > |
---|

60 | preflow(gw, s, t, const_1_map, flow); |
---|

61 | preflow.run(); |
---|

62 | |
---|

63 | cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " |
---|

64 | << endl; |
---|

65 | for(EdgeIt e(g); e!=INVALID; ++e) |
---|

66 | if (flow[e]) |
---|

67 | cout << " " << g.id(g.tail(e)) << "--" |
---|

68 | << length[e] << "->" << g.id(g.head(e)) << endl; |
---|

69 | |
---|

70 | return 0; |
---|

71 | } |
---|