Changeset 2629:84354c78b068 in lemon-0.x
- Timestamp:
- 11/13/08 16:29:04 (15 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3514
- Location:
- lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r2623 r2629 255 255 const CostMap &cost, 256 256 const SupplyMap &supply ) : 257 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),258 _supply( graph), _flow(NULL), _local_flow(false),257 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 258 _supply(supply), _flow(NULL), _local_flow(false), 259 259 _potential(NULL), _local_potential(false), 260 _res_cap( graph), _excess(graph), _pred(graph), _dijkstra(NULL)260 _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL) 261 261 { 262 // Removing non-zero lower bounds 263 _capacity = subMap(capacity, lower); 264 _res_cap = _capacity; 262 // Check the sum of supply values 265 263 Supply sum = 0; 266 for (NodeIt n(_graph); n != INVALID; ++n) { 267 Supply s = supply[n]; 268 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 269 s += lower[e]; 270 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 271 s -= lower[e]; 272 _supply[n] = s; 273 sum += s; 274 } 264 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; 275 265 _valid_supply = sum == 0; 266 267 // Remove non-zero lower bounds 268 typename LowerMap::Value lcap; 269 for (EdgeIt e(_graph); e != INVALID; ++e) { 270 if ((lcap = lower[e]) != 0) { 271 _capacity[e] -= lcap; 272 _res_cap[e] -= lcap; 273 _supply[_graph.source(e)] -= lcap; 274 _supply[_graph.target(e)] += lcap; 275 _excess[_graph.source(e)] -= lcap; 276 _excess[_graph.target(e)] += lcap; 277 } 278 } 276 279 } 277 280 … … 291 294 _supply(supply), _flow(NULL), _local_flow(false), 292 295 _potential(NULL), _local_potential(false), 293 _res_cap(capacity), _excess( graph), _pred(graph), _dijkstra(NULL)296 _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL) 294 297 { 295 // Check ingthe sum of supply values298 // Check the sum of supply values 296 299 Supply sum = 0; 297 300 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; … … 317 320 Node s, Node t, 318 321 Supply flow_value ) : 319 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),320 _supply(graph ), _flow(NULL), _local_flow(false),322 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 323 _supply(graph, 0), _flow(NULL), _local_flow(false), 321 324 _potential(NULL), _local_potential(false), 322 _res_cap( graph), _excess(graph), _pred(graph), _dijkstra(NULL)325 _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL) 323 326 { 324 // Removing non-zero lower bounds 325 _capacity = subMap(capacity, lower); 326 _res_cap = _capacity; 327 for (NodeIt n(_graph); n != INVALID; ++n) { 328 Supply sum = 0; 329 if (n == s) sum = flow_value; 330 if (n == t) sum = -flow_value; 331 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 332 sum += lower[e]; 333 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 334 sum -= lower[e]; 335 _supply[n] = sum; 327 // Remove non-zero lower bounds 328 _supply[s] = _excess[s] = flow_value; 329 _supply[t] = _excess[t] = -flow_value; 330 typename LowerMap::Value lcap; 331 for (EdgeIt e(_graph); e != INVALID; ++e) { 332 if ((lcap = lower[e]) != 0) { 333 _capacity[e] -= lcap; 334 _res_cap[e] -= lcap; 335 _supply[_graph.source(e)] -= lcap; 336 _supply[_graph.target(e)] += lcap; 337 _excess[_graph.source(e)] -= lcap; 338 _excess[_graph.target(e)] += lcap; 339 } 336 340 } 337 341 _valid_supply = true; … … 357 361 _supply(graph, 0), _flow(NULL), _local_flow(false), 358 362 _potential(NULL), _local_potential(false), 359 _res_cap(capacity), _excess(graph ), _pred(graph), _dijkstra(NULL)363 _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL) 360 364 { 361 _supply[s] = flow_value;362 _supply[t] = -flow_value;365 _supply[s] = _excess[s] = flow_value; 366 _supply[t] = _excess[t] = -flow_value; 363 367 _valid_supply = true; 364 368 } … … 498 502 for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 499 503 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 500 _excess = _supply;501 504 502 505 _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost, -
lemon/cost_scaling.h
r2625 r2629 201 201 const CostMap &cost, 202 202 const SupplyMap &supply ) : 203 _graph(graph), _lower(&lower), _capacity( graph), _orig_cost(cost),204 _cost(graph), _supply( graph), _flow(NULL), _local_flow(false),203 _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost), 204 _cost(graph), _supply(supply), _flow(NULL), _local_flow(false), 205 205 _potential(NULL), _local_potential(false), _res_cost(_cost), 206 206 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) 207 207 { 208 // Check the sum of supply values 209 Supply sum = 0; 210 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; 211 _valid_supply = sum == 0; 212 208 213 // Remove non-zero lower bounds 209 _capacity = subMap(capacity, lower); 210 Supply sum = 0; 211 for (NodeIt n(_graph); n != INVALID; ++n) { 212 Supply s = supply[n]; 213 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 214 s += lower[e]; 215 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 216 s -= lower[e]; 217 _supply[n] = s; 218 sum += s; 219 } 220 _valid_supply = sum == 0; 214 for (EdgeIt e(_graph); e != INVALID; ++e) { 215 if (lower[e] != 0) { 216 _capacity[e] -= lower[e]; 217 _supply[_graph.source(e)] -= lower[e]; 218 _supply[_graph.target(e)] += lower[e]; 219 } 220 } 221 221 } 222 222 … … 262 262 Node s, Node t, 263 263 Supply flow_value ) : 264 _graph(graph), _lower(&lower), _capacity( graph), _orig_cost(cost),265 _cost(graph), _supply(graph ), _flow(NULL), _local_flow(false),264 _graph(graph), _lower(&lower), _capacity(capacity), _orig_cost(cost), 265 _cost(graph), _supply(graph, 0), _flow(NULL), _local_flow(false), 266 266 _potential(NULL), _local_potential(false), _res_cost(_cost), 267 267 _res_graph(NULL), _red_cost(NULL), _excess(graph, 0) 268 268 { 269 // Remove nonzero lower bounds 270 _capacity = subMap(capacity, lower); 271 for (NodeIt n(_graph); n != INVALID; ++n) { 272 Supply sum = 0; 273 if (n == s) sum = flow_value; 274 if (n == t) sum = -flow_value; 275 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 276 sum += lower[e]; 277 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 278 sum -= lower[e]; 279 _supply[n] = sum; 269 // Remove non-zero lower bounds 270 _supply[s] = flow_value; 271 _supply[t] = -flow_value; 272 for (EdgeIt e(_graph); e != INVALID; ++e) { 273 if (lower[e] != 0) { 274 _capacity[e] -= lower[e]; 275 _supply[_graph.source(e)] -= lower[e]; 276 _supply[_graph.target(e)] += lower[e]; 277 } 280 278 } 281 279 _valid_supply = true; -
lemon/cycle_canceling.h
r2623 r2629 168 168 const CostMap &cost, 169 169 const SupplyMap &supply ) : 170 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),171 _supply( graph), _flow(NULL), _local_flow(false),170 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 171 _supply(supply), _flow(NULL), _local_flow(false), 172 172 _potential(NULL), _local_potential(false), _res_graph(NULL), 173 173 _res_cost(_cost) 174 174 { 175 // Removing non-zero lower bounds 176 _capacity = subMap(capacity, lower); 175 // Check the sum of supply values 177 176 Supply sum = 0; 178 for (NodeIt n(_graph); n != INVALID; ++n) { 179 Supply s = supply[n]; 180 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 181 s += lower[e]; 182 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 183 s -= lower[e]; 184 sum += (_supply[n] = s); 185 } 177 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; 186 178 _valid_supply = sum == 0; 179 180 // Remove non-zero lower bounds 181 for (EdgeIt e(_graph); e != INVALID; ++e) { 182 if (lower[e] != 0) { 183 _capacity[e] -= lower[e]; 184 _supply[_graph.source(e)] -= lower[e]; 185 _supply[_graph.target(e)] += lower[e]; 186 } 187 } 187 188 } 188 189 … … 204 205 _res_cost(_cost) 205 206 { 206 // Check ingthe sum of supply values207 // Check the sum of supply values 207 208 Supply sum = 0; 208 209 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; … … 228 229 Node s, Node t, 229 230 Supply flow_value ) : 230 _graph(graph), _lower(&lower), _capacity( graph), _cost(cost),231 _supply(graph ), _flow(NULL), _local_flow(false),231 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), 232 _supply(graph, 0), _flow(NULL), _local_flow(false), 232 233 _potential(NULL), _local_potential(false), _res_graph(NULL), 233 234 _res_cost(_cost) 234 235 { 235 // Removing non-zero lower bounds 236 _capacity = subMap(capacity, lower); 237 for (NodeIt n(_graph); n != INVALID; ++n) { 238 Supply sum = 0; 239 if (n == s) sum = flow_value; 240 if (n == t) sum = -flow_value; 241 for (InEdgeIt e(_graph, n); e != INVALID; ++e) 242 sum += lower[e]; 243 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) 244 sum -= lower[e]; 245 _supply[n] = sum; 236 // Remove non-zero lower bounds 237 _supply[s] = flow_value; 238 _supply[t] = -flow_value; 239 for (EdgeIt e(_graph); e != INVALID; ++e) { 240 if (lower[e] != 0) { 241 _capacity[e] -= lower[e]; 242 _supply[_graph.source(e)] -= lower[e]; 243 _supply[_graph.target(e)] += lower[e]; 244 } 246 245 } 247 246 _valid_supply = true; -
lemon/network_simplex.h
r2628 r2629 612 612 _node_ref(graph), _edge_ref(graph) 613 613 { 614 // Check ingthe sum of supply values614 // Check the sum of supply values 615 615 Supply sum = 0; 616 616 for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) … … 618 618 if (!(_valid_supply = sum == 0)) return; 619 619 620 // Copy ing_graph_ref to _graph620 // Copy _graph_ref to _graph 621 621 _graph.reserveNode(countNodes(_graph_ref) + 1); 622 622 _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref)); 623 623 copyGraph(_graph, _graph_ref) 624 .edgeMap(_capacity, capacity) 624 625 .edgeMap(_cost, cost) 626 .nodeMap(_supply, supply) 625 627 .nodeRef(_node_ref) 626 628 .edgeRef(_edge_ref) 627 629 .run(); 628 630 629 // Remov ingnon-zero lower bounds631 // Remove non-zero lower bounds 630 632 for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) { 633 if (lower[e] != 0) { 631 634 _capacity[_edge_ref[e]] = capacity[e] - lower[e]; 632 } 633 for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) { 634 Supply s = supply[n]; 635 for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e) 636 s += lower[e]; 637 for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e) 638 s -= lower[e]; 639 _supply[_node_ref[n]] = s; 635 _supply[_node_ref[_graph_ref.source(e)]] -= lower[e]; 636 _supply[_node_ref[_graph_ref.target(e)]] += lower[e]; 637 } 640 638 } 641 639 } … … 662 660 _node_ref(graph), _edge_ref(graph) 663 661 { 664 // Check ingthe sum of supply values662 // Check the sum of supply values 665 663 Supply sum = 0; 666 664 for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) … … 668 666 if (!(_valid_supply = sum == 0)) return; 669 667 670 // Copying _graph_ref to graph 668 // Copy _graph_ref to _graph 669 _graph.reserveNode(countNodes(_graph_ref) + 1); 670 _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref)); 671 671 copyGraph(_graph, _graph_ref) 672 672 .edgeMap(_capacity, capacity) … … 698 698 typename SupplyMap::Value flow_value ) : 699 699 _graph(), _graph_ref(graph), _lower(&lower), _capacity(_graph), 700 _cost(_graph), _supply(_graph ), _flow(_graph),700 _cost(_graph), _supply(_graph, 0), _flow(_graph), 701 701 _potential(_graph), _depth(_graph), _parent(_graph), 702 702 _pred_edge(_graph), _thread(_graph), _forward(_graph), … … 706 706 _node_ref(graph), _edge_ref(graph) 707 707 { 708 // Copying _graph_ref to graph 708 // Copy _graph_ref to graph 709 _graph.reserveNode(countNodes(_graph_ref) + 1); 710 _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref)); 709 711 copyGraph(_graph, _graph_ref) 712 .edgeMap(_capacity, capacity) 710 713 .edgeMap(_cost, cost) 711 714 .nodeRef(_node_ref) … … 713 716 .run(); 714 717 715 // Removing non-zero lower bounds 718 // Remove non-zero lower bounds 719 _supply[_node_ref[s]] = flow_value; 720 _supply[_node_ref[t]] = -flow_value; 716 721 for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e) { 722 if (lower[e] != 0) { 717 723 _capacity[_edge_ref[e]] = capacity[e] - lower[e]; 718 } 719 for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n) { 720 Supply sum = 0; 721 if (n == s) sum = flow_value; 722 if (n == t) sum = -flow_value; 723 for (typename Graph::InEdgeIt e(_graph_ref, n); e != INVALID; ++e) 724 sum += lower[e]; 725 for (typename Graph::OutEdgeIt e(_graph_ref, n); e != INVALID; ++e) 726 sum -= lower[e]; 727 _supply[_node_ref[n]] = sum; 724 _supply[_node_ref[_graph_ref.source(e)]] -= lower[e]; 725 _supply[_node_ref[_graph_ref.target(e)]] += lower[e]; 726 } 728 727 } 729 728 _valid_supply = true; … … 756 755 _node_ref(graph), _edge_ref(graph) 757 756 { 758 // Copying _graph_ref to graph 757 // Copy _graph_ref to graph 758 _graph.reserveNode(countNodes(_graph_ref) + 1); 759 _graph.reserveEdge(countEdges(_graph_ref) + countNodes(_graph_ref)); 759 760 copyGraph(_graph, _graph_ref) 760 761 .edgeMap(_capacity, capacity)
Note: See TracChangeset
for help on using the changeset viewer.