jacint@581: // -*- c++ -*- jacint@581: #include <iostream> jacint@581: #include <fstream> jacint@581: #include <vector> jacint@581: #include <cstdlib> jacint@581: jacint@581: #include <LEDA/graph.h> jacint@581: #include <LEDA/mc_matching.h> jacint@581: #include <LEDA/list.h> jacint@581: #include <LEDA/graph_gen.h> jacint@581: jacint@581: #include <leda_graph_wrapper.h> jacint@581: #include <list_graph.h> jacint@581: #include <dimacs.h> jacint@581: #include <time_measure.h> jacint@581: #include <for_each_macros.h> jacint@581: #include <graph_wrapper.h> jacint@581: #include <bipartite_graph_wrapper.h> jacint@581: #include <maps.h> jacint@581: #include <max_matching.h> jacint@581: jacint@581: // /** jacint@581: // * Inicializalja a veletlenszamgeneratort. jacint@581: // * Figyelem, ez nem jo igazi random szamokhoz, jacint@581: // * erre ne bizzad a titkaidat! jacint@581: // */ jacint@581: // void random_init() jacint@581: // { jacint@581: // unsigned int seed = getpid(); jacint@581: // seed |= seed << 15; jacint@581: // seed ^= time(0); jacint@581: jacint@581: // srand(seed); jacint@581: // } jacint@581: jacint@581: // /** jacint@581: // * Egy veletlen int-et ad vissza 0 es m-1 kozott. jacint@581: // */ jacint@581: // int random(int m) jacint@581: // { jacint@581: // return int( double(m) * rand() / (RAND_MAX + 1.0) ); jacint@581: // } jacint@581: alpar@921: using namespace lemon; jacint@581: jacint@581: int main() { jacint@581: jacint@581: //for leda graph jacint@581: leda::graph lg; jacint@581: //lg.make_undirected(); jacint@581: typedef LedaGraphWrapper<leda::graph> Graph; jacint@581: Graph g(lg); jacint@581: jacint@581: //for UndirListGraph jacint@581: //typedef UndirListGraph Graph; jacint@581: //Graph g; jacint@581: jacint@581: typedef Graph::Node Node; jacint@581: typedef Graph::NodeIt NodeIt; jacint@581: typedef Graph::Edge Edge; jacint@581: typedef Graph::EdgeIt EdgeIt; jacint@581: typedef Graph::OutEdgeIt OutEdgeIt; jacint@581: jacint@581: std::vector<Graph::Node> s_nodes; jacint@581: std::vector<Graph::Node> t_nodes; jacint@581: jacint@581: int n; jacint@581: std::cout << "Number of nodes="; jacint@581: std::cin >> n; jacint@581: int m; jacint@581: std::cout << "number of edges="; jacint@581: std::cin >> m; jacint@581: std::cout << std::endl; jacint@581: jacint@581: random_graph(lg, n, m); jacint@581: jacint@581: Timer ts; jacint@581: jacint@581: // writeDimacs(std::cout, g); //for check jacint@581: jacint@581: MaxMatching<Graph> max_matching(g); jacint@581: std::cout << jacint@581: "Running the edmonds algorithm run()... " jacint@581: <<std::endl; jacint@581: ts.reset(); jacint@581: max_matching.run(); jacint@581: std::cout<<"Elapsed time: "<<ts<<std::endl; jacint@581: int s=0; jacint@581: Graph::NodeMap<Node> mate(g,INVALID); jacint@581: max_matching.writeNMapNode(mate); jacint@581: NodeIt v; jacint@581: for(g.first(v); g.valid(v); g.next(v) ) { jacint@581: if ( g.valid(mate[v]) ) { jacint@581: ++s; jacint@581: } jacint@581: } jacint@581: int size=(int)s/2; //size will be used as the size of a maxmatching jacint@581: std::cout << size << " is the size of the matching found by run(),"<<std::endl; jacint@581: if ( size == max_matching.size() ) { jacint@581: std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl; jacint@581: } else { jacint@581: std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl; jacint@581: } jacint@581: jacint@581: jacint@581: jacint@581: jacint@581: ts.reset(); jacint@581: leda_list<leda_edge> ml=MAX_CARD_MATCHING(lg); jacint@581: std::cout << "LEDA max matching algorithm." << std::endl jacint@581: << "Size of matching: " jacint@581: << ml.size() << std::endl; jacint@581: std::cout << "elapsed time: " << ts << std::endl; jacint@581: std::cout << "\n"; jacint@581: jacint@581: return 0; jacint@581: }