Changeset 769:eb61fbc64c16 in lemon-0.x for src/work/marci/leda
- Timestamp:
- 08/23/04 13:26:09 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1032
- Location:
- src/work/marci/leda
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/leda/bipartite_matching_leda.cc
r648 r769 15 15 //#include <dimacs.h> 16 16 #include <hugo/time_measure.h> 17 #include < hugo/for_each_macros.h>17 #include <for_each_macros.h> 18 18 #include <hugo/graph_wrapper.h> 19 19 #include <bipartite_graph_wrapper.h> 20 20 #include <hugo/maps.h> 21 #include < max_flow.h>21 #include <hugo/max_flow.h> 22 22 23 23 /** … … 96 96 BGW::EdgeMap<int> dbyxcj(bgw); 97 97 98 typedef st GraphWrapper<BGW> stGW;98 typedef stBipartiteGraphWrapper<BGW> stGW; 99 99 stGW stgw(bgw); 100 100 ConstMap<stGW::Edge, int> const1map(1); … … 110 110 typedef SageGraph MutableGraph; 111 111 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 112 while (max_flow_test.augmentOnBlockingFlow2()) { 113 std::cout << max_flow_test.flowValue() << std::endl; 114 } 112 // while (max_flow_test.augmentOnBlockingFlow2()) { 113 // std::cout << max_flow_test.flowValue() << std::endl; 114 // } 115 max_flow_test.run(); 115 116 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; 116 117 std::cout << "elapsed time: " << ts << std::endl; -
src/work/marci/leda/bipartite_matching_leda_gen.cc
r768 r769 15 15 //#include <dimacs.h> 16 16 #include <hugo/time_measure.h> 17 #include < hugo/for_each_macros.h>17 #include <for_each_macros.h> 18 18 #include <hugo/graph_wrapper.h> 19 19 #include <bipartite_graph_wrapper.h> 20 20 #include <hugo/maps.h> 21 #include <max_flow.h> 21 #include <hugo/max_flow.h> 22 #include <augmenting_flow.h> 22 23 23 24 /** … … 126 127 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); 127 128 typedef SageGraph MutableGraph; 128 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { } 129 AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 130 max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); 131 while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { } 129 132 std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 130 133 << std::endl << "Matching size: " 131 << max_flow_test .flowValue() << std::endl;134 << max_flow_test_1.flowValue() << std::endl; 132 135 std::cout << "elapsed time: " << ts << std::endl; 133 136 -
src/work/marci/leda/comparison.cc
r768 r769 15 15 //#include <dimacs.h> 16 16 #include <hugo/time_measure.h> 17 #include < hugo/for_each_macros.h>17 #include <for_each_macros.h> 18 18 #include <hugo/graph_wrapper.h> 19 19 #include <bipartite_graph_wrapper.h> 20 20 #include <hugo/maps.h> 21 #include < max_flow.h>21 #include <hugo/max_flow.h> 22 22 23 /** 24 * Inicializalja a veletlenszamgeneratort. 25 * Figyelem, ez nem jo igazi random szamokhoz, 26 * erre ne bizzad a titkaidat! 27 */ 28 void random_init() 29 { 30 unsigned int seed = getpid(); 31 seed |= seed << 15; 32 seed ^= time(0); 33 34 srand(seed); 35 } 36 37 /** 38 * Egy veletlen int-et ad vissza 0 es m-1 kozott. 39 */ 40 int random(int m) 41 { 42 return int( double(m) * rand() / (RAND_MAX + 1.0) ); 43 } 23 using std::cout; 24 using std::endl; 44 25 45 26 using namespace hugo; … … 66 47 67 48 int a; 68 std::cout << "number of nodes in the first color class=";49 cout << "number of nodes in the first color class="; 69 50 std::cin >> a; 70 51 int b; 71 std::cout << "number of nodes in the second color class=";52 cout << "number of nodes in the second color class="; 72 53 std::cin >> b; 73 54 int m; 74 std::cout << "number of edges=";55 cout << "number of edges="; 75 56 std::cin >> m; 76 57 int k; 77 std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";78 std::cout << "number of groups in LEDA random group graph=";58 cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n"; 59 cout << "number of groups in LEDA random group graph="; 79 60 std::cin >> k; 80 std::cout << std::endl;61 cout << endl; 81 62 82 63 leda_list<leda_node> lS; … … 110 91 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); 111 92 max_flow_test.run(); 112 std::cout << "HUGO max matching algorithm based on preflow." << std::endl93 cout << "HUGO max matching algorithm based on preflow." << endl 113 94 << "Size of matching: " 114 << max_flow_test.flowValue() << std::endl;115 std::cout << "elapsed time: " << ts << std::endl << std::endl;95 << max_flow_test.flowValue() << endl; 96 cout << "elapsed time: " << ts << endl << endl; 116 97 117 98 ts.reset(); 118 99 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg); 119 std::cout << "LEDA max matching algorithm." << std::endl100 cout << "LEDA max matching algorithm." << endl 120 101 << "Size of matching: " 121 << ml.size() << std::endl;122 std::cout << "elapsed time: " << ts << std::endl << std::endl;102 << ml.size() << endl; 103 cout << "elapsed time: " << ts << endl << endl; 123 104 124 105 // ts.reset(); … … 126 107 // typedef SageGraph MutableGraph; 127 108 // 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;131 // std::cout << "elapsed time: " << ts << std::endl << std::endl;109 // cout << "HUGO max matching algorithm based on blocking flow augmentation." 110 // << endl << "Matching size: " 111 // << max_flow_test.flowValue() << endl; 112 // cout << "elapsed time: " << ts << endl << endl; 132 113 133 114 { … … 160 141 max_flow_test(hg, s, t, cm, flow); 161 142 max_flow_test.run(); 162 std::cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."163 << std::endl143 cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow." 144 << endl 164 145 << "Size of matching: " 165 << max_flow_test.flowValue() << std::endl;166 std::cout << "elapsed time: " << ts << std::endl << std::endl;146 << max_flow_test.flowValue() << endl; 147 cout << "elapsed time: " << ts << endl << endl; 167 148 } 168 149
Note: See TracChangeset
for help on using the changeset viewer.