Changeset 775:e46a1f0623a0 in lemon-0.x
- Timestamp:
- 08/31/04 13:26:59 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1068
- Location:
- src
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/graph_wrapper.h
r774 r775 348 348 }; 349 349 350 351 350 352 /// A graph wrapper for hiding nodes and edges from a graph. 351 353 … … 381 383 382 384 typedef typename GraphWrapper<Graph>::Node Node; 383 class NodeIt { 384 friend class GraphWrapper<Graph>; 385 // class NodeIt { 386 // friend class GraphWrapper<Graph>; 387 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 388 // typename Graph::NodeIt n; 389 // public: 390 // NodeIt() { } 391 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } 392 // NodeIt(const Invalid& i) : n(i) { } 393 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 394 // n(*(_G.graph)) { 395 // while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 396 // _G.graph->next(n); 397 // } 398 // operator Node() const { return Node(typename Graph::Node(n)); } 399 // }; 400 class NodeIt : public Node { 401 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 385 402 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 386 typename Graph::NodeIt n; 387 public: 403 public: 388 404 NodeIt() { } 389 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } 390 NodeIt(const Invalid& i) : n(i) { } 391 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 392 n(*(_G.graph)) { 393 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 394 _G.graph->next(n); 395 } 396 operator Node() const { return Node(typename Graph::Node(n)); } 405 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } 406 NodeIt(Invalid i) : Node(i) { } 407 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 408 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } 409 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 410 const Node& n) : 411 Node(n), gw(&_gw) { } 412 NodeIt& operator++() { 413 *(static_cast<Node*>(this))= 414 ++(typename Graph::NodeIt(*(gw->graph), *this)); 415 while (*static_cast<Node*>(this)!=INVALID && 416 !(*(gw->node_filter_map))[*this]) 417 *(static_cast<Node*>(this))= 418 ++(typename Graph::NodeIt(*(gw->graph), *this)); 419 return *this; 420 } 397 421 }; 398 422 typedef typename GraphWrapper<Graph>::Edge Edge; 399 class OutEdgeIt {400 friend class GraphWrapper<Graph>;423 class OutEdgeIt : public Edge { 424 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 401 425 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 402 typename Graph::OutEdgeIt e;403 426 public: 404 427 OutEdgeIt() { } 405 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 406 OutEdgeIt(const Invalid& i) : e(i) { } 407 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 408 const Node& _n) : 409 e(*(_G.graph), typename Graph::Node(_n)) { 410 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 411 _G.graph->next(e); 412 } 413 operator Edge() const { return Edge(typename Graph::Edge(e)); } 414 }; 415 class InEdgeIt { 416 friend class GraphWrapper<Graph>; 428 // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } 429 OutEdgeIt(Invalid i) : Edge(i) { } 430 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 431 Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { } 432 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 433 const Edge& e) : 434 Edge(e), gw(&_gw) { } 435 OutEdgeIt& operator++() { 436 *(static_cast<Edge*>(this))= 437 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 438 while (*static_cast<Edge*>(this)!=INVALID && 439 !(*(gw->edge_filter_map))[*this]) 440 *(static_cast<Edge*>(this))= 441 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 442 return *this; 443 } 444 }; 445 class InEdgeIt : public Edge { 446 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 417 447 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 418 typename Graph::InEdgeIt e;419 448 public: 420 449 InEdgeIt() { } 421 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 422 InEdgeIt(const Invalid& i) : e(i) { } 423 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 424 const Node& _n) : 425 e(*(_G.graph), typename Graph::Node(_n)) { 426 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 427 _G.graph->next(e); 428 } 429 operator Edge() const { return Edge(typename Graph::Edge(e)); } 430 }; 431 //typedef typename Graph::SymEdgeIt SymEdgeIt; 432 class EdgeIt { 433 friend class GraphWrapper<Graph>; 450 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } 451 InEdgeIt(Invalid i) : Edge(i) { } 452 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 453 Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { } 454 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 455 const Edge& e) : 456 Edge(e), gw(&_gw) { } 457 InEdgeIt& operator++() { 458 *(static_cast<Edge*>(this))= 459 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 460 while (*static_cast<Edge*>(this)!=INVALID && 461 !(*(gw->edge_filter_map))[*this]) 462 *(static_cast<Edge*>(this))= 463 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 464 return *this; 465 } 466 }; 467 class EdgeIt : public Edge { 468 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 434 469 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 435 typename Graph::EdgeIt e;436 470 public: 437 471 EdgeIt() { } 438 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } 439 EdgeIt(const Invalid& i) : e(i) { } 440 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 441 e(*(_G.graph)) { 442 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 443 _G.graph->next(e); 444 } 445 operator Edge() const { return Edge(typename Graph::Edge(e)); } 472 // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } 473 EdgeIt(Invalid i) : Edge(i) { } 474 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 475 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } 476 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 477 const Edge& e) : 478 Edge(e), gw(&_gw) { } 479 EdgeIt& operator++() { 480 *(static_cast<Edge*>(this))= 481 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 482 while (*static_cast<Edge*>(this)!=INVALID && 483 !(*(gw->edge_filter_map))[*this]) 484 *(static_cast<Edge*>(this))= 485 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 486 return *this; 487 } 446 488 }; 447 489 … … 459 501 } 460 502 461 NodeIt& next(NodeIt& i) const {462 this->graph->next(i.n);463 while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {464 this->graph->next(i.n); }465 return i;466 }467 OutEdgeIt& next(OutEdgeIt& i) const {468 this->graph->next(i.e);469 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {470 this->graph->next(i.e); }471 return i;472 }473 InEdgeIt& next(InEdgeIt& i) const {474 this->graph->next(i.e);475 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {476 this->graph->next(i.e); }477 return i;478 }479 EdgeIt& next(EdgeIt& i) const {480 this->graph->next(i.e);481 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {482 this->graph->next(i.e); }483 return i;484 }485 486 Node aNode(const OutEdgeIt& e) const {487 return Node(this->graph->aNode(e.e)); }488 Node aNode(const InEdgeIt& e) const {489 return Node(this->graph->aNode(e.e)); }490 Node bNode(const OutEdgeIt& e) const {491 return Node(this->graph->bNode(e.e)); }492 Node bNode(const InEdgeIt& e) const {493 return Node(this->graph->bNode(e.e)); }503 // NodeIt& next(NodeIt& i) const { 504 // this->graph->next(i.n); 505 // while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 506 // this->graph->next(i.n); } 507 // return i; 508 // } 509 // OutEdgeIt& next(OutEdgeIt& i) const { 510 // this->graph->next(i.e); 511 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 512 // this->graph->next(i.e); } 513 // return i; 514 // } 515 // InEdgeIt& next(InEdgeIt& i) const { 516 // this->graph->next(i.e); 517 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 518 // this->graph->next(i.e); } 519 // return i; 520 // } 521 // EdgeIt& next(EdgeIt& i) const { 522 // this->graph->next(i.e); 523 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 524 // this->graph->next(i.e); } 525 // return i; 526 // } 527 528 // Node aNode(const OutEdgeIt& e) const { 529 // return Node(this->graph->aNode(e.e)); } 530 // Node aNode(const InEdgeIt& e) const { 531 // return Node(this->graph->aNode(e.e)); } 532 // Node bNode(const OutEdgeIt& e) const { 533 // return Node(this->graph->bNode(e.e)); } 534 // Node bNode(const InEdgeIt& e) const { 535 // return Node(this->graph->bNode(e.e)); } 494 536 495 537 /// This function hides \c n in the graph, i.e. the iteration … … 754 796 *(static_cast<GraphEdge*>(this))= 755 797 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 756 if (*static_cast<GraphEdge*>(this)==INVALID) 798 if (*static_cast<GraphEdge*>(this)==INVALID) { 757 799 *static_cast<Edge*>(this)= 758 800 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); 759 while (*static_cast<GraphEdge*>(this)!=INVALID && 760 !(*(gw->backward_filter))[*this]) 761 *(static_cast<GraphEdge*>(this))= 762 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 801 while (*static_cast<GraphEdge*>(this)!=INVALID && 802 !(*(gw->backward_filter))[*this]) 803 *(static_cast<GraphEdge*>(this))= 804 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 805 } 763 806 } 764 807 OutEdgeIt(const SubBidirGraphWrapper<Graph, … … 774 817 *(static_cast<GraphEdge*>(this))= 775 818 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 776 if (*static_cast<GraphEdge*>(this)==INVALID) 819 if (*static_cast<GraphEdge*>(this)==INVALID) { 777 820 *static_cast<Edge*>(this)= 778 821 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); 779 while (*static_cast<GraphEdge*>(this)!=INVALID && 780 !(*(gw->backward_filter))[*this]) 781 *(static_cast<GraphEdge*>(this))= 782 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 822 while (*static_cast<GraphEdge*>(this)!=INVALID && 823 !(*(gw->backward_filter))[*this]) 824 *(static_cast<GraphEdge*>(this))= 825 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 826 } 783 827 } else { 784 828 *(static_cast<GraphEdge*>(this))= … … 810 854 *(static_cast<GraphEdge*>(this))= 811 855 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 812 if (*static_cast<GraphEdge*>(this)==INVALID) 856 if (*static_cast<GraphEdge*>(this)==INVALID) { 813 857 *static_cast<Edge*>(this)= 814 858 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); 815 while (*static_cast<GraphEdge*>(this)!=INVALID && 816 !(*(gw->backward_filter))[*this]) 817 *(static_cast<GraphEdge*>(this))= 818 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 859 while (*static_cast<GraphEdge*>(this)!=INVALID && 860 !(*(gw->backward_filter))[*this]) 861 *(static_cast<GraphEdge*>(this))= 862 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 863 } 819 864 } 820 865 InEdgeIt(const SubBidirGraphWrapper<Graph, … … 823 868 InEdgeIt& operator++() { 824 869 if (!this->backward) { 825 Node n=gw-> head(*this);870 Node n=gw->tail(*this); 826 871 *(static_cast<GraphEdge*>(this))= 827 872 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); … … 830 875 *(static_cast<GraphEdge*>(this))= 831 876 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 832 if (*static_cast<GraphEdge*>(this)==INVALID) 877 if (*static_cast<GraphEdge*>(this)==INVALID) { 833 878 *static_cast<Edge*>(this)= 834 879 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); 835 while (*static_cast<GraphEdge*>(this)!=INVALID && 836 !(*(gw->backward_filter))[*this]) 837 *(static_cast<GraphEdge*>(this))= 838 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 880 while (*static_cast<GraphEdge*>(this)!=INVALID && 881 !(*(gw->backward_filter))[*this]) 882 *(static_cast<GraphEdge*>(this))= 883 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 884 } 839 885 } else { 840 886 *(static_cast<GraphEdge*>(this))= … … 860 906 //the unique invalid iterator 861 907 EdgeIt(const SubBidirGraphWrapper<Graph, 862 863 Edge(typename Graph:: EdgeIt(*(_gw.graph)), false), gw(&_gw) {908 ForwardFilterMap, BackwardFilterMap>& _gw) : 909 Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) { 864 910 while (*static_cast<GraphEdge*>(this)!=INVALID && 865 911 !(*(gw->forward_filter))[*this]) 866 912 *(static_cast<GraphEdge*>(this))= 867 913 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 868 if (*static_cast<GraphEdge*>(this)==INVALID) 914 if (*static_cast<GraphEdge*>(this)==INVALID) { 869 915 *static_cast<Edge*>(this)= 870 916 Edge(typename Graph::EdgeIt(*(_gw.graph)), true); 871 while (*static_cast<GraphEdge*>(this)!=INVALID && 872 !(*(gw->backward_filter))[*this]) 873 *(static_cast<GraphEdge*>(this))= 874 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 917 while (*static_cast<GraphEdge*>(this)!=INVALID && 918 !(*(gw->backward_filter))[*this]) 919 *(static_cast<GraphEdge*>(this))= 920 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 921 } 875 922 } 876 923 EdgeIt(const SubBidirGraphWrapper<Graph, … … 885 932 *(static_cast<GraphEdge*>(this))= 886 933 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 887 if (*static_cast<GraphEdge*>(this)==INVALID) 934 if (*static_cast<GraphEdge*>(this)==INVALID) { 888 935 *static_cast<Edge*>(this)= 889 936 Edge(typename Graph::EdgeIt(*(gw->graph)), true); 890 while (*static_cast<GraphEdge*>(this)!=INVALID && 891 !(*(gw->backward_filter))[*this]) 892 *(static_cast<GraphEdge*>(this))= 893 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 937 while (*static_cast<GraphEdge*>(this)!=INVALID && 938 !(*(gw->backward_filter))[*this]) 939 *(static_cast<GraphEdge*>(this))= 940 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 941 } 894 942 } else { 895 943 *(static_cast<GraphEdge*>(this))= -
src/work/marci/augmenting_flow.h
r762 r775 1021 1021 case AFTER_AUGMENTING: 1022 1022 // std::cout << "AFTER_AUGMENTING" << std::endl; 1023 for(g->first(v); g->valid(v); g->next(v)) {1023 for(g->first(v); v!=INVALID; ++v) { 1024 1024 if (level[v]) { 1025 1025 M.set(v, true); … … 1031 1031 case AFTER_FAST_AUGMENTING: 1032 1032 // std::cout << "AFTER_FAST_AUGMENTING" << std::endl; 1033 for(g->first(v); g->valid(v); g->next(v)) {1033 for(g->first(v); v!=INVALID; ++v) { 1034 1034 if (level[v]==number_of_augmentations) { 1035 1035 M.set(v, true); … … 1054 1054 1055 1055 OutEdgeIt e; 1056 for(g->first(e,w) ; g->valid(e); g->next(e)) {1056 for(g->first(e,w) ; e!=INVALID; ++e) { 1057 1057 Node v=g->head(e); 1058 1058 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { … … 1063 1063 1064 1064 InEdgeIt f; 1065 for(g->first(f,w) ; g->valid(f); g->next(f)) {1065 for(g->first(f,w) ; f!=INVALID; ++f) { 1066 1066 Node v=g->tail(f); 1067 1067 if (!M[v] && (*flow)[f] > 0 ) { … … 1134 1134 while ( !bfs.finished() ) { 1135 1135 ResGWOutEdgeIt e=bfs; 1136 if ( res_graph.valid(e)&& bfs.isBNodeNewlyReached()) {1136 if (e!=INVALID && bfs.isBNodeNewlyReached()) { 1137 1137 Node v=res_graph.tail(e); 1138 1138 Node w=res_graph.head(e); 1139 1139 pred.set(w, e); 1140 if ( res_graph.valid(pred[v])) {1140 if (pred[v]!=INVALID) { 1141 1141 free.set(w, std::min(free[v], res_graph.resCap(e))); 1142 1142 } else { … … 1152 1152 Node n=t; 1153 1153 Num augment_value=free[t]; 1154 while ( res_graph.valid(pred[n])) {1154 while (pred[n]!=INVALID) { 1155 1155 ResGWEdge e=pred[n]; 1156 1156 res_graph.augment(e, augment_value); … … 1191 1191 while ( !bfs.finished() ) { 1192 1192 ResGWOutEdgeIt e=bfs; 1193 if ( res_graph.valid(e)&& bfs.isBNodeNewlyReached()) {1193 if (e!=INVALID && bfs.isBNodeNewlyReached()) { 1194 1194 Node v=res_graph.tail(e); 1195 1195 Node w=res_graph.head(e); 1196 1196 pred.set(w, e); 1197 if ( res_graph.valid(pred[v])) {1197 if (pred[v]!=INVALID) { 1198 1198 free.set(w, std::min(free[v], res_graph.resCap(e))); 1199 1199 } else { … … 1209 1209 Node n=t; 1210 1210 Num augment_value=free[t]; 1211 while ( res_graph.valid(pred[n])) {1211 while (pred[n]!=INVALID) { 1212 1212 ResGWEdge e=pred[n]; 1213 1213 res_graph.augment(e, augment_value); … … 1245 1245 { 1246 1246 typename ResGW::NodeIt n; 1247 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {1247 for(res_graph.first(n); n!=INVALID; ++n) { 1248 1248 res_graph_to_F.set(n, F.addNode()); 1249 1249 } … … 1257 1257 while ( !bfs.finished() ) { 1258 1258 ResGWOutEdgeIt e=bfs; 1259 if ( res_graph.valid(e)) {1259 if (e!=INVALID) { 1260 1260 if (bfs.isBNodeNewlyReached()) { 1261 1261 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); … … 1300 1300 typename MG::Node w=F.bNode(dfs); 1301 1301 pred.set(w, dfs); 1302 if ( F.valid(pred[v])) {1302 if (pred[v]!=INVALID) { 1303 1303 free.set(w, std::min(free[v], residual_capacity[dfs])); 1304 1304 } else { … … 1320 1320 typename MG::Node n=tF; 1321 1321 Num augment_value=free[tF]; 1322 while ( F.valid(pred[n])) {1322 while (pred[n]!=INVALID) { 1323 1323 typename MG::Edge e=pred[n]; 1324 1324 res_graph.augment(original_edge[e], augment_value); … … 1338 1338 1339 1339 1340 1341 1342 1340 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 1343 1341 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() … … 1355 1353 while ( !bfs.finished() ) { 1356 1354 ResGWOutEdgeIt e=bfs; 1357 if ( res_graph.valid(e)&& bfs.isBNodeNewlyReached()) {1355 if (e!=INVALID && bfs.isBNodeNewlyReached()) { 1358 1356 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); 1359 1357 } … … 1372 1370 first_out_edges(filter_res_graph); 1373 1371 typename FilterResGW::NodeIt v; 1374 for(filter_res_graph.first(v); filter_res_graph.valid(v); 1375 filter_res_graph.next(v)) 1372 for(filter_res_graph.first(v); v!=INVALID; ++v) 1376 1373 { 1377 1374 typename FilterResGW::OutEdgeIt e; … … 1419 1416 1420 1417 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); 1421 if ( erasing_res_graph.valid(pred[v])) {1418 if (pred[v]!=INVALID) { 1422 1419 free1.set 1423 1420 (w, std::min(free1[v], res_graph.resCap -
src/work/marci/makefile
r773 r775 5 5 6 6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 7 BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 7 BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba8 8 8 #BINARIES = preflow_bug 9 9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda -
src/work/marci/max_flow_demo.cc
r762 r775 17 17 18 18 // Use a DIMACS max flow file as stdin. 19 // read_dimacs_demo < dimacs_max_flow_file 20 21 22 // struct Ize { 23 // }; 24 25 // struct Mize { 26 // Ize bumm; 27 // }; 28 29 // template <typename B> 30 // class Huha { 31 // public: 32 // int u; 33 // B brr; 34 // }; 35 19 // max_flow_demo < dimacs_max_flow_file 36 20 37 21 int main(int, char **) { … … 44 28 typedef Graph::Node Node; 45 29 typedef Graph::EdgeIt EdgeIt; 46 47 48 // Mize mize[10];49 // Mize bize[0];50 // Mize zize;51 // typedef Mize Tize[0];52 53 // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;54 // std::cout << sizeof(bize) << std::endl;55 56 57 // Huha<Tize> k;58 // std::cout << sizeof(k) << std::endl;59 60 61 // struct Bumm {62 // //int a;63 // bool b;64 // };65 66 // std::cout << sizeof(Bumm) << std::endl;67 68 30 69 31 Graph g; … … 142 104 143 105 // { 144 // std::cout << " faster physicalblocking flow augmentation ..." << std::endl;106 // std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; 145 107 // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); 146 108 // ts.reset(); 147 109 // int i=0; 148 // while ( max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }110 // while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; } 149 111 // std::cout << "elapsed time: " << ts << std::endl; 150 112 // std::cout << "number of augmentation phases: " << i << std::endl; 151 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 113 // std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 114 115 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 116 // if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 117 // std::cout << "Slackness does not hold!" << std::endl; 118 // if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 119 // std::cout << "Slackness does not hold!" << std::endl; 120 // } 152 121 // } 153 154 {155 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;156 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);157 ts.reset();158 int i=0;159 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }160 std::cout << "elapsed time: " << ts << std::endl;161 std::cout << "number of augmentation phases: " << i << std::endl;162 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;163 164 FOR_EACH_LOC(Graph::EdgeIt, e, g) {165 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])166 std::cout << "Slackness does not hold!" << std::endl;167 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)168 std::cout << "Slackness does not hold!" << std::endl;169 }170 }171 122 172 123 {
Note: See TracChangeset
for help on using the changeset viewer.