1.1 --- a/src/work/marci/leda/bipartite_matching_leda_gen.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,138 +0,0 @@
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 <sage_graph.h>
1.17 -//#include <smart_graph.h>
1.18 -//#include <dimacs.h>
1.19 -#include <lemon/time_measure.h>
1.20 -#include <for_each_macros.h>
1.21 -#include <lemon/graph_wrapper.h>
1.22 -#include <bipartite_graph_wrapper.h>
1.23 -#include <lemon/maps.h>
1.24 -#include <lemon/max_flow.h>
1.25 -#include <augmenting_flow.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 lemon;
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 UndirSageGraph
1.59 - //typedef UndirSageGraph 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 << "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.82 - std::cout << "number of groups in LEDA random group graph=";
1.83 - std::cin >> k;
1.84 - std::cout << std::endl;
1.85 -
1.86 - leda_list<leda_node> lS;
1.87 - leda_list<leda_node> lT;
1.88 - random_bigraph(lg, a, b, m, lS, lT, k);
1.89 -
1.90 - Graph::NodeMap<int> ref_map(g, -1);
1.91 - IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.92 -
1.93 - //generating leda random group graph
1.94 - leda_node ln;
1.95 - forall(ln, lS) bipartite_map.insert(ln, false);
1.96 - forall(ln, lT) bipartite_map.insert(ln, true);
1.97 -
1.98 - //making bipartite graph
1.99 - typedef BipartiteGraphWrapper<Graph> BGW;
1.100 - BGW bgw(g, bipartite_map);
1.101 -
1.102 -
1.103 - //st-wrapper
1.104 - typedef stBipartiteGraphWrapper<BGW> stGW;
1.105 - stGW stgw(bgw);
1.106 - ConstMap<stGW::Edge, int> const1map(1);
1.107 - stGW::EdgeMap<int> flow(stgw);
1.108 -
1.109 - Timer ts;
1.110 -
1.111 - ts.reset();
1.112 - FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.113 - MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.114 - max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
1.115 - max_flow_test.run();
1.116 - std::cout << "LEMON max matching algorithm based on preflow." << std::endl
1.117 - << "Size of matching: "
1.118 - << max_flow_test.flowValue() << std::endl;
1.119 - std::cout << "elapsed time: " << ts << std::endl << std::endl;
1.120 -
1.121 - ts.reset();
1.122 - leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
1.123 - std::cout << "LEDA max matching algorithm." << std::endl
1.124 - << "Size of matching: "
1.125 - << ml.size() << std::endl;
1.126 - std::cout << "elapsed time: " << ts << std::endl;
1.127 - std::cout << "\n";
1.128 -
1.129 - ts.reset();
1.130 - FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.131 - typedef SageGraph MutableGraph;
1.132 - AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.133 - max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
1.134 - while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
1.135 - std::cout << "LEMON max matching algorithm based on blocking flow augmentation."
1.136 - << std::endl << "Matching size: "
1.137 - << max_flow_test_1.flowValue() << std::endl;
1.138 - std::cout << "elapsed time: " << ts << std::endl;
1.139 -
1.140 - return 0;
1.141 -}