Changeset 854:baf0b6e40211 in lemon-0.x
- Timestamp:
- 09/15/04 12:34:12 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1153
- Location:
- src
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/graph_wrapper.h
r849 r854 379 379 NodeIt(Invalid i) : Node(i) { } 380 380 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 381 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } 381 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 382 while (*static_cast<Node*>(this)!=INVALID && 383 !(*(gw->edge_filter_map))[*this]) 384 *(static_cast<Node*>(this))= 385 ++(typename Graph::NodeIt(*(gw->graph), *this)); 386 } 382 387 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 383 388 const Node& n) : … … 402 407 OutEdgeIt(Invalid i) : Edge(i) { } 403 408 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 404 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } 409 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 410 while (*static_cast<Edge*>(this)!=INVALID && 411 !(*(gw->edge_filter_map))[*this]) 412 *(static_cast<Edge*>(this))= 413 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); 414 } 405 415 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 406 416 const Edge& e) : … … 424 434 InEdgeIt(Invalid i) : Edge(i) { } 425 435 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 426 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } 436 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 437 while (*static_cast<Edge*>(this)!=INVALID && 438 !(*(gw->edge_filter_map))[*this]) 439 *(static_cast<Edge*>(this))= 440 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); 441 } 427 442 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 428 443 const Edge& e) : … … 446 461 EdgeIt(Invalid i) : Edge(i) { } 447 462 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 448 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } 463 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 464 while (*static_cast<Edge*>(this)!=INVALID && 465 !(*(gw->edge_filter_map))[*this]) 466 *(static_cast<Edge*>(this))= 467 ++(typename Graph::EdgeIt(*(gw->graph), *this)); 468 } 449 469 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 450 470 const Edge& e) : -
src/work/makefile
r773 r854 1 1 INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos} 2 CXXFLAGS = -g -O 3-W -Wall $(INCLUDEDIRS) -ansi -pedantic2 CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic 3 3 4 4 BINARIES ?= bin_heap_demo -
src/work/marci/augmenting_flow.h
r777 r854 1262 1262 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], 1263 1263 res_graph_to_F[res_graph.head(e)]); 1264 original_edge.update();1264 //original_edge.update(); 1265 1265 original_edge.set(f, e); 1266 residual_capacity.update();1266 //residual_capacity.update(); 1267 1267 residual_capacity.set(f, res_graph.resCap(e)); 1268 1268 } else { … … 1270 1270 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], 1271 1271 res_graph_to_F[res_graph.head(e)]); 1272 original_edge.update();1272 //original_edge.update(); 1273 1273 original_edge.set(f, e); 1274 residual_capacity.update();1274 //residual_capacity.update(); 1275 1275 residual_capacity.set(f, res_graph.resCap(e)); 1276 1276 } … … 1295 1295 while (!dfs.finished()) { 1296 1296 ++dfs; 1297 if ( F.valid(/*typename MG::OutEdgeIt*/(dfs))) {1297 if (typename MG::Edge(dfs)!=INVALID) { 1298 1298 if (dfs.isBNodeNewlyReached()) { 1299 1299 typename MG::Node v=F.tail(dfs); … … 1312 1312 1313 1313 } else { 1314 F.erase( /*typename MG::OutEdgeIt*/(dfs));1314 F.erase(typename MG::Edge(dfs)); 1315 1315 } 1316 1316 } -
src/work/marci/max_flow_demo.cc
r849 r854 4 4 // max_flow_demo < dimacs_max_flow_file 5 5 6 7 6 #include <iostream> 8 7 #include <fstream> 9 8 10 #include <sage_graph.h>11 9 #include <hugo/smart_graph.h> 10 #include <hugo/list_graph.h> 12 11 #include <hugo/dimacs.h> 13 12 #include <hugo/time_measure.h> 14 //#include <graph_wrapper.h>15 13 #include <hugo/preflow.h> 16 14 #include <augmenting_flow.h> 17 //#include <preflow_res.h>18 #include <for_each_macros.h>19 15 #include <graph_concept.h> 20 16 … … 23 19 int main(int, char **) { 24 20 25 typedef SageGraph MutableGraph; 26 27 //typedef FullFeatureGraphConcept Graph; 28 //typedef SmartGraph Graph; 29 typedef SageGraph Graph; 21 typedef ListGraph MutableGraph; 22 typedef SmartGraph Graph; 30 23 typedef Graph::Node Node; 31 24 typedef Graph::EdgeIt EdgeIt; … … 54 47 max_flow_test.minCut(cut); 55 48 56 FOR_EACH_LOC(Graph::EdgeIt, e, g) {49 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 57 50 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 58 51 std::cout << "Slackness does not hold!" << std::endl; … … 64 57 { 65 58 std::cout << "preflow ..." << std::endl; 66 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);59 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 67 60 ts.reset(); 68 max_flow_test. preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);61 max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); 69 62 std::cout << "elapsed time: " << ts << std::endl; 70 63 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 71 64 72 FOR_EACH_LOC(Graph::EdgeIt, e, g) {65 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 73 66 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 74 67 std::cout << "Slackness does not hold!" << std::endl; … … 89 82 { 90 83 std::cout << "physical blocking flow augmentation ..." << std::endl; 91 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);84 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 92 85 ts.reset(); 93 86 int i=0; … … 97 90 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 98 91 99 FOR_EACH_LOC(Graph::EdgeIt, e, g) {92 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 100 93 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 101 94 std::cout << "Slackness does not hold!" << std::endl; … … 107 100 { 108 101 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; 109 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);102 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 110 103 ts.reset(); 111 104 int i=0; … … 115 108 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 116 109 117 FOR_EACH_LOC(Graph::EdgeIt, e, g) {110 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 118 111 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 119 112 std::cout << "Slackness does not hold!" << std::endl; … … 125 118 { 126 119 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; 127 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);120 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 128 121 ts.reset(); 129 122 int i=0; … … 133 126 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 134 127 135 FOR_EACH_LOC(Graph::EdgeIt, e, g) {128 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 136 129 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 137 130 std::cout << "Slackness does not hold!" << std::endl; … … 143 136 { 144 137 std::cout << "on-the-fly shortest path augmentation ..." << std::endl; 145 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);138 for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0); 146 139 ts.reset(); 147 140 int i=0; … … 151 144 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; 152 145 153 FOR_EACH_LOC(Graph::EdgeIt, e, g) {146 for(Graph::EdgeIt e(g); e!=INVALID; ++e) { 154 147 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 155 148 std::cout << "Slackness does not hold!" << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.