Changeset 986:e997802b855c in lemon-0.x for src/work/marci/experiment
- Timestamp:
- 11/13/04 13:53:28 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
- Location:
- src/work/marci/experiment
- Files:
-
- 10 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/experiment/edmonds_karp.h
r921 r986 41 41 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } 42 42 Number free() const { 43 if (resG->G.aNode(sym)==resG->G. tail(sym)) {43 if (resG->G.aNode(sym)==resG->G.source(sym)) { 44 44 return (resG->capacity.get(sym)-resG->flow.get(sym)); 45 45 } else { … … 49 49 bool valid() const { return sym.valid(); } 50 50 void augment(Number a) const { 51 if (resG->G.aNode(sym)==resG->G. tail(sym)) {51 if (resG->G.aNode(sym)==resG->G.source(sym)) { 52 52 resG->flow.set(sym, resG->flow.get(sym)+a); 53 53 //resG->flow[sym]+=a; … … 97 97 } 98 98 99 Node tail(Edge e) const { return G.aNode(e.sym); }100 Node head(Edge e) const { return G.bNode(e.sym); }99 Node source(Edge e) const { return G.aNode(e.sym); } 100 Node target(Edge e) const { return G.bNode(e.sym); } 101 101 102 102 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } … … 224 224 } 225 225 226 Node tail(Edge e) const {226 Node source(Edge e) const { 227 227 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 228 Node head(Edge e) const {228 Node target(Edge e) const { 229 229 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 230 230 … … 288 288 ResGWOutEdgeIt e=bfs; 289 289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 290 Node v=res_graph. tail(e);291 Node w=res_graph. head(e);290 Node v=res_graph.source(e); 291 Node w=res_graph.target(e); 292 292 pred.set(w, e); 293 293 if (res_graph.valid(pred.get(v))) { … … 296 296 free.set(w, res_graph.resCap(e)); 297 297 } 298 if (res_graph. head(e)==t) { _augment=true; break; }298 if (res_graph.target(e)==t) { _augment=true; break; } 299 299 } 300 300 … … 308 308 ResGWEdge e=pred.get(n); 309 309 res_graph.augment(e, augment_value); 310 n=res_graph. tail(e);310 n=res_graph.source(e); 311 311 } 312 312 } … … 325 325 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } 326 326 bool get(const typename MapGraphWrapper::Edge& e) const { 327 return (dist.get(gw. tail(e))<dist.get(gw.head(e)));327 return (dist.get(gw.source(e))<dist.get(gw.target(e))); 328 328 } 329 329 }; … … 344 344 ResGWOutEdgeIt e=bfs; 345 345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 346 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);346 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 347 347 } 348 348 ++bfs; … … 370 370 typename FilterResGW::EdgeIt e; 371 371 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 372 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));372 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 374 374 original_edge.update(); 375 375 original_edge.set(f, e); … … 424 424 typename MG::Edge e=pred.get(n); 425 425 res_graph.augment(original_edge.get(e), augment_value); 426 n=F. tail(e);426 n=F.source(e); 427 427 if (residual_capacity.get(e)==augment_value) 428 428 F.erase(e); … … 469 469 if (res_graph.valid(e)) { 470 470 if (bfs.isBNodeNewlyReached()) { 471 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));471 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 473 473 original_edge.update(); 474 474 original_edge.set(f, e); … … 476 476 residual_capacity.set(f, res_graph.resCap(e)); 477 477 } else { 478 if (dist.get(res_graph. head(e))==(dist.get(res_graph.tail(e))+1)) {479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));478 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { 479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 480 480 original_edge.update(); 481 481 original_edge.set(f, e); … … 532 532 typename MG::Edge e=pred.get(n); 533 533 res_graph.augment(original_edge.get(e), augment_value); 534 n=F. tail(e);534 n=F.source(e); 535 535 if (residual_capacity.get(e)==augment_value) 536 536 F.erase(e); … … 558 558 ResGWOutEdgeIt e=bfs; 559 559 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 560 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);560 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 561 561 } 562 562 ++bfs; … … 634 634 typename ErasingResGW::OutEdgeIt e=pred.get(n); 635 635 res_graph.augment(e, augment_value); 636 n=erasing_res_graph. tail(e);636 n=erasing_res_graph.source(e); 637 637 if (res_graph.resCap(e)==0) 638 638 erasing_res_graph.erase(e); … … 669 669 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 670 670 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 671 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);671 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 672 672 // } 673 673 // ++bfs; … … 723 723 // EAugEdge e=pred.get(n); 724 724 // res_graph.augment(e, augment_value); 725 // n=res_graph. tail(e);725 // n=res_graph.source(e); 726 726 // if (res_graph.free(e)==0) 727 727 // res_graph.erase(e); … … 818 818 // AugOutEdgeIt e=bfs; 819 819 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 820 // Node v=res_graph. tail(e);821 // Node w=res_graph. head(e);820 // Node v=res_graph.source(e); 821 // Node w=res_graph.target(e); 822 822 // pred.set(w, e); 823 823 // if (res_graph.valid(pred.get(v))) { … … 826 826 // free.set(w, res_graph.free(e)); 827 827 // } 828 // n=res_graph. head(e);828 // n=res_graph.target(e); 829 829 // if (T->get(n) && (used.get(n)<1) ) { 830 830 // //Number u=0; … … 848 848 // AugEdge e=pred.get(n); 849 849 // res_graph.augment(e, augment_value); 850 // n=res_graph. tail(e);850 // n=res_graph.source(e); 851 851 // } 852 852 // used.set(n, 1); //mind2 vegen jav … … 889 889 // // AugOutEdgeIt e=bfs; 890 890 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 891 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);891 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 892 892 // // } 893 893 … … 911 911 // // //which are in some shortest paths 912 912 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 913 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {914 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));913 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 914 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 915 915 // // original_edge.update(); 916 916 // // original_edge.set(f, e); … … 964 964 // // typename MutableGraph::Edge e=pred.get(n); 965 965 // // res_graph.augment(original_edge.get(e), augment_value); 966 // // n=F. tail(e);966 // // n=F.source(e); 967 967 // // if (residual_capacity.get(e)==augment_value) 968 968 // // F.erase(e); … … 1015 1015 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 1016 1016 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 1017 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);1017 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 1018 1018 // } 1019 1019 // ++bfs; … … 1092 1092 // EAugEdge e=pred.get(n); 1093 1093 // res_graph.augment(e, augment_value); 1094 // n=res_graph. tail(e);1094 // n=res_graph.source(e); 1095 1095 // if (res_graph.free(e)==0) 1096 1096 // res_graph.erase(e); … … 1185 1185 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 1186 1186 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 1187 // // Node v=res_graph. tail(e);1188 // // Node w=res_graph. head(e);1187 // // Node v=res_graph.source(e); 1188 // // Node w=res_graph.target(e); 1189 1189 // // pred.set(w, e); 1190 1190 // // if (pred.get(v).valid()) { … … 1193 1193 // // free.set(w, e.free()); 1194 1194 // // } 1195 // // if (TMap.get(res_graph. head(e))) {1195 // // if (TMap.get(res_graph.target(e))) { 1196 1196 // // _augment=true; 1197 // // reached_t_node=res_graph. head(e);1197 // // reached_t_node=res_graph.target(e); 1198 1198 // // break; 1199 1199 // // } … … 1209 1209 // // AugEdge e=pred.get(n); 1210 1210 // // e.augment(augment_value); 1211 // // n=res_graph. tail(e);1211 // // n=res_graph.source(e); 1212 1212 // // } 1213 1213 // // } -
src/work/marci/experiment/edmonds_karp_1.h
r921 r986 42 42 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } 43 43 Number free() const { 44 if (resG->G.aNode(sym)==resG->G. tail(sym)) {44 if (resG->G.aNode(sym)==resG->G.source(sym)) { 45 45 return (resG->capacity.get(sym)-resG->flow.get(sym)); 46 46 } else { … … 50 50 bool valid() const { return sym.valid(); } 51 51 void augment(Number a) const { 52 if (resG->G.aNode(sym)==resG->G. tail(sym)) {52 if (resG->G.aNode(sym)==resG->G.source(sym)) { 53 53 resG->flow.set(sym, resG->flow.get(sym)+a); 54 54 //resG->flow[sym]+=a; … … 98 98 } 99 99 100 Node tail(Edge e) const { return G.aNode(e.sym); }101 Node head(Edge e) const { return G.bNode(e.sym); }100 Node source(Edge e) const { return G.aNode(e.sym); } 101 Node target(Edge e) const { return G.bNode(e.sym); } 102 102 103 103 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } … … 225 225 } 226 226 227 Node tail(Edge e) const {227 Node source(Edge e) const { 228 228 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 229 Node head(Edge e) const {229 Node target(Edge e) const { 230 230 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 231 231 … … 287 287 ResGWOutEdgeIt e=bfs; 288 288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 289 Node v=res_graph. tail(e);290 Node w=res_graph. head(e);289 Node v=res_graph.source(e); 290 Node w=res_graph.target(e); 291 291 pred.set(w, e); 292 292 if (res_graph.valid(pred.get(v))) { … … 295 295 free.set(w, res_graph.resCap(e)); 296 296 } 297 if (res_graph. head(e)==t) { _augment=true; break; }297 if (res_graph.target(e)==t) { _augment=true; break; } 298 298 } 299 299 … … 307 307 ResGWEdge e=pred.get(n); 308 308 res_graph.augment(e, augment_value); 309 n=res_graph. tail(e);309 n=res_graph.source(e); 310 310 } 311 311 } … … 324 324 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } 325 325 bool get(const typename MapGraphWrapper::Edge& e) const { 326 return (dist.get(g-> tail(e))<dist.get(g->head(e)));326 return (dist.get(g->source(e))<dist.get(g->target(e))); 327 327 } 328 328 }; … … 343 343 ResGWOutEdgeIt e=bfs; 344 344 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 345 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);345 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 346 346 } 347 347 ++bfs; … … 369 369 typename FilterResGW::EdgeIt e; 370 370 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 371 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));371 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 373 373 original_edge.update(); 374 374 original_edge.set(f, e); … … 423 423 typename MG::Edge e=pred.get(n); 424 424 res_graph.augment(original_edge.get(e), augment_value); 425 n=F. tail(e);425 n=F.source(e); 426 426 if (residual_capacity.get(e)==augment_value) 427 427 F.erase(e); … … 468 468 if (res_graph.valid(e)) { 469 469 if (bfs.isBNodeNewlyReached()) { 470 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));470 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 472 472 original_edge.update(); 473 473 original_edge.set(f, e); … … 475 475 residual_capacity.set(f, res_graph.resCap(e)); 476 476 } else { 477 if (dist.get(res_graph. head(e))==(dist.get(res_graph.tail(e))+1)) {478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));477 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { 478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 479 479 original_edge.update(); 480 480 original_edge.set(f, e); … … 531 531 typename MG::Edge e=pred.get(n); 532 532 res_graph.augment(original_edge.get(e), augment_value); 533 n=F. tail(e);533 n=F.source(e); 534 534 if (residual_capacity.get(e)==augment_value) 535 535 F.erase(e); … … 557 557 ResGWOutEdgeIt e=bfs; 558 558 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 559 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);559 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 560 560 } 561 561 ++bfs; … … 633 633 typename ErasingResGW::OutEdgeIt e=pred.get(n); 634 634 res_graph.augment(e, augment_value); 635 n=erasing_res_graph. tail(e);635 n=erasing_res_graph.source(e); 636 636 if (res_graph.resCap(e)==0) 637 637 erasing_res_graph.erase(e); … … 728 728 // AugOutEdgeIt e=bfs; 729 729 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 730 // Node v=res_graph. tail(e);731 // Node w=res_graph. head(e);730 // Node v=res_graph.source(e); 731 // Node w=res_graph.target(e); 732 732 // pred.set(w, e); 733 733 // if (res_graph.valid(pred.get(v))) { … … 736 736 // free.set(w, res_graph.free(e)); 737 737 // } 738 // n=res_graph. head(e);738 // n=res_graph.target(e); 739 739 // if (T->get(n) && (used.get(n)<1) ) { 740 740 // //Number u=0; … … 758 758 // AugEdge e=pred.get(n); 759 759 // res_graph.augment(e, augment_value); 760 // n=res_graph. tail(e);760 // n=res_graph.source(e); 761 761 // } 762 762 // used.set(n, 1); //mind2 vegen jav … … 799 799 // // AugOutEdgeIt e=bfs; 800 800 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 801 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);801 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 802 802 // // } 803 803 … … 821 821 // // //which are in some shortest paths 822 822 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 823 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));823 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 825 825 // // original_edge.update(); 826 826 // // original_edge.set(f, e); … … 874 874 // // typename MutableGraph::Edge e=pred.get(n); 875 875 // // res_graph.augment(original_edge.get(e), augment_value); 876 // // n=F. tail(e);876 // // n=F.source(e); 877 877 // // if (residual_capacity.get(e)==augment_value) 878 878 // // F.erase(e); … … 925 925 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 926 926 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 927 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);927 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 928 928 // } 929 929 // ++bfs; … … 1002 1002 // EAugEdge e=pred.get(n); 1003 1003 // res_graph.augment(e, augment_value); 1004 // n=res_graph. tail(e);1004 // n=res_graph.source(e); 1005 1005 // if (res_graph.free(e)==0) 1006 1006 // res_graph.erase(e); … … 1095 1095 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 1096 1096 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 1097 // // Node v=res_graph. tail(e);1098 // // Node w=res_graph. head(e);1097 // // Node v=res_graph.source(e); 1098 // // Node w=res_graph.target(e); 1099 1099 // // pred.set(w, e); 1100 1100 // // if (pred.get(v).valid()) { … … 1103 1103 // // free.set(w, e.free()); 1104 1104 // // } 1105 // // if (TMap.get(res_graph. head(e))) {1105 // // if (TMap.get(res_graph.target(e))) { 1106 1106 // // _augment=true; 1107 // // reached_t_node=res_graph. head(e);1107 // // reached_t_node=res_graph.target(e); 1108 1108 // // break; 1109 1109 // // } … … 1119 1119 // // AugEdge e=pred.get(n); 1120 1120 // // e.augment(augment_value); 1121 // // n=res_graph. tail(e);1121 // // n=res_graph.source(e); 1122 1122 // // } 1123 1123 // // } -
src/work/marci/experiment/edmonds_karp_demo.cc
r921 r986 105 105 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 106 106 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 107 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";107 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 116 116 // } 117 117 // std::cout<<std::endl; … … 136 136 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 137 137 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 138 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";138 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 147 147 // } 148 148 // std::cout<<std::endl; … … 167 167 while (max_flow_test.augmentOnBlockingFlow2()) { 168 168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 169 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";169 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 178 178 // } 179 179 // std::cout<<std::endl; … … 198 198 while (max_flow_test.augmentOnShortestPath()) { 199 199 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 200 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";200 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 209 209 // } 210 210 // std::cout<<std::endl; -
src/work/marci/experiment/edmonds_karp_demo_1.cc
r921 r986 105 105 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 106 106 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 107 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";107 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 108 // } 109 // std::cout<<std::endl; 110 ++i; 111 } 112 113 // std::cout << "maximum flow: "<< std::endl; 114 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 115 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 116 116 // } 117 117 // std::cout<<std::endl; … … 136 136 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 137 137 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 138 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";138 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 139 // } 140 // std::cout<<std::endl; 141 ++i; 142 } 143 144 // std::cout << "maximum flow: "<< std::endl; 145 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 146 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 147 147 // } 148 148 // std::cout<<std::endl; … … 167 167 while (max_flow_test.augmentOnBlockingFlow2()) { 168 168 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 169 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";169 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 170 // } 171 // std::cout<<std::endl; 172 ++i; 173 } 174 175 // std::cout << "maximum flow: "<< std::endl; 176 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 177 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 178 178 // } 179 179 // std::cout<<std::endl; … … 198 198 while (max_flow_test.augmentOnShortestPath()) { 199 199 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 200 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";200 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 201 // } 202 // std::cout<<std::endl; 203 ++i; 204 } 205 206 // std::cout << "maximum flow: "<< std::endl; 207 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 208 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 209 209 // } 210 210 // std::cout<<std::endl; -
src/work/marci/experiment/graph_wrapper.h
r921 r986 97 97 It e; first(e, v); return e; } 98 98 99 Node head(const Edge& e) const { return graph->head(e); }100 Node tail(const Edge& e) const { return graph->tail(e); }99 Node target(const Edge& e) const { return graph->target(e); } 100 Node source(const Edge& e) const { return graph->source(e); } 101 101 102 102 template<typename I> bool valid(const I& i) const … … 115 115 116 116 Node addNode() const { return graph->addNode(); } 117 Edge addEdge(const Node& tail, const Node& head) const {118 return graph->addEdge( tail, head); }117 Edge addEdge(const Node& source, const Node& target) const { 118 return graph->addEdge(source, target); } 119 119 120 120 template<typename I> void erase(const I& i) const { graph->erase(i); } … … 246 246 It e; this->first(e, v); return e; } 247 247 248 Node head(const Edge& e) const { return gw.head(e); }249 Node tail(const Edge& e) const { return gw.tail(e); }248 Node target(const Edge& e) const { return gw.target(e); } 249 Node source(const Edge& e) const { return gw.source(e); } 250 250 251 251 template<typename I> bool valid(const I& i) const { return gw.valid(i); } … … 261 261 262 262 Node addNode() const { return gw.addNode(); } 263 Edge addEdge(const Node& tail, const Node& head) const {264 return gw.addEdge( tail, head); }263 Edge addEdge(const Node& source, const Node& target) const { 264 return gw.addEdge(source, target); } 265 265 266 266 template<typename I> void erase(const I& i) const { gw.erase(i); } … … 323 323 // It e; first(e, v); return e; } 324 324 325 // Node head(const Edge& e) const { return graph->tail(e); }326 // Node tail(const Edge& e) const { return graph->head(e); }325 // Node target(const Edge& e) const { return graph->source(e); } 326 // Node source(const Edge& e) const { return graph->target(e); } 327 327 328 328 // template<typename I> bool valid(const I& i) const … … 338 338 339 339 // Node addNode() const { return graph->addNode(); } 340 // Edge addEdge(const Node& tail, const Node& head) const {341 // return graph->addEdge( tail, head); }340 // Edge addEdge(const Node& source, const Node& target) const { 341 // return graph->addEdge(source, target); } 342 342 343 343 // int nodeNum() const { return graph->nodeNum(); } … … 404 404 // // It e; first(e, v); return e; } 405 405 406 // //Node head(const Edge& e) const { return graph->tail(e); }407 // //Node tail(const Edge& e) const { return graph->head(e); }406 // //Node target(const Edge& e) const { return graph->source(e); } 407 // //Node source(const Edge& e) const { return graph->target(e); } 408 408 409 409 // //template<typename I> bool valid(const I& i) const … … 419 419 420 420 // //Node addNode() const { return graph->addNode(); } 421 // //Edge addEdge(const Node& tail, const Node& head) const {422 // // return graph->addEdge( tail, head); }421 // //Edge addEdge(const Node& source, const Node& target) const { 422 // // return graph->addEdge(source, target); } 423 423 424 424 // //int nodeNum() const { return graph->nodeNum(); } … … 468 468 GraphWrapper<GraphWrapper>(_gw) { } 469 469 470 Node head(const Edge& e) const471 { return GraphWrapper<GraphWrapper>:: tail(e); }472 Node tail(const Edge& e) const473 { return GraphWrapper<GraphWrapper>:: head(e); }470 Node target(const Edge& e) const 471 { return GraphWrapper<GraphWrapper>::source(e); } 472 Node source(const Edge& e) const 473 { return GraphWrapper<GraphWrapper>::target(e); } 474 474 }; 475 475 … … 600 600 // OutEdgeIt& next(OutEdgeIt& e) const { 601 601 // if (e.out_or_in) { 602 // Node n=gw. tail(e.out);602 // Node n=gw.source(e.out); 603 603 // gw.next(e.out); 604 604 // if (!gw.valid(e.out)) { … … 613 613 614 614 // Node aNode(const OutEdgeIt& e) const { 615 // if (e.out_or_in) return gw. tail(e); else return gw.head(e); }615 // if (e.out_or_in) return gw.source(e); else return gw.target(e); } 616 616 // Node bNode(const OutEdgeIt& e) const { 617 // if (e.out_or_in) return gw. head(e); else return gw.tail(e); }617 // if (e.out_or_in) return gw.target(e); else return gw.source(e); } 618 618 619 619 // typedef OutEdgeIt InEdgeIt; … … 633 633 // It e; first(e, v); return e; } 634 634 635 // Node head(const Edge& e) const { return gw.head(e); }636 // Node tail(const Edge& e) const { return gw.tail(e); }635 // Node target(const Edge& e) const { return gw.target(e); } 636 // Node source(const Edge& e) const { return gw.source(e); } 637 637 638 638 // template<typename I> bool valid(const I& i) const … … 652 652 // Node addNode() const { return gw.addNode(); } 653 653 // // FIXME: ez igy nem jo, mert nem 654 // // Edge addEdge(const Node& tail, const Node& head) const {655 // // return graph->addEdge( tail, head); }654 // // Edge addEdge(const Node& source, const Node& target) const { 655 // // return graph->addEdge(source, target); } 656 656 657 657 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 799 799 OutEdgeIt& next(OutEdgeIt& e) const { 800 800 if (e.out_or_in) { 801 Node n=gw. tail(e.out);801 Node n=gw.source(e.out); 802 802 gw.next(e.out); 803 803 if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); } … … 809 809 810 810 EdgeIt& next(EdgeIt& e) const { 811 //NodeIt v= tail(e);811 //NodeIt v=source(e); 812 812 gw.next(e.out); 813 813 while (valid(e.v) && !gw.valid(e.out)) { … … 827 827 It e; first(e, v); return e; } 828 828 829 // Node head(const Edge& e) const { return gw.head(e); }830 // Node tail(const Edge& e) const { return gw.tail(e); }829 // Node target(const Edge& e) const { return gw.target(e); } 830 // Node source(const Edge& e) const { return gw.source(e); } 831 831 832 832 // template<typename I> bool valid(const I& i) const … … 842 842 843 843 Node aNode(const OutEdgeIt& e) const { 844 if (e.out_or_in) return gw. tail(e); else return gw.head(e); }844 if (e.out_or_in) return gw.source(e); else return gw.target(e); } 845 845 Node bNode(const OutEdgeIt& e) const { 846 if (e.out_or_in) return gw. head(e); else return gw.tail(e); }846 if (e.out_or_in) return gw.target(e); else return gw.source(e); } 847 847 848 848 // Node addNode() const { return gw.addNode(); } 849 849 850 850 // FIXME: ez igy nem jo, mert nem 851 // Edge addEdge(const Node& tail, const Node& head) const {852 // return graph->addEdge( tail, head); }851 // Edge addEdge(const Node& source, const Node& target) const { 852 // return graph->addEdge(source, target); } 853 853 854 854 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 914 914 // It e; first(e, v); return e; } 915 915 916 // Node head(const Edge& e) const { return graph->head(e); }917 // Node tail(const Edge& e) const { return graph->tail(e); }916 // Node target(const Edge& e) const { return graph->target(e); } 917 // Node source(const Edge& e) const { return graph->source(e); } 918 918 919 919 // template<typename I> Node aNode(const I& e) const { … … 929 929 930 930 // Node addNode() { return graph->addNode(); } 931 // Edge addEdge(const Node& tail, const Node& head) {932 // return graph->addEdge( tail, head); }931 // Edge addEdge(const Node& source, const Node& target) { 932 // return graph->addEdge(source, target); } 933 933 934 934 // template<typename I> void erase(const I& i) { graph->erase(i); } … … 1181 1181 } 1182 1182 1183 Node tail(Edge e) const {1183 Node source(Edge e) const { 1184 1184 return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); } 1185 Node head(Edge e) const {1185 Node target(Edge e) const { 1186 1186 return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); } 1187 1187 … … 1312 1312 OutEdgeIt f=e; 1313 1313 this->next(f); 1314 first_out_edges->set(this-> tail(e), f);1314 first_out_edges->set(this->source(e), f); 1315 1315 } 1316 1316 }; … … 1382 1382 // It e; first(e, v); return e; } 1383 1383 1384 // //Node head(const Edge& e) const { return gw.head(e); }1385 // //Node tail(const Edge& e) const { return gw.tail(e); }1384 // //Node target(const Edge& e) const { return gw.target(e); } 1385 // //Node source(const Edge& e) const { return gw.source(e); } 1386 1386 1387 1387 // //template<typename I> bool valid(const I& i) const … … 1397 1397 1398 1398 // //Node addNode() const { return gw.addNode(); } 1399 // //Edge addEdge(const Node& tail, const Node& head) const {1400 // // return gw.addEdge( tail, head); }1399 // //Edge addEdge(const Node& source, const Node& target) const { 1400 // // return gw.addEdge(source, target); } 1401 1401 1402 1402 // //void erase(const OutEdgeIt& e) { 1403 // // first_out_edge(this-> tail(e))=e;1403 // // first_out_edge(this->source(e))=e; 1404 1404 // //} 1405 1405 // void erase(const Edge& e) { 1406 1406 // OutEdgeIt f(e); 1407 1407 // next(f); 1408 // first_out_edges.set(this-> tail(e), f);1408 // first_out_edges.set(this->source(e), f); 1409 1409 // } 1410 1410 // //template<typename I> void erase(const I& i) const { gw.erase(i); } … … 1460 1460 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 1461 1461 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n); 1462 // while (valid(e) && (dist.get( tail(e))/*+1!=*/>=dist.get(head(e))))1462 // while (valid(e) && (dist.get(source(e))/*+1!=*/>=dist.get(target(e)))) 1463 1463 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 1464 1464 // return e; … … 1471 1471 // OutEdgeIt& next(OutEdgeIt& e) const { 1472 1472 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 1473 // while (valid(e) && (dist.get( tail(e))/*+1!*/>=dist.get(head(e))))1473 // while (valid(e) && (dist.get(source(e))/*+1!*/>=dist.get(target(e)))) 1474 1474 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); 1475 1475 // return e; … … 1483 1483 // OutEdgeIt f(e); 1484 1484 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); 1485 // while (valid(f) && (dist.get( tail(f))/*+1!=*/>=dist.get(head(f))))1485 // while (valid(f) && (dist.get(source(f))/*+1!=*/>=dist.get(target(f)))) 1486 1486 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); 1487 // first_out_edges.set(this-> tail(e), f);1487 // first_out_edges.set(this->source(e), f); 1488 1488 // } 1489 1489 … … 1508 1508 // It e; first(e, v); return e; } 1509 1509 1510 // //Node head(const Edge& e) const { return gw.head(e); }1511 // //Node tail(const Edge& e) const { return gw.tail(e); }1510 // //Node target(const Edge& e) const { return gw.target(e); } 1511 // //Node source(const Edge& e) const { return gw.source(e); } 1512 1512 1513 1513 // //template<typename I> bool valid(const I& i) const … … 1526 1526 1527 1527 // //Node addNode() const { return gw.addNode(); } 1528 // //Edge addEdge(const Node& tail, const Node& head) const {1529 // // return gw.addEdge( tail, head); }1528 // //Edge addEdge(const Node& source, const Node& target) const { 1529 // // return gw.addEdge(source, target); } 1530 1530 1531 1531 // //template<typename I> void erase(const I& i) const { gw.erase(i); } … … 1670 1670 // It e; first(e, v); return e; } 1671 1671 1672 // Node head(const Edge& e) const { return gw.head(e); }1673 // Node tail(const Edge& e) const { return gw.tail(e); }1672 // Node target(const Edge& e) const { return gw.target(e); } 1673 // Node source(const Edge& e) const { return gw.source(e); } 1674 1674 1675 1675 // template<typename I> Node aNode(const I& e) const { … … 1685 1685 1686 1686 // Node addNode() { return gw.addNode(); } 1687 // Edge addEdge(const Node& tail, const Node& head) {1688 // return gw.addEdge( tail, head); }1687 // Edge addEdge(const Node& source, const Node& target) { 1688 // return gw.addEdge(source, target); } 1689 1689 1690 1690 // template<typename I> void erase(const I& i) { gw.erase(i); } -
src/work/marci/experiment/graph_wrapper_1.h
r921 r986 91 91 It e; this->first(e, v); return e; } 92 92 93 Node head(const Edge& e) const { return graph->head(e); }94 Node tail(const Edge& e) const { return graph->tail(e); }93 Node target(const Edge& e) const { return graph->target(e); } 94 Node source(const Edge& e) const { return graph->source(e); } 95 95 96 96 template<typename I> bool valid(const I& i) const { … … 109 109 110 110 Node addNode() const { return graph->addNode(); } 111 Edge addEdge(const Node& tail, const Node& head) const {112 return graph->addEdge( tail, head); }111 Edge addEdge(const Node& source, const Node& target) const { 112 return graph->addEdge(source, target); } 113 113 114 114 template<typename I> void erase(const I& i) const { graph->erase(i); } … … 236 236 It e; this->first(e, v); return e; } 237 237 238 Node head(const Edge& e) const { return graph->head(e); }239 Node tail(const Edge& e) const { return graph->tail(e); }238 Node target(const Edge& e) const { return graph->target(e); } 239 Node source(const Edge& e) const { return graph->source(e); } 240 240 241 241 template<typename I> bool valid(const I& i) const { … … 254 254 255 255 Node addNode() const { return graph->addNode(); } 256 Edge addEdge(const Node& tail, const Node& head) const {257 return graph->addEdge( tail, head); }256 Edge addEdge(const Node& source, const Node& target) const { 257 return graph->addEdge(source, target); } 258 258 259 259 template<typename I> void erase(const I& i) const { graph->erase(i); } … … 317 317 // It e; first(e, v); return e; } 318 318 319 // Node head(const Edge& e) const { return graph->tail(e); }320 // Node tail(const Edge& e) const { return graph->head(e); }319 // Node target(const Edge& e) const { return graph->source(e); } 320 // Node source(const Edge& e) const { return graph->target(e); } 321 321 322 322 // template<typename I> bool valid(const I& i) const … … 332 332 333 333 // Node addNode() const { return graph->addNode(); } 334 // Edge addEdge(const Node& tail, const Node& head) const {335 // return graph->addEdge( tail, head); }334 // Edge addEdge(const Node& source, const Node& target) const { 335 // return graph->addEdge(source, target); } 336 336 337 337 // int nodeNum() const { return graph->nodeNum(); } … … 379 379 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 380 380 381 Node head(const Edge& e) const382 { return GraphWrapper<Graph>:: tail(e); }383 Node tail(const Edge& e) const384 { return GraphWrapper<Graph>:: head(e); }381 Node target(const Edge& e) const 382 { return GraphWrapper<Graph>::source(e); } 383 Node source(const Edge& e) const 384 { return GraphWrapper<Graph>::target(e); } 385 385 }; 386 386 … … 512 512 // OutEdgeIt& next(OutEdgeIt& e) const { 513 513 // if (e.out_or_in) { 514 // Node n=gw. tail(e.out);514 // Node n=gw.source(e.out); 515 515 // gw.next(e.out); 516 516 // if (!gw.valid(e.out)) { … … 525 525 526 526 // Node aNode(const OutEdgeIt& e) const { 527 // if (e.out_or_in) return gw. tail(e); else return gw.head(e); }527 // if (e.out_or_in) return gw.source(e); else return gw.target(e); } 528 528 // Node bNode(const OutEdgeIt& e) const { 529 // if (e.out_or_in) return gw. head(e); else return gw.tail(e); }529 // if (e.out_or_in) return gw.target(e); else return gw.source(e); } 530 530 531 531 // typedef OutEdgeIt InEdgeIt; … … 545 545 // It e; first(e, v); return e; } 546 546 547 // Node head(const Edge& e) const { return gw.head(e); }548 // Node tail(const Edge& e) const { return gw.tail(e); }547 // Node target(const Edge& e) const { return gw.target(e); } 548 // Node source(const Edge& e) const { return gw.source(e); } 549 549 550 550 // template<typename I> bool valid(const I& i) const … … 564 564 // Node addNode() const { return gw.addNode(); } 565 565 // // FIXME: ez igy nem jo, mert nem 566 // // Edge addEdge(const Node& tail, const Node& head) const {567 // // return graph->addEdge( tail, head); }566 // // Edge addEdge(const Node& source, const Node& target) const { 567 // // return graph->addEdge(source, target); } 568 568 569 569 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 693 693 OutEdgeIt& next(OutEdgeIt& e) const { 694 694 if (e.out_or_in) { 695 Node n=graph-> tail(e.out);695 Node n=graph->source(e.out); 696 696 graph->next(e.out); 697 697 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } … … 703 703 704 704 EdgeIt& next(EdgeIt& e) const { 705 //NodeIt v= tail(e);705 //NodeIt v=source(e); 706 706 graph->next(e.out); 707 707 while (valid(e.v) && !graph->valid(e.out)) { … … 721 721 It e; this->first(e, v); return e; } 722 722 723 // Node head(const Edge& e) const { return gw.head(e); }724 // Node tail(const Edge& e) const { return gw.tail(e); }723 // Node target(const Edge& e) const { return gw.target(e); } 724 // Node source(const Edge& e) const { return gw.source(e); } 725 725 726 726 // template<typename I> bool valid(const I& i) const … … 736 736 737 737 Node aNode(const OutEdgeIt& e) const { 738 if (e.out_or_in) return graph-> tail(e); else return graph->head(e); }738 if (e.out_or_in) return graph->source(e); else return graph->target(e); } 739 739 Node bNode(const OutEdgeIt& e) const { 740 if (e.out_or_in) return graph-> head(e); else return graph->tail(e); }740 if (e.out_or_in) return graph->target(e); else return graph->source(e); } 741 741 742 742 // Node addNode() const { return gw.addNode(); } 743 743 744 744 // FIXME: ez igy nem jo, mert nem 745 // Edge addEdge(const Node& tail, const Node& head) const {746 // return graph->addEdge( tail, head); }745 // Edge addEdge(const Node& source, const Node& target) const { 746 // return graph->addEdge(source, target); } 747 747 748 748 // template<typename I> void erase(const I& i) const { gw.erase(i); } … … 808 808 // It e; first(e, v); return e; } 809 809 810 // Node head(const Edge& e) const { return graph->head(e); }811 // Node tail(const Edge& e) const { return graph->tail(e); }810 // Node target(const Edge& e) const { return graph->target(e); } 811 // Node source(const Edge& e) const { return graph->source(e); } 812 812 813 813 // template<typename I> Node aNode(const I& e) const { … … 823 823 824 824 // Node addNode() { return graph->addNode(); } 825 // Edge addEdge(const Node& tail, const Node& head) {826 // return graph->addEdge( tail, head); }825 // Edge addEdge(const Node& source, const Node& target) { 826 // return graph->addEdge(source, target); } 827 827 828 828 // template<typename I> void erase(const I& i) { graph->erase(i); } … … 1064 1064 } 1065 1065 1066 Node tail(Edge e) const {1066 Node source(Edge e) const { 1067 1067 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1068 Node head(Edge e) const {1068 Node target(Edge e) const { 1069 1069 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1070 1070 … … 1193 1193 OutEdgeIt f=e; 1194 1194 this->next(f); 1195 first_out_edges->set(this-> tail(e), f);1195 first_out_edges->set(this->source(e), f); 1196 1196 } 1197 1197 }; … … 1311 1311 // It e; first(e, v); return e; } 1312 1312 1313 // Node head(const Edge& e) const { return gw.head(e); }1314 // Node tail(const Edge& e) const { return gw.tail(e); }1313 // Node target(const Edge& e) const { return gw.target(e); } 1314 // Node source(const Edge& e) const { return gw.source(e); } 1315 1315 1316 1316 // template<typename I> Node aNode(const I& e) const { … … 1326 1326 1327 1327 // Node addNode() { return gw.addNode(); } 1328 // Edge addEdge(const Node& tail, const Node& head) {1329 // return gw.addEdge( tail, head); }1328 // Edge addEdge(const Node& source, const Node& target) { 1329 // return gw.addEdge(source, target); } 1330 1330 1331 1331 // template<typename I> void erase(const I& i) { gw.erase(i); } -
src/work/marci/experiment/graph_wrapper_st_ostream_op.h
r921 r986 167 167 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } 168 168 169 Node tail(const Edge& e) const {170 return Node(graph-> tail(static_cast<typename Graph::Edge>(e))); }171 Node head(const Edge& e) const {172 return Node(graph-> head(static_cast<typename Graph::Edge>(e))); }169 Node source(const Edge& e) const { 170 return Node(graph->source(static_cast<typename Graph::Edge>(e))); } 171 Node target(const Edge& e) const { 172 return Node(graph->target(static_cast<typename Graph::Edge>(e))); } 173 173 174 174 bool valid(const Node& n) const { … … 186 186 187 187 Node addNode() const { return Node(graph->addNode()); } 188 Edge addEdge(const Node& tail, const Node& head) const {189 return Edge(graph->addEdge( tail, head)); }188 Edge addEdge(const Node& source, const Node& target) const { 189 return Edge(graph->addEdge(source, target)); } 190 190 191 191 void erase(const Node& i) const { graph->erase(i); } … … 273 273 return Node(this->graph->bNode(e.e)); } 274 274 275 Node tail(const Edge& e) const {276 return GraphWrapper<Graph>:: head(e); }277 Node head(const Edge& e) const {278 return GraphWrapper<Graph>:: tail(e); }275 Node source(const Edge& e) const { 276 return GraphWrapper<Graph>::target(e); } 277 Node target(const Edge& e) const { 278 return GraphWrapper<Graph>::source(e); } 279 279 280 280 }; … … 490 490 OutEdgeIt& next(OutEdgeIt& e) const { 491 491 if (e.out_or_in) { 492 typename Graph::Node n=this->graph-> tail(e.out);492 typename Graph::Node n=this->graph->source(e.out); 493 493 this->graph->next(e.out); 494 494 if (!this->graph->valid(e.out)) { … … 507 507 508 508 Node aNode(const OutEdgeIt& e) const { 509 if (e.out_or_in) return this->graph-> tail(e); else510 return this->graph-> head(e); }509 if (e.out_or_in) return this->graph->source(e); else 510 return this->graph->target(e); } 511 511 Node bNode(const OutEdgeIt& e) const { 512 if (e.out_or_in) return this->graph-> head(e); else513 return this->graph-> tail(e); }512 if (e.out_or_in) return this->graph->target(e); else 513 return this->graph->source(e); } 514 514 }; 515 515 … … 725 725 } 726 726 727 Node tail(Edge e) const {728 return ((e.forward) ? this->graph-> tail(e) : this->graph->head(e)); }729 Node head(Edge e) const {730 return ((e.forward) ? this->graph-> head(e) : this->graph->tail(e)); }727 Node source(Edge e) const { 728 return ((e.forward) ? this->graph->source(e) : this->graph->target(e)); } 729 Node target(Edge e) const { 730 return ((e.forward) ? this->graph->target(e) : this->graph->source(e)); } 731 731 732 732 Node aNode(OutEdgeIt e) const { … … 914 914 OutEdgeIt f=e; 915 915 this->next(f); 916 first_out_edges->set(this-> tail(e), f.e);916 first_out_edges->set(this->source(e), f.e); 917 917 } 918 918 }; … … 1042 1042 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 1043 1043 1044 Node tail(const Edge& e) {1045 if (!(*(this->s_false_t_true_map))[this->graph-> tail(e)])1046 return Node(this->graph-> tail(e));1044 Node source(const Edge& e) { 1045 if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 1046 return Node(this->graph->source(e)); 1047 1047 else 1048 return Node(this->graph-> head(e));1049 } 1050 Node head(const Edge& e) {1051 if (!(*(this->s_false_t_true_map))[this->graph-> tail(e)])1052 return Node(this->graph-> head(e));1048 return Node(this->graph->target(e)); 1049 } 1050 Node target(const Edge& e) { 1051 if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 1052 return Node(this->graph->target(e)); 1053 1053 else 1054 return Node(this->graph-> tail(e));1054 return Node(this->graph->source(e)); 1055 1055 } 1056 1056 … … 1470 1470 } 1471 1471 1472 Node tail(const Edge& e) const {1472 Node source(const Edge& e) const { 1473 1473 switch (e.spec) { 1474 1474 case 0: 1475 return Node(this->graph-> tail(e));1475 return Node(this->graph->source(e)); 1476 1476 break; 1477 1477 case 1: … … 1484 1484 } 1485 1485 } 1486 Node head(const Edge& e) const {1486 Node target(const Edge& e) const { 1487 1487 switch (e.spec) { 1488 1488 case 0: 1489 return Node(this->graph-> head(e));1489 return Node(this->graph->target(e)); 1490 1490 break; 1491 1491 case 1: … … 1507 1507 } 1508 1508 1509 Node aNode(const OutEdgeIt& e) const { return tail(e); }1510 Node aNode(const InEdgeIt& e) const { return head(e); }1511 Node bNode(const OutEdgeIt& e) const { return head(e); }1512 Node bNode(const InEdgeIt& e) const { return tail(e); }1509 Node aNode(const OutEdgeIt& e) const { return source(e); } 1510 Node aNode(const InEdgeIt& e) const { return target(e); } 1511 Node bNode(const OutEdgeIt& e) const { return target(e); } 1512 Node bNode(const InEdgeIt& e) const { return source(e); } 1513 1513 1514 1514 void addNode() const { } … … 1516 1516 1517 1517 // Node addNode() const { return Node(this->graph->addNode()); } 1518 // Edge addEdge(const Node& tail, const Node& head) const {1519 // return Edge(this->graph->addEdge( tail, head)); }1518 // Edge addEdge(const Node& source, const Node& target) const { 1519 // return Edge(this->graph->addEdge(source, target)); } 1520 1520 1521 1521 // void erase(const Node& i) const { this->graph->erase(i); } -
src/work/marci/experiment/iterator_bfs_demo.cc
r921 r986 23 23 string get(typename Graph::Edge e) const { 24 24 return 25 (node_name_map.get(graph. tail(e))+"->"+node_name_map.get(graph.head(e)));25 (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); 26 26 } 27 27 }; -
src/work/marci/experiment/iterator_bfs_demo_1.cc
r921 r986 23 23 string get(typename Graph::Edge e) const { 24 24 return 25 (node_name_map.get(graph. tail(e))+"->"+node_name_map.get(graph.head(e)));25 (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e))); 26 26 } 27 27 }; -
src/work/marci/experiment/list_graph.h
r921 r986 123 123 //ListGraph* G; 124 124 int id; 125 node_item* _ tail;126 node_item* _ head;125 node_item* _source; 126 node_item* _target; 127 127 edge_item* _next_out; 128 128 edge_item* _prev_out; … … 150 150 } 151 151 152 edge_item* _add_edge(node_item* _ tail, node_item* _head) {152 edge_item* _add_edge(node_item* _source, node_item* _target) { 153 153 edge_item* e=new edge_item; 154 154 e->id=edge_id++; 155 e->_ tail=_tail;156 e->_ head=_head;157 158 e->_prev_out=_ tail->_last_out_edge;159 if (_ tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;160 _ tail->_last_out_edge=e;161 if (!_ tail->_first_out_edge) _tail->_first_out_edge=e;155 e->_source=_source; 156 e->_target=_target; 157 158 e->_prev_out=_source->_last_out_edge; 159 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; 160 _source->_last_out_edge=e; 161 if (!_source->_first_out_edge) _source->_first_out_edge=e; 162 162 e->_next_out=0; 163 163 164 e->_prev_in=_ head->_last_in_edge;165 if (_ head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;166 _ head->_last_in_edge=e;167 if (!_ head->_first_in_edge) { _head->_first_in_edge=e; }164 e->_prev_in=_target->_last_in_edge; 165 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; 166 _target->_last_in_edge=e; 167 if (!_target->_first_in_edge) { _target->_first_in_edge=e; } 168 168 e->_next_in=0; 169 169 … … 185 185 void _delete_edge(edge_item* e) { 186 186 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 187 (e->_ tail)->_last_out_edge=e->_prev_out;187 (e->_source)->_last_out_edge=e->_prev_out; 188 188 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 189 (e->_ tail)->_first_out_edge=e->_next_out;189 (e->_source)->_first_out_edge=e->_next_out; 190 190 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 191 (e->_ head)->_last_in_edge=e->_prev_in;191 (e->_target)->_last_in_edge=e->_prev_in; 192 192 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 193 (e->_ head)->_first_in_edge=e->_next_in;193 (e->_target)->_first_in_edge=e->_next_in; 194 194 195 195 delete e; … … 197 197 } 198 198 199 void _set_ tail(edge_item* e, node_item* _tail) {199 void _set_source(edge_item* e, node_item* _source) { 200 200 if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else 201 (e->_ tail)->_last_out_edge=e->_prev_out;201 (e->_source)->_last_out_edge=e->_prev_out; 202 202 if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else 203 (e->_ tail)->_first_out_edge=e->_next_out;204 205 e->_ tail=_tail;206 207 e->_prev_out=_ tail->_last_out_edge;208 if (_ tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;209 _ tail->_last_out_edge=e;210 if (!_ tail->_first_out_edge) _tail->_first_out_edge=e;203 (e->_source)->_first_out_edge=e->_next_out; 204 205 e->_source=_source; 206 207 e->_prev_out=_source->_last_out_edge; 208 if (_source->_last_out_edge) (_source->_last_out_edge)->_next_out=e; 209 _source->_last_out_edge=e; 210 if (!_source->_first_out_edge) _source->_first_out_edge=e; 211 211 e->_next_out=0; 212 212 } 213 213 214 void _set_ head(edge_item* e, node_item* _head) {214 void _set_target(edge_item* e, node_item* _target) { 215 215 if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else 216 (e->_ head)->_last_in_edge=e->_prev_in;216 (e->_target)->_last_in_edge=e->_prev_in; 217 217 if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else 218 (e->_ head)->_first_in_edge=e->_next_in;219 220 e->_ head=_head;221 222 e->_prev_in=_ head->_last_in_edge;223 if (_ head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;224 _ head->_last_in_edge=e;225 if (!_ head->_first_in_edge) { _head->_first_in_edge=e; }218 (e->_target)->_first_in_edge=e->_next_in; 219 220 e->_target=_target; 221 222 e->_prev_in=_target->_last_in_edge; 223 if (_target->_last_in_edge) (_target->_last_in_edge)->_next_in=e; 224 _target->_last_in_edge=e; 225 if (!_target->_first_in_edge) { _target->_first_in_edge=e; } 226 226 e->_next_in=0; 227 227 } … … 248 248 //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); } 249 249 //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); } 250 Node tail(Edge e) const { return e.tailNode(); }251 Node head(Edge e) const { return e.headNode(); }250 Node source(Edge e) const { return e.sourceNode(); } 251 Node target(Edge e) const { return e.targetNode(); } 252 252 253 253 Node aNode(const OutEdgeIt& e) const { return e.aNode(); } … … 278 278 SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const { 279 279 e=SymEdgeIt(*this, v); return e; } 280 //void get Tail(Node& n, const Edge& e) const { n=tail(e); }281 //void get Head(Node& n, const Edge& e) const { n=head(e); }280 //void getSource(Node& n, const Edge& e) const { n=source(e); } 281 //void getTarget(Node& n, const Edge& e) const { n=target(e); } 282 282 283 283 //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); } … … 346 346 } 347 347 348 void set Tail(Edge e, Node tail) {349 _set_ tail(e.edge, tail.node);350 } 351 352 void set Head(Edge e, Node head) {353 _set_ head(e.edge, head.node);348 void setSource(Edge e, Node source) { 349 _set_source(e.edge, source.node); 350 } 351 352 void setTarget(Edge e, Node target) { 353 _set_target(e.edge, target.node); 354 354 } 355 355 … … 360 360 } 361 361 friend std::ostream& operator<<(std::ostream& os, const Edge& i) { 362 os << "(" << i.edge->_ tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";362 os << "(" << i.edge->_source->id << "--" << i.edge->id << "->" << i.edge->_target->id << ")"; 363 363 return os; 364 364 } … … 427 427 friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; } 428 428 protected: 429 Node tailNode() const { return Node(edge->_tail); }430 Node headNode() const { return Node(edge->_head); }429 Node sourceNode() const { return Node(edge->_source); } 430 Node targetNode() const { return Node(edge->_target); } 431 431 public: 432 432 friend std::ostream& operator<<(std::ostream& os, const Edge& i); … … 448 448 EdgeIt(edge_item* _e) : Edge(_e) { } 449 449 EdgeIt& operator++() { 450 node_item* v=edge->_ tail;450 node_item* v=edge->_source; 451 451 edge=edge->_next_out; 452 452 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } … … 468 468 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } 469 469 protected: 470 Node aNode() const { return Node(edge->_ tail); }471 Node bNode() const { return Node(edge->_ head); }470 Node aNode() const { return Node(edge->_source); } 471 Node bNode() const { return Node(edge->_target); } 472 472 }; 473 473 … … 485 485 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } 486 486 protected: 487 Node aNode() const { return Node(edge->_ head); }488 Node bNode() const { return Node(edge->_ tail); }487 Node aNode() const { return Node(edge->_target); } 488 Node bNode() const { return Node(edge->_source); } 489 489 }; 490 490 … … 511 511 SymEdgeIt& operator++() { 512 512 if (out_or_in) { 513 node_item* v=edge->_ tail;513 node_item* v=edge->_source; 514 514 edge=edge->_next_out; 515 515 if (!edge) { out_or_in=0; edge=v->_first_in_edge; } … … 521 521 protected: 522 522 Node aNode() const { 523 return (out_or_in) ? Node(edge->_ tail) : Node(edge->_head); }523 return (out_or_in) ? Node(edge->_source) : Node(edge->_target); } 524 524 Node bNode() const { 525 return (out_or_in) ? Node(edge->_ head) : Node(edge->_tail); }525 return (out_or_in) ? Node(edge->_target) : Node(edge->_source); } 526 526 }; 527 527
Note: See TracChangeset
for help on using the changeset viewer.