61 // }; |
61 // }; |
62 |
62 |
63 // std::cout << sizeof(Bumm) << std::endl; |
63 // std::cout << sizeof(Bumm) << std::endl; |
64 |
64 |
65 |
65 |
66 Graph G; |
66 Graph g; |
67 Node s, t; |
67 Node s, t; |
68 Graph::EdgeMap<int> cap(G); |
68 Graph::EdgeMap<int> cap(g); |
69 readDimacsMaxFlow(std::cin, G, s, t, cap); |
69 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
|
70 readDimacs(std::cin, g, cap, s, t); |
70 Timer ts; |
71 Timer ts; |
71 Graph::EdgeMap<int> flow(G); //0 flow |
72 Graph::EdgeMap<int> flow(g); //0 flow |
72 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
73 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
73 max_flow_test(G, s, t, cap, flow); |
74 max_flow_test(g, s, t, cap, flow); |
74 |
75 |
75 { |
76 { |
76 std::cout << "preflow ..." << std::endl; |
77 std::cout << "preflow ..." << std::endl; |
77 ts.reset(); |
78 ts.reset(); |
78 max_flow_test.run(); |
79 max_flow_test.run(); |
80 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
81 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
81 } |
82 } |
82 |
83 |
83 { |
84 { |
84 std::cout << "preflow ..." << std::endl; |
85 std::cout << "preflow ..." << std::endl; |
85 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
86 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
86 ts.reset(); |
87 ts.reset(); |
87 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
88 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
88 std::cout << "elapsed time: " << ts << std::endl; |
89 std::cout << "elapsed time: " << ts << std::endl; |
89 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
90 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
90 } |
91 } |
91 |
92 |
92 // { |
93 // { |
93 // std::cout << "wrapped preflow ..." << std::endl; |
94 // std::cout << "wrapped preflow ..." << std::endl; |
94 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
95 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
95 // ts.reset(); |
96 // ts.reset(); |
96 // pre_flow_res.run(); |
97 // pre_flow_res.run(); |
97 // std::cout << "elapsed time: " << ts << std::endl; |
98 // std::cout << "elapsed time: " << ts << std::endl; |
98 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
99 // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
99 // } |
100 // } |
100 |
101 |
101 { |
102 { |
102 std::cout << "physical blocking flow augmentation ..." << std::endl; |
103 std::cout << "physical blocking flow augmentation ..." << std::endl; |
103 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
104 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
104 ts.reset(); |
105 ts.reset(); |
105 int i=0; |
106 int i=0; |
106 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
107 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; } |
107 std::cout << "elapsed time: " << ts << std::endl; |
108 std::cout << "elapsed time: " << ts << std::endl; |
108 std::cout << "number of augmentation phases: " << i << std::endl; |
109 std::cout << "number of augmentation phases: " << i << std::endl; |
109 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
110 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
110 } |
111 } |
111 |
112 |
112 // { |
113 // { |
113 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
114 // std::cout << "faster physical blocking flow augmentation ..." << std::endl; |
114 // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
115 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
115 // ts.reset(); |
116 // ts.reset(); |
116 // int i=0; |
117 // int i=0; |
117 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
118 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; } |
118 // std::cout << "elapsed time: " << ts << std::endl; |
119 // std::cout << "elapsed time: " << ts << std::endl; |
119 // std::cout << "number of augmentation phases: " << i << std::endl; |
120 // std::cout << "number of augmentation phases: " << i << std::endl; |
120 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
121 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
121 // } |
122 // } |
122 |
123 |
123 { |
124 { |
124 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
125 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; |
125 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
126 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
126 ts.reset(); |
127 ts.reset(); |
127 int i=0; |
128 int i=0; |
128 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
129 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } |
129 std::cout << "elapsed time: " << ts << std::endl; |
130 std::cout << "elapsed time: " << ts << std::endl; |
130 std::cout << "number of augmentation phases: " << i << std::endl; |
131 std::cout << "number of augmentation phases: " << i << std::endl; |
131 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
132 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
132 } |
133 } |
133 |
134 |
134 { |
135 { |
135 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
136 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; |
136 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
137 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
137 ts.reset(); |
138 ts.reset(); |
138 int i=0; |
139 int i=0; |
139 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
140 while (max_flow_test.augmentOnShortestPath()) { ++i; } |
140 std::cout << "elapsed time: " << ts << std::endl; |
141 std::cout << "elapsed time: " << ts << std::endl; |
141 std::cout << "number of augmentation phases: " << i << std::endl; |
142 std::cout << "number of augmentation phases: " << i << std::endl; |