Changeset 482:dce64ce044d6 in lemon0.x for src/work/marci/leda
 Timestamp:
 04/29/04 18:59:00 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@639
 Location:
 src/work/marci/leda
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/leda/bipartite_matching_leda.cc
r459 r482 19 19 #include <graph_wrapper.h> 20 20 #include <maps.h> 21 #include <edmonds_karp.h> 22 #include <preflow.h> 21 #include <max_flow.h> 23 22 24 23 /** … … 102 101 103 102 Timer ts; 103 stGW::EdgeMap<int> flow(stgw); 104 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 105 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 106 104 107 ts.reset(); 105 stGW::EdgeMap<int> max_flow(stgw); 106 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 107 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow); 108 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); 108 109 // while (max_flow_test.augmentOnShortestPath()) { } 109 110 typedef ListGraph MutableGraph; … … 114 115 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; 115 116 std::cout << "elapsed time: " << ts << std::endl; 116 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {117 // std::cout << e << ": " << max_flow[e] << "\n";118 // }119 // std::cout << "\n";120 117 121 118 ts.reset(); 122 stGW::EdgeMap<int> pre_flow(stgw); 123 Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 124 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/); 125 pre_flow_test.run(); 119 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); 120 max_flow_test.run(); 126 121 std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl; 127 122 std::cout << "elapsed time: " << ts << std::endl; 128 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {129 // std::cout << e << ": " << pre_flow[e] << "\n";130 // }131 // std::cout << "\n";132 123 133 124 ts.reset(); 134 125 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); 135 // stGW::EdgeMap<int> pre_flow(stgw);136 //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >137 // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);138 //pre_flow_test.run();139 126 std::cout << "leda matching value: " << ml.size() << std::endl; 140 127 std::cout << "elapsed time: " << ts << std::endl; 141 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {142 // std::cout << e << ": " << pre_flow[e] << "\n";143 // }144 // std::cout << "\n";145 128 146 129 return 0; 
src/work/marci/leda/bipartite_matching_leda_gen.cc
r459 r482 16 16 #include <time_measure.h> 17 17 #include <for_each_macros.h> 18 //#include <bfs_iterator.h>19 18 #include <graph_wrapper.h> 20 19 #include <maps.h> 21 #include <edmonds_karp.h> 22 #include <preflow.h> 20 #include <max_flow.h> 23 21 24 22 /** … … 79 77 std::cout << "number of groups in LEDA random group graph="; 80 78 std::cin >> k; 81 79 std::cout << std::endl; 80 82 81 leda_list<leda_node> lS; 83 82 leda_list<leda_node> lT; 84 83 random_bigraph(lg, a, b, m, lS, lT, k); 85 84 86 // for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());87 // for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());85 Graph::NodeMap<int> ref_map(g, 1); 86 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); 88 87 89 // random_init(); 90 // for(int i=0; i<m; ++i) { 91 // g.addEdge(s_nodes[random(a)], t_nodes[random(b)]); 92 // } 93 94 Graph::NodeMap<int> ref_map(g, 1); 95 96 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); 97 // for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false); 98 // for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true); 88 //generating leda random group graph 99 89 leda_node ln; 100 90 forall(ln, lS) bipartite_map.insert(ln, false); 101 91 forall(ln, lT) bipartite_map.insert(ln, true); 102 92 93 //making bipartite graph 103 94 typedef BipartiteGraphWrapper<Graph> BGW; 104 95 BGW bgw(g, bipartite_map); 105 96 106 // BGW::NodeMap<int> dbyj(bgw);107 // BGW::EdgeMap<int> dbyxcj(bgw);108 97 98 //stwrapper 109 99 typedef stGraphWrapper<BGW> stGW; 110 100 stGW stgw(bgw); … … 113 103 114 104 Timer ts; 105 106 ts.reset(); 115 107 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); 116 ts.reset(); 117 // stGW::EdgeMap<int> pre_flow(stgw); 118 Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 119 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); 120 pre_flow_test.run(); 121 std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl; 122 std::cout << "elapsed time: " << ts << std::endl; 123 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 124 // std::cout << e << ": " << pre_flow[e] << "\n"; 125 // } 126 std::cout << "\n"; 108 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 109 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); 110 max_flow_test.run(); 111 std::cout << "HUGO max matching algorithm based on preflow." << std::endl 112 << "Size of matching: " 113 << max_flow_test.flowValue() << std::endl; 114 std::cout << "elapsed time: " << ts << std::endl << std::endl; 127 115 128 116 ts.reset(); 129 117 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); 130 // stGW::EdgeMap<int> pre_flow(stgw); 131 //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 132 // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true); 133 //pre_flow_test.run(); 134 std::cout << "LEDA matching value: " << ml.size() << std::endl; 118 std::cout << "LEDA max matching algorithm." << std::endl 119 << "Size of matching: " 120 << ml.size() << std::endl; 135 121 std::cout << "elapsed time: " << ts << std::endl; 136 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {137 // std::cout << e << ": " << pre_flow[e] << "\n";138 // }139 122 std::cout << "\n"; 140 123 124 ts.reset(); 141 125 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); 142 ts.reset();143 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >144 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);145 // while (max_flow_test.augmentOnShortestPath()) { }146 126 typedef ListGraph MutableGraph; 147 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 148 while (max_flow_test.augmentOnBlockingFlow2()) { 149 std::cout << max_flow_test.flowValue() << std::endl; 150 } 151 std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl; 127 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } 128 std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 129 << std::endl << "Matching size: " 130 << max_flow_test.flowValue() << std::endl; 152 131 std::cout << "elapsed time: " << ts << std::endl; 153 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {154 // std::cout << e << ": " << max_flow[e] << "\n";155 // }156 // std::cout << "\n";157 132 158 133 return 0; 
src/work/marci/leda/leda_graph_wrapper.h
r473 r482 47 47 Graph* _graph; 48 48 LedaGraphWrapper() : _graph(0) { } 49 setGraph(Graph& __graph) { _graph=&__graph; }49 void setGraph(Graph& __graph) { _graph=&__graph; } 50 50 public: 51 51
Note: See TracChangeset
for help on using the changeset viewer.