src/work/jacint/ledacomp.cc
author athos
Wed, 23 Mar 2005 11:51:40 +0000
changeset 1247 60708e1475ae
parent 581 26e1cd224bdc
permissions -rw-r--r--
Completions.
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 #include <vector>
     5 #include <cstdlib>
     6 
     7 #include <LEDA/graph.h>
     8 #include <LEDA/mc_matching.h>
     9 #include <LEDA/list.h>
    10 #include <LEDA/graph_gen.h>
    11 
    12 #include <leda_graph_wrapper.h>
    13 #include <list_graph.h>
    14 #include <dimacs.h>
    15 #include <time_measure.h>
    16 #include <for_each_macros.h>
    17 #include <graph_wrapper.h>
    18 #include <bipartite_graph_wrapper.h>
    19 #include <maps.h>
    20 #include <max_matching.h>
    21 
    22 // /**
    23 //  * Inicializalja a veletlenszamgeneratort.
    24 //  * Figyelem, ez nem jo igazi random szamokhoz,
    25 //  * erre ne bizzad a titkaidat!
    26 //  */
    27 // void random_init()
    28 // {
    29 // 	unsigned int seed = getpid();
    30 // 	seed |= seed << 15;
    31 // 	seed ^= time(0);
    32 
    33 // 	srand(seed);
    34 // }
    35 
    36 // /**
    37 //  * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    38 //  */
    39 // int random(int m)
    40 // {
    41 //   return int( double(m) * rand() / (RAND_MAX + 1.0) );
    42 // }
    43 
    44 using namespace lemon;
    45 
    46 int main() {
    47 
    48   //for leda graph
    49   leda::graph lg;
    50   //lg.make_undirected();
    51   typedef LedaGraphWrapper<leda::graph> Graph;
    52   Graph g(lg);
    53 
    54   //for UndirListGraph
    55   //typedef UndirListGraph Graph; 
    56   //Graph g;
    57 
    58   typedef Graph::Node Node;
    59   typedef Graph::NodeIt NodeIt;
    60   typedef Graph::Edge Edge;
    61   typedef Graph::EdgeIt EdgeIt;
    62   typedef Graph::OutEdgeIt OutEdgeIt;
    63 
    64   std::vector<Graph::Node> s_nodes;
    65   std::vector<Graph::Node> t_nodes;
    66 
    67   int n;
    68   std::cout << "Number of nodes=";
    69   std::cin >> n; 
    70   int m;
    71   std::cout << "number of edges=";
    72   std::cin >> m; 
    73   std::cout << std::endl;
    74   
    75   random_graph(lg, n, m);
    76 
    77   Timer ts;
    78 
    79   //  writeDimacs(std::cout, g); //for check
    80 
    81   MaxMatching<Graph> max_matching(g);
    82   std::cout << 
    83     "Running the edmonds algorithm run()... " 
    84 	    <<std::endl;
    85   ts.reset();  
    86   max_matching.run();
    87   std::cout<<"Elapsed time: "<<ts<<std::endl;
    88   int s=0;
    89   Graph::NodeMap<Node> mate(g,INVALID);
    90   max_matching.writeNMapNode(mate);
    91   NodeIt v;
    92   for(g.first(v); g.valid(v); g.next(v) ) {
    93     if ( g.valid(mate[v]) ) {
    94       ++s;
    95     }
    96   }
    97   int size=(int)s/2;  //size will be used as the size of a maxmatching
    98   std::cout << size << " is the size of the matching found by run(),"<<std::endl;
    99   if ( size == max_matching.size() ) {
   100     std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl;
   101   } else {  
   102     std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl;
   103   }
   104 
   105 
   106 
   107 
   108   ts.reset();  
   109   leda_list<leda_edge> ml=MAX_CARD_MATCHING(lg);
   110   std::cout << "LEDA max matching algorithm." << std::endl 
   111 	    << "Size of matching: " 
   112 	    << ml.size() << std::endl;
   113   std::cout << "elapsed time: " << ts << std::endl;
   114   std::cout << "\n";
   115 
   116   return 0;
   117 }