COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_bipartite_matching_demo.cc @ 194:a1680b3c516c

Last change on this file since 194:a1680b3c516c was 194:a1680b3c516c, checked in by marci, 16 years ago

.

File size: 2.5 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_graph_wrapper.h>
9#include <dimacs.h>
10#include <time_measure.h>
11#include <edmonds_karp.h>
12
13/**
14 * Inicializalja a veletlenszamgeneratort.
15 * Figyelem, ez nem jo igazi random szamokhoz,
16 * erre ne bizzad a titkaidat!
17 */
18void random_init()
19{
20        unsigned int seed = getpid();
21        seed |= seed << 15;
22        seed ^= time(0);
23
24        srand(seed);
25}
26
27/**
28 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
29 */
30int random(int m)
31{
32        return int( double(m) * rand() / (RAND_MAX + 1.0) );
33}
34
35using namespace hugo;
36
37using std::cout;
38using std::endl;
39
40int main() {
41  leda::graph g;
42  typedef LedaGraphWrapper<leda::graph> Graph;
43  Graph G(g);
44
45  typedef Graph::Node Node;
46  typedef Graph::NodeIt NodeIt; 
47  typedef Graph::Edge Edge;
48  typedef Graph::EdgeIt EdgeIt;
49  typedef Graph::OutEdgeIt OutEdgeIt;
50  typedef Graph::InEdgeIt InEdgeIt;
51
52  //Node s, t;
53  //Graph::EdgeMap<int> cap(G);
54  //readDimacsMaxFlow(std::cin, G, s, t, cap);
55  std::vector<Node> s_nodes;
56  std::vector<Node> t_nodes;
57
58  for(int i=0; i<20; ++i) {
59    s_nodes.push_back(G.addNode());
60  }
61  for(int i=0; i<20; ++i) {
62    t_nodes.push_back(G.addNode());
63  }
64  random_init();
65  for(int i=0; i<50; ++i) {
66    G.addEdge(s_nodes[random(20)], t_nodes[random(20)]);
67  }
68  Graph::NodeMap<bool> s_map(G); //false
69  Graph::NodeMap<bool> t_map(G); //false
70 
71  for(int i=0; i<20; ++i) {
72    s_map.set(s_nodes[i], true);
73    t_map.set(t_nodes[i], true);
74  }
75
76  {
77    std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
78    Graph::EdgeMap<int> flow(G); //0 flow
79    Graph::EdgeMap<int> cap(G, 1);
80
81    Timer ts;
82    ts.reset();
83
84    MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
85    //max_flow_test.augmentWithBlockingFlow<Graph>();
86    int i=0;
87    while (max_flow_test.augmentOnShortestPath()) {
88//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
89//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
90//     }
91//     std::cout<<std::endl;
92      ++i;
93    }
94
95//   std::cout << "maximum flow: "<< std::endl;
96//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
97//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
98//   }
99//   std::cout<<std::endl;
100    std::cout << "elapsed time: " << ts << std::endl;
101    std::cout << "number of augmentation phases: " << i << std::endl;
102    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
103  }
104 
105
106  return 0;
107}
Note: See TracBrowser for help on using the repository browser.