COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/ledacomp.cc @ 619:e09818232531

Last change on this file since 619:e09818232531 was 581:26e1cd224bdc, checked in by jacint, 21 years ago

leda-hugo matching alg osszehasonlito

File size: 2.6 KB
Line 
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
44using namespace hugo;
45
46int 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}
Note: See TracBrowser for help on using the repository browser.