Changeset 512:d5fe2f3f95fc in lemon0.x
 Timestamp:
 05/03/04 13:43:27 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@672
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bipartite_matching_try_3.cc
r510 r512 44 44 typename EdgeFlow, typename NodeFlow> 45 45 class MaxMatching { 46 // : public MaxFlow<stGraphWrapper<Graph>,47 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {48 // typedef MaxFlow<stGraphWrapper<Graph>,49 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,50 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >51 // Parent;52 46 protected: 53 47 // EdgeCap* edge_cap; … … 59 53 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 60 54 CapMap cap; 55 NodeFlow* node_flow; 61 56 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; 62 57 FlowMap flow; … … 69 64 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : 70 65 stgw(_g), 71 cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow), 66 cap(_edge_cap, _node_cap), 67 node_flow(0), 68 flow(_edge_flow, _node_flow), 72 69 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } 70 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, 71 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : 72 stgw(_g), 73 cap(_edge_cap, _node_cap), 74 node_flow(new NodeFlow(_g)), 75 flow(_edge_flow, *node_flow), 76 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } 77 ~MaxMatching() { if (node_flow) delete node_flow; } 73 78 void run() { mf.run(); } 74 79 int matchingValue() { return mf.flowValue(); } … … 131 136 } 132 137 133 std::cout << "Edges of the bipartite graph:" << std::endl;134 FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";135 std::cout << std::endl;136 137 std::cout << "Nodes:" << std::endl;138 FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";139 std::cout << std::endl;140 std::cout << "Nodes in T:" << std::endl;141 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";142 std::cout << std::endl;143 std::cout << "Nodes in S:" << std::endl;144 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";145 std::cout << std::endl;146 147 std::cout << "Erasing the first node..." << std::endl;148 NodeIt n;149 g.first(n);150 g.erase(n);151 std::cout << "Nodes of the bipartite graph:" << std::endl;152 FOR_EACH_GLOB(n, g) std::cout << n << " ";153 std::cout << std::endl;154 155 std::cout << "Nodes in T:" << std::endl;156 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";157 std::cout << std::endl;158 std::cout << "Nodes in S:" << std::endl;159 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";160 std::cout << std::endl;138 // std::cout << "Edges of the bipartite graph:" << std::endl; 139 // FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; 140 // std::cout << std::endl; 141 142 // std::cout << "Nodes:" << std::endl; 143 // FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " "; 144 // std::cout << std::endl; 145 // std::cout << "Nodes in T:" << std::endl; 146 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; 147 // std::cout << std::endl; 148 // std::cout << "Nodes in S:" << std::endl; 149 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; 150 // std::cout << std::endl; 151 152 // std::cout << "Erasing the first node..." << std::endl; 153 // NodeIt n; 154 // g.first(n); 155 // g.erase(n); 156 // std::cout << "Nodes of the bipartite graph:" << std::endl; 157 // FOR_EACH_GLOB(n, g) std::cout << n << " "; 158 // std::cout << std::endl; 159 160 // std::cout << "Nodes in T:" << std::endl; 161 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; 162 // std::cout << std::endl; 163 // std::cout << "Nodes in S:" << std::endl; 164 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; 165 // std::cout << std::endl; 161 166 162 167 typedef stGraphWrapper<Graph> stGW; … … 178 183 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; 179 184 std::cout << "elapsed time: " << ts << std::endl; 180 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {181 if (flow[e]) std::cout << e << std::endl;182 }185 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 186 // if (flow[e]) std::cout << e << std::endl; 187 // } 183 188 std::cout << std::endl; 184 189 … … 230 235 // } 231 236 std::cout << std::endl; 237 238 ts.reset(); 239 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); 240 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); 241 MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, 242 Graph::EdgeMap<int>, Graph::NodeMap<int> > 243 matching_test_1(g, ge1, gn1, gef/*, gnf*/); 244 matching_test_1.run(); 245 246 std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl; 247 std::cout << "elapsed time: " << ts << std::endl; 248 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { 249 // if (gef[e]) std::cout << e << std::endl; 250 // } 251 std::cout << std::endl; 252 232 253 return 0; 233 254 }
Note: See TracChangeset
for help on using the changeset viewer.