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