jacint@581: // -*- c++ -*- jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include jacint@581: #include 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: jacint@581: using namespace hugo; 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 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 s_nodes; jacint@581: std::vector 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 max_matching(g); jacint@581: std::cout << jacint@581: "Running the edmonds algorithm run()... " jacint@581: < 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(),"< 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: }