equal
deleted
inserted
replaced
116 total_length = 0; |
116 total_length = 0; |
117 |
117 |
118 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ |
118 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ |
119 flow.set(e,0); |
119 flow.set(e,0); |
120 } |
120 } |
121 |
121 |
|
122 //Initialize the potential to zero |
122 FOR_EACH_LOC(typename Graph::NodeIt, n, G){ |
123 FOR_EACH_LOC(typename Graph::NodeIt, n, G){ |
123 //cout << potential[n]<<endl; |
|
124 potential.set(n,0); |
124 potential.set(n,0); |
125 } |
125 } |
126 |
126 |
127 |
127 |
128 |
128 |
129 //We need a residual graph |
129 //We need a residual graph |
130 ResGraphType res_graph(G, capacity, flow); |
130 ResGraphType res_graph(G, capacity, flow); |
131 |
|
132 //Initialize the copy of the Dijkstra potential to zero |
|
133 |
|
134 //typename ResGraphType::template NodeMap<Length> potential(res_graph); |
|
135 |
131 |
136 |
132 |
137 ModLengthMap mod_length(res_graph, length, potential); |
133 ModLengthMap mod_length(res_graph, length, potential); |
138 |
134 |
139 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
135 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
144 if (!dijkstra.reached(t)){ |
140 if (!dijkstra.reached(t)){ |
145 //There are no k paths from s to t |
141 //There are no k paths from s to t |
146 break; |
142 break; |
147 }; |
143 }; |
148 |
144 |
149 //We have to copy the potential |
145 //We have to change the potential |
150 FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){ |
146 FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){ |
151 potential[n] += dijkstra.distMap()[n]; |
147 potential[n] += dijkstra.distMap()[n]; |
152 } |
148 } |
153 /* |
149 |
154 { |
|
155 //We have to copy the potential |
|
156 typename ResGraphType::NodeIt n; |
|
157 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
|
158 potential[n] += dijkstra.distMap()[n]; |
|
159 } |
|
160 } |
|
161 */ |
|
162 |
150 |
163 //Augmenting on the sortest path |
151 //Augmenting on the sortest path |
164 Node n=t; |
152 Node n=t; |
165 ResGraphEdge e; |
153 ResGraphEdge e; |
166 while (n!=s){ |
154 while (n!=s){ |