Changeset 499:767f3da8ce0e in lemon0.x for src/work/marci/bipartite_matching_try_2.cc
 Timestamp:
 04/30/04 19:10:01 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@659
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bipartite_matching_try_2.cc
r498 r499 11 11 #include <for_each_macros.h> 12 12 #include <bfs_iterator.h> 13 #include <graph_wrapper.h>14 13 #include <bipartite_graph_wrapper.h> 15 14 #include <maps.h> … … 41 40 42 41 int main() { 43 typedef UndirListGraph Graph; 42 //typedef UndirListGraph Graph; 43 typedef BipartiteGraph<ListGraph> Graph; 44 44 45 typedef Graph::Node Node; 45 46 typedef Graph::NodeIt NodeIt; … … 64 65 65 66 66 for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode( ));67 for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode( ));67 for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false)); 68 for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true)); 68 69 69 70 random_init(); … … 72 73 } 73 74 74 Graph::NodeMap<int> ref_map(g, 1); 75 std::cout << "Edges of the bipartite graph:" << std::endl; 76 FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; 77 std::cout << std::endl; 75 78 76 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);77 for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);78 for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);79 typedef stGraphWrapper<Graph> stGW; 80 stGW stgw(g); 81 ConstMap<stGW::Edge, int> const1map(1); 79 82 80 // Graph::Node u;81 // std::cout << "These nodes will be in S:\n";82 // //FIXME azert kellene ++, es invalid vizsgalat ubol, hogy ezt le lehessen83 // //irni 1etlen FOR_EACHcsel.84 // for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))85 // std::cout << u << " ";86 // std::cout << "\n";87 // std::cout << "These nodes will be in T:\n";88 // for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))89 // std::cout << u << " ";90 // std::cout << "\n";91 83 92 typedef BipartiteGraphWrapper<Graph> BGW;93 BGW bgw(g, bipartite_map);94 95 // std::cout << "Nodes by NodeIt:\n";96 // FOR_EACH_LOC(BGW::NodeIt, n, bgw) {97 // std::cout << n << " ";98 // }99 // std::cout << "\n";100 // std::cout << "Nodes in S by ClassNodeIt:\n";101 // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {102 // std::cout << n << " ";103 // }104 // std::cout << "\n";105 // std::cout << "Nodes in T by ClassNodeIt:\n";106 // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {107 // std::cout << n << " ";108 // }109 // std::cout << "\n";110 // std::cout << "Edges of the bipartite graph:\n";111 // FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {112 // std::cout << bgw.tail(e) << ">" << bgw.head(e) << std::endl;113 // }114 115 // BGW::NodeMap<int> dbyj(bgw);116 // BGW::EdgeMap<int> dbyxcj(bgw);117 118 typedef stGraphWrapper<BGW> stGW;119 stGW stgw(bgw);120 ConstMap<stGW::Edge, int> const1map(1);121 // stGW::NodeMap<int> ize(stgw);122 123 // BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);124 // Graph::NodeIt si;125 // Graph::Node s;126 // s=g.first(si);127 // bfs.pushAndSetReached(BGW::Node(s));128 // while (!bfs.finished()) { ++bfs; }129 130 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) {131 // std::cout << "outedges of " << n << ":\n";132 // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {133 // std::cout << " " << e << "\n";134 // std::cout << " aNode: " << stgw.aNode(e) << "\n";135 // std::cout << " bNode: " << stgw.bNode(e) << "\n";136 // }137 // std::cout << "inedges of " << n << ":\n";138 // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {139 // std::cout << " " << e << "\n";140 // std::cout << " aNode: " << stgw.aNode(e) << "\n";141 // std::cout << " bNode: " << stgw.bNode(e) << "\n";142 // }143 // }144 // std::cout << "Edges of the stGraphWrapper:\n";145 // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {146 // std::cout << " " << n << "\n";147 // }148 149 // stGW::NodeMap<bool> b(stgw);150 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) {151 // std::cout << n << ": " << b[n] <<"\n";152 // }153 154 // std::cout << "Bfs from s: \n";155 // BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);156 // bfs_stgw.pushAndSetReached(stgw.S_NODE);157 // while (!bfs_stgw.finished()) {158 // std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";159 // ++bfs_stgw;160 // }161 84 162 85 163 86 Timer ts; 164 87 ts.reset(); 165 stGW::EdgeMap<int> max_flow(stgw);88 stGW::EdgeMap<int> flow(stgw); 166 89 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 167 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);90 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 168 91 // while (max_flow_test.augmentOnShortestPath()) { } 169 92 typedef ListGraph MutableGraph; … … 174 97 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; 175 98 std::cout << "elapsed time: " << ts << std::endl; 176 //FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {177 // std::cout << e << ": " << max_flow[e] << "\n";178 //}179 // std::cout << "\n";99 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 100 if (flow[e]) std::cout << e << std::endl; 101 } 102 std::cout << std::endl; 180 103 181 104 ts.reset();
Note: See TracChangeset
for help on using the changeset viewer.