Changeset 657:531fc5f575ef in lemon0.x
 Timestamp:
 05/24/04 12:43:44 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@860
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/mincostflow.h
r645 r657 11 11 #include <hugo/maps.h> 12 12 #include <vector> 13 #include <list> 13 14 #include <for_each_macros.h> 15 #include <hugo/union_find.h> 14 16 15 17 namespace hugo { … … 119 121 120 122 typedef typename Graph::template NodeMap<int> HeapMap; 121 typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,123 typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>, 122 124 std::greater<SupplyDemand> > HeapType; 123 125 … … 130 132 HeapType deficit_nodes(deficit_nodes_map); 131 133 134 //A container to store nonabundant arcs 135 list<Edge> nonabundant_arcs; 132 136 133 137 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){ 134 138 flow.set(e,0); 139 nonabundant_arcs.push_back(e); 135 140 } 136 141 137 142 //Initial value for delta 138 143 SupplyDemand delta = 0; 144 145 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE; 146 147 //A unionfind structure to store the abundant components 148 UFE::MapType abund_comp_map(G); 149 UFE abundant_components(abund_comp_map); 150 151 139 152 140 153 FOR_EACH_LOC(typename Graph::NodeIt, n, G){ … … 154 167 //Initialize the copy of the Dijkstra potential to zero 155 168 potential.set(n,0); 169 //Every single point is an abundant component initially 170 abundant_components.insert(n); 156 171 } 157 172 … … 172 187 while (max_excess > 0){ 173 188 189 //Reset delta if still too big 190 if (8*number_of_nodes*max_excess <= delta){ 191 delta = max_excess; 192 193 } 194 174 195 /* 175 196 * Beginning of the delta scaling phase 176 197 */ 177 178 198 //Merge and stuff 199 { 200 SupplyDemand buf=8*number_of_nodes*delta; 201 list<Edge>::iterator i = nonabundant_arcs.begin(); 202 while ( i != nonabundant_arcs.end() ){ 203 if (flow[i]>=buf){ 204 Node a = abundant_components.find(res_graph.head(i)); 205 Node b = abundant_components.find(res_graph.tail(i)); 206 //Merge 207 if (a != b){ 208 //Find path and augment 209 //!!! 210 //Find path and augment 211 abundant_components.join(a,b); 212 } 213 //What happens to i? 214 nonabundant_arcs.erase(i); 215 } 216 else 217 ++i; 218 } 219 } 220 179 221 180 222 Node s = excess_nodes.top(); … … 262 304 } 263 305 */ 264 //Reset delta if still too big 265 if (8*number_of_nodes*max_excess <= delta){ 266 delta = max_excess; 267 268 } 306 269 307 270 308 }//while(max_excess > 0)
Note: See TracChangeset
for help on using the changeset viewer.