COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_matching_try.cc @ 762:511200bdb71f

Last change on this file since 762:511200bdb71f was 762:511200bdb71f, checked in by marci, 16 years ago

technical corrections

File size: 5.7 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <vector>
5#include <cstdlib>
6
7#include <sage_graph.h>
8//#include <smart_graph.h>
9//#include <dimacs.h>
10#include <hugo/time_measure.h>
11#include <for_each_macros.h>
12#include <bfs_dfs.h>
13#include <hugo/graph_wrapper.h>
14#include <bipartite_graph_wrapper.h>
15#include <hugo/maps.h>
16#include <hugo/max_flow.h>
17#include <augmenting_flow.h>
18
19/**
20 * Inicializalja a veletlenszamgeneratort.
21 * Figyelem, ez nem jo igazi random szamokhoz,
22 * erre ne bizzad a titkaidat!
23 */
24void random_init()
25{
26        unsigned int seed = getpid();
27        seed |= seed << 15;
28        seed ^= time(0);
29
30        srand(seed);
31}
32
33/**
34 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
35 */
36int random(int m)
37{
38  return int( double(m) * rand() / (RAND_MAX + 1.0) );
39}
40
41using namespace hugo;
42
43int main() {
44  typedef UndirSageGraph Graph;
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
51  Graph g;
52
53  std::vector<Graph::Node> s_nodes;
54  std::vector<Graph::Node> t_nodes;
55
56  int a;
57  std::cout << "number of nodes in the first color class=";
58  std::cin >> a;
59  int b;
60  std::cout << "number of nodes in the second color class=";
61  std::cin >> b;
62  int m;
63  std::cout << "number of edges=";
64  std::cin >> m;
65 
66
67  for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
68  for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
69
70  random_init();
71  for(int i=0; i<m; ++i) {
72    g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
73  }
74
75  Graph::NodeMap<int> ref_map(g, -1);
76
77  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
78  for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
79  for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
80
81//   Graph::Node u;
82//   std::cout << "These nodes will be in S:\n";
83//   //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
84//   //irni 1etlen FOR_EACH-csel.
85//   for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
86//     std::cout << u << " ";
87//   std::cout << "\n";
88//   std::cout << "These nodes will be in T:\n";
89//   for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
90//     std::cout << u << " ";
91//   std::cout << "\n";
92
93  typedef BipartiteGraphWrapper<Graph> BGW;
94  BGW bgw(g, bipartite_map);
95
96//   std::cout << "Nodes by NodeIt:\n";
97//   FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
98//     std::cout << n << " ";
99//   }
100//   std::cout << "\n";
101//   std::cout << "Nodes in S by ClassNodeIt:\n";
102//   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
103//     std::cout << n << " ";
104//   }
105//   std::cout << "\n";
106//   std::cout << "Nodes in T by ClassNodeIt:\n";
107//   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
108//     std::cout << n << " ";
109//   }
110//   std::cout << "\n";
111//   std::cout << "Edges of the bipartite graph:\n";
112//   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
113//     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
114//   }
115
116//  BGW::NodeMap<int> dbyj(bgw);
117//  BGW::EdgeMap<int> dbyxcj(bgw);
118
119  typedef stGraphWrapper<BGW> stGW;
120  stGW stgw(bgw);
121  ConstMap<stGW::Edge, int> const1map(1);
122//  stGW::NodeMap<int> ize(stgw);
123
124//   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
125//   Graph::NodeIt si;
126//   Graph::Node s;
127//   s=g.first(si);
128//   bfs.pushAndSetReached(BGW::Node(s));
129//   while (!bfs.finished()) { ++bfs; }
130
131//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
132//     std::cout << "out-edges of " << n << ":\n";
133//     FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
134//       std::cout << " " << e << "\n";
135//       std::cout << " aNode: " << stgw.aNode(e) << "\n";
136//       std::cout << " bNode: " << stgw.bNode(e) << "\n";     
137//     }
138//     std::cout << "in-edges of " << n << ":\n";
139//     FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
140//       std::cout << " " << e << "\n";
141//       std::cout << " aNode: " << stgw.aNode(e) << "\n";
142//       std::cout << " bNode: " << stgw.bNode(e) << "\n";     
143//     }
144//   }
145//   std::cout << "Edges of the stGraphWrapper:\n";
146//   FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
147//     std::cout << " " << n << "\n";
148//   }
149
150//   stGW::NodeMap<bool> b(stgw);
151//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
152//     std::cout << n << ": " << b[n] <<"\n";
153//   }
154
155//   std::cout << "Bfs from s: \n";
156//   BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
157//   bfs_stgw.pushAndSetReached(stgw.S_NODE);
158//   while (!bfs_stgw.finished()) {
159//     std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
160//     ++bfs_stgw;
161//   }
162
163
164  Timer ts;
165  ts.reset();
166  stGW::EdgeMap<int> max_flow(stgw);
167  AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
168    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
169//  while (max_flow_test.augmentOnShortestPath()) { }
170  typedef SageGraph MutableGraph;
171//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
172  while (max_flow_test.augmentOnBlockingFlow2()) {
173   std::cout << max_flow_test.flowValue() << std::endl;
174  }
175  std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
176  std::cout << "elapsed time: " << ts << std::endl;
177//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
178//     std::cout << e << ": " << max_flow[e] << "\n";
179//   }
180//   std::cout << "\n";
181
182  ts.reset();
183  stGW::EdgeMap<int> pre_flow(stgw);
184  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
185    pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
186  pre_flow_test.run();
187  std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
188  std::cout << "elapsed time: " << ts << std::endl;
189//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
190//     std::cout << e << ": " << pre_flow[e] << "\n";
191//   }
192//   std::cout << "\n";
193
194  return 0;
195}
Note: See TracBrowser for help on using the repository browser.