1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/leda/comparison.cc Tue May 11 21:26:29 2004 +0000
1.3 @@ -0,0 +1,170 @@
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 <hugo/time_measure.h>
1.20 +#include <for_each_macros.h>
1.21 +#include <hugo/graph_wrapper.h>
1.22 +#include <bipartite_graph_wrapper.h>
1.23 +#include <hugo/maps.h>
1.24 +#include <max_flow.h>
1.25 +
1.26 +/**
1.27 + * Inicializalja a veletlenszamgeneratort.
1.28 + * Figyelem, ez nem jo igazi random szamokhoz,
1.29 + * erre ne bizzad a titkaidat!
1.30 + */
1.31 +void random_init()
1.32 +{
1.33 + unsigned int seed = getpid();
1.34 + seed |= seed << 15;
1.35 + seed ^= time(0);
1.36 +
1.37 + srand(seed);
1.38 +}
1.39 +
1.40 +/**
1.41 + * Egy veletlen int-et ad vissza 0 es m-1 kozott.
1.42 + */
1.43 +int random(int m)
1.44 +{
1.45 + return int( double(m) * rand() / (RAND_MAX + 1.0) );
1.46 +}
1.47 +
1.48 +using namespace hugo;
1.49 +
1.50 +int main() {
1.51 + //for leda graph
1.52 + leda::graph lg;
1.53 + //lg.make_undirected();
1.54 + typedef LedaGraphWrapper<leda::graph> Graph;
1.55 + Graph g(lg);
1.56 +
1.57 + //for UndirListGraph
1.58 + //typedef UndirListGraph Graph;
1.59 + //Graph g;
1.60 +
1.61 + typedef Graph::Node Node;
1.62 + typedef Graph::NodeIt NodeIt;
1.63 + typedef Graph::Edge Edge;
1.64 + typedef Graph::EdgeIt EdgeIt;
1.65 + typedef Graph::OutEdgeIt OutEdgeIt;
1.66 +
1.67 + std::vector<Graph::Node> s_nodes;
1.68 + std::vector<Graph::Node> t_nodes;
1.69 +
1.70 + int a;
1.71 + std::cout << "number of nodes in the first color class=";
1.72 + std::cin >> a;
1.73 + int b;
1.74 + std::cout << "number of nodes in the second color class=";
1.75 + std::cin >> b;
1.76 + int m;
1.77 + std::cout << "number of edges=";
1.78 + std::cin >> m;
1.79 + int k;
1.80 + 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";
1.81 + std::cout << "number of groups in LEDA random group graph=";
1.82 + std::cin >> k;
1.83 + std::cout << std::endl;
1.84 +
1.85 + leda_list<leda_node> lS;
1.86 + leda_list<leda_node> lT;
1.87 + random_bigraph(lg, a, b, m, lS, lT, k);
1.88 +
1.89 + Graph::NodeMap<int> ref_map(g, -1);
1.90 + IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.91 +
1.92 + //generating leda random group graph
1.93 + leda_node ln;
1.94 + forall(ln, lS) bipartite_map.insert(ln, false);
1.95 + forall(ln, lT) bipartite_map.insert(ln, true);
1.96 +
1.97 + //making bipartite graph
1.98 + typedef BipartiteGraphWrapper<Graph> BGW;
1.99 + BGW bgw(g, bipartite_map);
1.100 +
1.101 +
1.102 + //st-wrapper
1.103 + typedef stGraphWrapper<BGW> stGW;
1.104 + stGW stgw(bgw);
1.105 + ConstMap<stGW::Edge, int> const1map(1);
1.106 + stGW::EdgeMap<int> flow(stgw);
1.107 +
1.108 + Timer ts;
1.109 +
1.110 + ts.reset();
1.111 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.112 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.113 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
1.114 + max_flow_test.run();
1.115 + std::cout << "HUGO max matching algorithm based on preflow." << std::endl
1.116 + << "Size of matching: "
1.117 + << max_flow_test.flowValue() << std::endl;
1.118 + std::cout << "elapsed time: " << ts << std::endl << std::endl;
1.119 +
1.120 + ts.reset();
1.121 + leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
1.122 + std::cout << "LEDA max matching algorithm." << std::endl
1.123 + << "Size of matching: "
1.124 + << ml.size() << std::endl;
1.125 + std::cout << "elapsed time: " << ts << std::endl << std::endl;
1.126 +
1.127 +// ts.reset();
1.128 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.129 +// typedef ListGraph MutableGraph;
1.130 +// while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
1.131 +// std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
1.132 +// << std::endl << "Matching size: "
1.133 +// << max_flow_test.flowValue() << std::endl;
1.134 +// std::cout << "elapsed time: " << ts << std::endl << std::endl;
1.135 +
1.136 + {
1.137 + ListGraph hg;
1.138 + ListGraph::Node s=hg.addNode();
1.139 + ListGraph::Node t=hg.addNode();
1.140 + BGW::NodeMap<ListGraph::Node> b_s_nodes(bgw);
1.141 + BGW::NodeMap<ListGraph::Node> b_t_nodes(bgw);
1.142 +
1.143 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
1.144 + b_s_nodes.set(n, hg.addNode());
1.145 + hg.addEdge(s, b_s_nodes[n]);
1.146 + }
1.147 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
1.148 + b_t_nodes.set(n, hg.addNode());
1.149 + hg.addEdge(b_t_nodes[n], t);
1.150 + }
1.151 +
1.152 + FOR_EACH_LOC(BGW::EdgeIt, e, bgw)
1.153 + hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]);
1.154 +
1.155 + ConstMap<ListGraph::Edge, int> cm(1);
1.156 + ListGraph::EdgeMap<int> flow(hg); //0
1.157 +
1.158 + Timer ts;
1.159 +
1.160 + ts.reset();
1.161 + MaxFlow<ListGraph, int, ConstMap<ListGraph::Edge, int>,
1.162 + ListGraph::EdgeMap<int> >
1.163 + max_flow_test(hg, s, t, cm, flow);
1.164 + max_flow_test.run();
1.165 + std::cout << "HUGO max matching algorithm on ListGraph by copying the graph, based on preflow."
1.166 + << std::endl
1.167 + << "Size of matching: "
1.168 + << max_flow_test.flowValue() << std::endl;
1.169 + std::cout << "elapsed time: " << ts << std::endl << std::endl;
1.170 + }
1.171 +
1.172 + return 0;
1.173 +}