Changeset 646:bd7a69231cf8 in lemon0.x for src/work/marci/max_flow_demo.cc
 Timestamp:
 05/19/04 18:06:57 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@846
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/max_flow_demo.cc
r642 r646 73 73 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 74 74 max_flow_test(g, s, t, cap, flow); 75 Graph::NodeMap<bool> cut(g); 75 76 76 77 { … … 80 81 std::cout << "elapsed time: " << ts << std::endl; 81 82 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 83 max_flow_test.actMinCut(cut); 84 85 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 86 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 87 std::cout << "Slackness does not hold!" << std::endl; 88 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 89 std::cout << "Slackness does not hold!" << std::endl; 90 } 82 91 } 83 92 … … 89 98 std::cout << "elapsed time: " << ts << std::endl; 90 99 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 100 101 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 102 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 103 std::cout << "Slackness does not hold!" << std::endl; 104 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 105 std::cout << "Slackness does not hold!" << std::endl; 106 } 91 107 } 92 108 … … 109 125 std::cout << "number of augmentation phases: " << i << std::endl; 110 126 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 127 128 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 129 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 130 std::cout << "Slackness does not hold!" << std::endl; 131 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 132 std::cout << "Slackness does not hold!" << std::endl; 133 } 111 134 } 112 135 … … 131 154 std::cout << "number of augmentation phases: " << i << std::endl; 132 155 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 156 157 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 158 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 159 std::cout << "Slackness does not hold!" << std::endl; 160 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 161 std::cout << "Slackness does not hold!" << std::endl; 162 } 133 163 } 134 164 … … 142 172 std::cout << "number of augmentation phases: " << i << std::endl; 143 173 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 144 } 145 174 175 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 176 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 177 std::cout << "Slackness does not hold!" << std::endl; 178 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 179 std::cout << "Slackness does not hold!" << std::endl; 180 } 181 } 182 183 { 184 std::cout << "onthefly shortest path augmentation ..." << std::endl; 185 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); 186 ts.reset(); 187 int i=0; 188 while (max_flow_test.augmentOnShortestPath2()) { ++i; } 189 std::cout << "elapsed time: " << ts << std::endl; 190 std::cout << "number of augmentation phases: " << i << std::endl; 191 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 192 193 FOR_EACH_LOC(Graph::EdgeIt, e, g) { 194 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 195 std::cout << "Slackness does not hold!" << std::endl; 196 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 197 std::cout << "Slackness does not hold!" << std::endl; 198 } 199 } 146 200 147 201 return 0;
Note: See TracChangeset
for help on using the changeset viewer.