equal
deleted
inserted
replaced
6 2 phase |
6 2 phase |
7 gap |
7 gap |
8 list 'level_list' on the nodes on level i implemented by hand |
8 list 'level_list' on the nodes on level i implemented by hand |
9 stack 'active' on the active nodes on level i implemented by hand |
9 stack 'active' on the active nodes on level i implemented by hand |
10 runs heuristic 'highest label' for H1*n relabels |
10 runs heuristic 'highest label' for H1*n relabels |
11 runs heuristic 'dound decrease' for H0*n relabels, starts with 'highest label' |
11 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' |
12 |
12 |
13 Parameters H0 and H1 are initialized to 20 and 10. |
13 Parameters H0 and H1 are initialized to 20 and 10. |
14 |
14 |
15 The best preflow I could ever write. |
15 The best preflow I could ever write. |
16 |
16 |
41 #define H0 20 |
41 #define H0 20 |
42 #define H1 1 |
42 #define H1 1 |
43 |
43 |
44 #include <vector> |
44 #include <vector> |
45 #include <queue> |
45 #include <queue> |
|
46 |
|
47 #include <time_measure.h> |
46 |
48 |
47 namespace hugo { |
49 namespace hugo { |
48 |
50 |
49 template <typename Graph, typename T, |
51 template <typename Graph, typename T, |
50 typename FlowMap=typename Graph::EdgeMap<T>, |
52 typename FlowMap=typename Graph::EdgeMap<T>, |
63 FlowMap flow; |
65 FlowMap flow; |
64 CapMap& capacity; |
66 CapMap& capacity; |
65 T value; |
67 T value; |
66 |
68 |
67 public: |
69 public: |
68 |
70 double time; |
69 preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) : |
71 preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) : |
70 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) |
72 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) |
71 { |
73 { |
72 |
74 |
73 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd |
75 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd |
164 if ( !what_heur && !end && k > 0 ) { |
166 if ( !what_heur && !end && k > 0 ) { |
165 b=k; |
167 b=k; |
166 end=true; |
168 end=true; |
167 } else { |
169 } else { |
168 phase=1; |
170 phase=1; |
169 |
171 time=currTime(); |
170 level.set(s,0); |
172 level.set(s,0); |
171 std::queue<NodeIt> bfs_queue; |
173 std::queue<NodeIt> bfs_queue; |
172 bfs_queue.push(s); |
174 bfs_queue.push(s); |
173 |
175 |
174 while (!bfs_queue.empty()) { |
176 while (!bfs_queue.empty()) { |