1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc Tue Apr 27 14:10:19 2004 +0000
1.3 @@ -0,0 +1,158 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +#include <vector>
1.8 +#include <cstdlib>
1.9 +
1.10 +#include <LEDA/graph.h>
1.11 +#include <LEDA/mcb_matching.h>
1.12 +#include <LEDA/list.h>
1.13 +#include <LEDA/graph_gen.h>
1.14 +
1.15 +#include <leda_graph_wrapper.h>
1.16 +#include <list_graph.h>
1.17 +//#include <smart_graph.h>
1.18 +//#include <dimacs.h>
1.19 +#include <time_measure.h>
1.20 +#include <for_each_macros.h>
1.21 +//#include <bfs_iterator.h>
1.22 +#include <graph_wrapper.h>
1.23 +#include <maps.h>
1.24 +#include <edmonds_karp.h>
1.25 +#include <preflow.h>
1.26 +
1.27 +/**
1.28 + * Inicializalja a veletlenszamgeneratort.
1.29 + * Figyelem, ez nem jo igazi random szamokhoz,
1.30 + * erre ne bizzad a titkaidat!
1.31 + */
1.32 +void random_init()
1.33 +{
1.34 + unsigned int seed = getpid();
1.35 + seed |= seed << 15;
1.36 + seed ^= time(0);
1.37 +
1.38 + srand(seed);
1.39 +}
1.40 +
1.41 +/**
1.42 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
1.43 + */
1.44 +int random(int m)
1.45 +{
1.46 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
1.47 +}
1.48 +
1.49 +using namespace hugo;
1.50 +
1.51 +int main() {
1.52 + //for leda graph
1.53 + leda::graph lg;
1.54 + //lg.make_undirected();
1.55 + typedef LedaGraphWrapper<leda::graph> Graph;
1.56 + Graph g(lg);
1.57 +
1.58 + //for UndirListGraph
1.59 + //typedef UndirListGraph Graph;
1.60 + //Graph g;
1.61 +
1.62 + typedef Graph::Node Node;
1.63 + typedef Graph::NodeIt NodeIt;
1.64 + typedef Graph::Edge Edge;
1.65 + typedef Graph::EdgeIt EdgeIt;
1.66 + typedef Graph::OutEdgeIt OutEdgeIt;
1.67 +
1.68 + std::vector<Graph::Node> s_nodes;
1.69 + std::vector<Graph::Node> t_nodes;
1.70 +
1.71 + int a;
1.72 + std::cout << "number of nodes in the first color class=";
1.73 + std::cin >> a;
1.74 + int b;
1.75 + std::cout << "number of nodes in the second color class=";
1.76 + std::cin >> b;
1.77 + int m;
1.78 + std::cout << "number of edges=";
1.79 + std::cin >> m;
1.80 + int k;
1.81 + std::cout << "number of groups in LEDA random group graph=";
1.82 + std::cin >> k;
1.83 +
1.84 + leda_list<leda_node> lS;
1.85 + leda_list<leda_node> lT;
1.86 + random_bigraph(lg, a, b, m, lS, lT, k);
1.87 +
1.88 +// for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
1.89 +// for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
1.90 +
1.91 +// random_init();
1.92 +// for(int i=0; i<m; ++i) {
1.93 +// g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
1.94 +// }
1.95 +
1.96 + Graph::NodeMap<int> ref_map(g, -1);
1.97 +
1.98 + IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.99 +// for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
1.100 +// for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
1.101 + leda_node ln;
1.102 + forall(ln, lS) bipartite_map.insert(ln, false);
1.103 + forall(ln, lT) bipartite_map.insert(ln, true);
1.104 +
1.105 + typedef BipartiteGraphWrapper<Graph> BGW;
1.106 + BGW bgw(g, bipartite_map);
1.107 +
1.108 + // BGW::NodeMap<int> dbyj(bgw);
1.109 + // BGW::EdgeMap<int> dbyxcj(bgw);
1.110 +
1.111 + typedef stGraphWrapper<BGW> stGW;
1.112 + stGW stgw(bgw);
1.113 + ConstMap<stGW::Edge, int> const1map(1);
1.114 + stGW::EdgeMap<int> flow(stgw);
1.115 +
1.116 + Timer ts;
1.117 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.118 + ts.reset();
1.119 + // stGW::EdgeMap<int> pre_flow(stgw);
1.120 + Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.121 + pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow, true);
1.122 + pre_flow_test.run();
1.123 + std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl;
1.124 + std::cout << "elapsed time: " << ts << std::endl;
1.125 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.126 +// std::cout << e << ": " << pre_flow[e] << "\n";
1.127 +// }
1.128 + std::cout << "\n";
1.129 +
1.130 + ts.reset();
1.131 + leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
1.132 + // stGW::EdgeMap<int> pre_flow(stgw);
1.133 + //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.134 + // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
1.135 + //pre_flow_test.run();
1.136 + std::cout << "LEDA matching value: " << ml.size() << std::endl;
1.137 + std::cout << "elapsed time: " << ts << std::endl;
1.138 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.139 +// std::cout << e << ": " << pre_flow[e] << "\n";
1.140 +// }
1.141 + std::cout << "\n";
1.142 +
1.143 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.144 + ts.reset();
1.145 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.146 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.147 +// while (max_flow_test.augmentOnShortestPath()) { }
1.148 + typedef ListGraph MutableGraph;
1.149 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
1.150 + while (max_flow_test.augmentOnBlockingFlow2()) {
1.151 + std::cout << max_flow_test.flowValue() << std::endl;
1.152 + }
1.153 + std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl;
1.154 + std::cout << "elapsed time: " << ts << std::endl;
1.155 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
1.156 +// std::cout << e << ": " << max_flow[e] << "\n";
1.157 +// }
1.158 +// std::cout << "\n";
1.159 +
1.160 + return 0;
1.161 +}