1.1 --- a/src/work/marci/leda/bipartite_matching_leda.cc Mon Aug 23 11:06:00 2004 +0000
1.2 +++ b/src/work/marci/leda/bipartite_matching_leda.cc Mon Aug 23 11:26:09 2004 +0000
1.3 @@ -14,11 +14,11 @@
1.4 //#include <smart_graph.h>
1.5 //#include <dimacs.h>
1.6 #include <hugo/time_measure.h>
1.7 -#include <hugo/for_each_macros.h>
1.8 +#include <for_each_macros.h>
1.9 #include <hugo/graph_wrapper.h>
1.10 #include <bipartite_graph_wrapper.h>
1.11 #include <hugo/maps.h>
1.12 -#include <max_flow.h>
1.13 +#include <hugo/max_flow.h>
1.14
1.15 /**
1.16 * Inicializalja a veletlenszamgeneratort.
1.17 @@ -95,7 +95,7 @@
1.18 BGW::NodeMap<int> dbyj(bgw);
1.19 BGW::EdgeMap<int> dbyxcj(bgw);
1.20
1.21 - typedef stGraphWrapper<BGW> stGW;
1.22 + typedef stBipartiteGraphWrapper<BGW> stGW;
1.23 stGW stgw(bgw);
1.24 ConstMap<stGW::Edge, int> const1map(1);
1.25
1.26 @@ -109,9 +109,10 @@
1.27 // while (max_flow_test.augmentOnShortestPath()) { }
1.28 typedef SageGraph MutableGraph;
1.29 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.30 - while (max_flow_test.augmentOnBlockingFlow2()) {
1.31 - std::cout << max_flow_test.flowValue() << std::endl;
1.32 - }
1.33 +// while (max_flow_test.augmentOnBlockingFlow2()) {
1.34 +// std::cout << max_flow_test.flowValue() << std::endl;
1.35 +// }
1.36 + max_flow_test.run();
1.37 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
1.38 std::cout << "elapsed time: " << ts << std::endl;
1.39
2.1 --- a/src/work/marci/leda/bipartite_matching_leda_gen.cc Mon Aug 23 11:06:00 2004 +0000
2.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc Mon Aug 23 11:26:09 2004 +0000
2.3 @@ -14,11 +14,12 @@
2.4 //#include <smart_graph.h>
2.5 //#include <dimacs.h>
2.6 #include <hugo/time_measure.h>
2.7 -#include <hugo/for_each_macros.h>
2.8 +#include <for_each_macros.h>
2.9 #include <hugo/graph_wrapper.h>
2.10 #include <bipartite_graph_wrapper.h>
2.11 #include <hugo/maps.h>
2.12 -#include <max_flow.h>
2.13 +#include <hugo/max_flow.h>
2.14 +#include <augmenting_flow.h>
2.15
2.16 /**
2.17 * Inicializalja a veletlenszamgeneratort.
2.18 @@ -125,10 +126,12 @@
2.19 ts.reset();
2.20 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
2.21 typedef SageGraph MutableGraph;
2.22 - while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
2.23 + AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
2.24 + max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
2.25 + while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
2.26 std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
2.27 << std::endl << "Matching size: "
2.28 - << max_flow_test.flowValue() << std::endl;
2.29 + << max_flow_test_1.flowValue() << std::endl;
2.30 std::cout << "elapsed time: " << ts << std::endl;
2.31
2.32 return 0;
3.1 --- a/src/work/marci/leda/comparison.cc Mon Aug 23 11:06:00 2004 +0000
3.2 +++ b/src/work/marci/leda/comparison.cc Mon Aug 23 11:26:09 2004 +0000
3.3 @@ -14,33 +14,14 @@
3.4 //#include <smart_graph.h>
3.5 //#include <dimacs.h>
3.6 #include <hugo/time_measure.h>
3.7 -#include <hugo/for_each_macros.h>
3.8 +#include <for_each_macros.h>
3.9 #include <hugo/graph_wrapper.h>
3.10 #include <bipartite_graph_wrapper.h>
3.11 #include <hugo/maps.h>
3.12 -#include <max_flow.h>
3.13 +#include <hugo/max_flow.h>
3.14
3.15 -/**
3.16 - * Inicializalja a veletlenszamgeneratort.
3.17 - * Figyelem, ez nem jo igazi random szamokhoz,
3.18 - * erre ne bizzad a titkaidat!
3.19 - */
3.20 -void random_init()
3.21 -{
3.22 - unsigned int seed = getpid();
3.23 - seed |= seed << 15;
3.24 - seed ^= time(0);
3.25 -
3.26 - srand(seed);
3.27 -}
3.28 -
3.29 -/**
3.30 - * Egy veletlen int-et ad vissza 0 es m-1 kozott.
3.31 - */
3.32 -int random(int m)
3.33 -{
3.34 - return int( double(m) * rand() / (RAND_MAX + 1.0) );
3.35 -}
3.36 +using std::cout;
3.37 +using std::endl;
3.38
3.39 using namespace hugo;
3.40
3.41 @@ -65,19 +46,19 @@
3.42 std::vector<Graph::Node> t_nodes;
3.43
3.44 int a;
3.45 - std::cout << "number of nodes in the first color class=";
3.46 + cout << "number of nodes in the first color class=";
3.47 std::cin >> a;
3.48 int b;
3.49 - std::cout << "number of nodes in the second color class=";
3.50 + cout << "number of nodes in the second color class=";
3.51 std::cin >> b;
3.52 int m;
3.53 - std::cout << "number of edges=";
3.54 + cout << "number of edges=";
3.55 std::cin >> m;
3.56 int k;
3.57 - 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";
3.58 - std::cout << "number of groups in LEDA random group graph=";
3.59 + 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";
3.60 + cout << "number of groups in LEDA random group graph=";
3.61 std::cin >> k;
3.62 - std::cout << std::endl;
3.63 + cout << endl;
3.64
3.65 leda_list<leda_node> lS;
3.66 leda_list<leda_node> lT;
3.67 @@ -109,26 +90,26 @@
3.68 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
3.69 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
3.70 max_flow_test.run();
3.71 - std::cout << "HUGO max matching algorithm based on preflow." << std::endl
3.72 + cout << "HUGO max matching algorithm based on preflow." << endl
3.73 << "Size of matching: "
3.74 - << max_flow_test.flowValue() << std::endl;
3.75 - std::cout << "elapsed time: " << ts << std::endl << std::endl;
3.76 + << max_flow_test.flowValue() << endl;
3.77 + cout << "elapsed time: " << ts << endl << endl;
3.78
3.79 ts.reset();
3.80 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
3.81 - std::cout << "LEDA max matching algorithm." << std::endl
3.82 + cout << "LEDA max matching algorithm." << endl
3.83 << "Size of matching: "
3.84 - << ml.size() << std::endl;
3.85 - std::cout << "elapsed time: " << ts << std::endl << std::endl;
3.86 + << ml.size() << endl;
3.87 + cout << "elapsed time: " << ts << endl << endl;
3.88
3.89 // ts.reset();
3.90 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
3.91 // typedef SageGraph MutableGraph;
3.92 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
3.93 -// std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
3.94 -// << std::endl << "Matching size: "
3.95 -// << max_flow_test.flowValue() << std::endl;
3.96 -// std::cout << "elapsed time: " << ts << std::endl << std::endl;
3.97 +// cout << "HUGO max matching algorithm based on blocking flow augmentation."
3.98 +// << endl << "Matching size: "
3.99 +// << max_flow_test.flowValue() << endl;
3.100 +// cout << "elapsed time: " << ts << endl << endl;
3.101
3.102 {
3.103 SageGraph hg;
3.104 @@ -159,11 +140,11 @@
3.105 SageGraph::EdgeMap<int> >
3.106 max_flow_test(hg, s, t, cm, flow);
3.107 max_flow_test.run();
3.108 - std::cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
3.109 - << std::endl
3.110 + cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
3.111 + << endl
3.112 << "Size of matching: "
3.113 - << max_flow_test.flowValue() << std::endl;
3.114 - std::cout << "elapsed time: " << ts << std::endl << std::endl;
3.115 + << max_flow_test.flowValue() << endl;
3.116 + cout << "elapsed time: " << ts << endl << endl;
3.117 }
3.118
3.119 return 0;