src/work/jacint/ledacomp.cc
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
     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 hugo;
    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 }