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