// -*- c++ -*- #include #include #include #include #include #include #include #include #include #include //#include //#include #include #include #include #include #include /** * Inicializalja a veletlenszamgeneratort. * Figyelem, ez nem jo igazi random szamokhoz, * erre ne bizzad a titkaidat! */ void random_init() { unsigned int seed = getpid(); seed |= seed << 15; seed ^= time(0); srand(seed); } /** * Egy veletlen int-et ad vissza 0 es m-1 kozott. */ int random(int m) { return int( double(m) * rand() / (RAND_MAX + 1.0) ); } using namespace hugo; int main() { //for leda graph leda::graph lg; //lg.make_undirected(); typedef LedaGraphWrapper Graph; Graph g(lg); //for UndirListGraph //typedef UndirListGraph Graph; //Graph g; typedef Graph::Node Node; typedef Graph::NodeIt NodeIt; typedef Graph::Edge Edge; typedef Graph::EdgeIt EdgeIt; typedef Graph::OutEdgeIt OutEdgeIt; std::vector s_nodes; std::vector t_nodes; int a; std::cout << "number of nodes in the first color class="; std::cin >> a; int b; std::cout << "number of nodes in the second color class="; std::cin >> b; int m; std::cout << "number of edges="; std::cin >> m; int k; 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"; std::cout << "number of groups in LEDA random group graph="; std::cin >> k; std::cout << std::endl; leda_list lS; leda_list lT; random_bigraph(lg, a, b, m, lS, lT, k); Graph::NodeMap ref_map(g, -1); IterableBoolMap< Graph::NodeMap > bipartite_map(ref_map); //generating leda random group graph leda_node ln; forall(ln, lS) bipartite_map.insert(ln, false); forall(ln, lT) bipartite_map.insert(ln, true); //making bipartite graph typedef BipartiteGraphWrapper BGW; BGW bgw(g, bipartite_map); //st-wrapper typedef stGraphWrapper stGW; stGW stgw(bgw); ConstMap const1map(1); stGW::EdgeMap flow(stgw); Timer ts; ts.reset(); FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); MaxFlow, stGW::EdgeMap > max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/); max_flow_test.run(); std::cout << "HUGO max matching algorithm based on preflow." << std::endl << "Size of matching: " << max_flow_test.flowValue() << std::endl; std::cout << "elapsed time: " << ts << std::endl << std::endl; ts.reset(); leda_list ml=MAX_CARD_BIPARTITE_MATCHING(lg); std::cout << "LEDA max matching algorithm." << std::endl << "Size of matching: " << ml.size() << std::endl; std::cout << "elapsed time: " << ts << std::endl; std::cout << "\n"; ts.reset(); FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0); typedef ListGraph MutableGraph; while (max_flow_test.augmentOnBlockingFlow()) { } std::cout << "HUGO max matching algorithm based on blocking flow augmentation." << std::endl << "Matching size: " << max_flow_test.flowValue() << std::endl; std::cout << "elapsed time: " << ts << std::endl; return 0; }