COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_matching_demo.cc @ 1153:4b0468de3a31

Last change on this file since 1153:4b0468de3a31 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

File size: 5.8 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <vector>
5
6#include <sage_graph.h>
7//#include <smart_graph.h>
8//#include <dimacs.h>
9#include <lemon/time_measure.h>
10#include <for_each_macros.h>
11#include <bfs_dfs.h>
12#include <bipartite_graph_wrapper.h>
13#include <lemon/maps.h>
14#include <lemon/max_flow.h>
15#include <graph_gen.h>
16#include <max_bipartite_matching.h>
17
18using namespace lemon;
19
20using std::cin;
21using std::cout;
22using std::endl;
23
24int main() {
25  //typedef UndirListGraph Graph;
26  typedef BipartiteGraph<SageGraph> Graph;
27 
28  typedef Graph::Node Node;
29  typedef Graph::NodeIt NodeIt;
30  typedef Graph::Edge Edge;
31  typedef Graph::EdgeIt EdgeIt;
32  typedef Graph::OutEdgeIt OutEdgeIt;
33
34  Graph g;
35
36  int a;
37  cout << "number of nodes in the first color class=";
38  cin >> a;
39  int b;
40  cout << "number of nodes in the second color class=";
41  cin >> b;
42  int m;
43  cout << "number of edges=";
44  cin >> m;
45 
46  cout << "Generatig a random bipartite graph..." << endl;
47  random_init();
48  randomBipartiteGraph(g, a, b, m);
49
50//   cout << "Edges of the bipartite graph:" << endl;
51//   FOR_EACH_LOC(EdgeIt, e, g) cout << e << " ";
52//   cout << endl;
53
54//   cout << "Nodes:" << endl;
55//   FOR_EACH_LOC(Graph::NodeIt, v, g) cout << v << " ";
56//   cout << endl;
57//   cout << "Nodes in T:" << endl;
58//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
59//   cout << endl;
60//   cout << "Nodes in S:" << endl;
61//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
62//   cout << endl;
63
64//   cout << "Erasing the first node..." << endl;
65//   NodeIt n;
66//   g.first(n);
67//   g.erase(n);
68//   cout << "Nodes of the bipartite graph:" << endl;
69//   FOR_EACH_GLOB(n, g) cout << n << " ";
70//   cout << endl;
71
72//   cout << "Nodes in T:" << endl;
73//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) cout << v << " ";
74//   cout << endl;
75//   cout << "Nodes in S:" << endl;
76//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) cout << v << " ";
77//   cout << endl;
78
79  typedef stBipartiteGraphWrapper<Graph> stGW;
80  stGW stgw(g);
81  ConstMap<stGW::Edge, int> const1map(1);
82
83  Timer ts;
84  cout << "max bipartite matching with stGraphWrapper..." << endl;
85  ts.reset();
86  stGW::EdgeMap<int> flow(stgw);
87  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
88    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
89  max_flow_test.run();
90//  while (max_flow_test.augmentOnShortestPath()) { }
91//  typedef ListGraph MutableGraph;
92//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
93//  while (max_flow_test.augmentOnBlockingFlow2()) {
94//   cout << max_flow_test.flowValue() << endl;
95//  }
96  cout << "matching value: " << max_flow_test.flowValue() << endl;
97  cout << "elapsed time: " << ts << endl;
98//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
99//     if (flow[e]) cout << e << endl;
100//   }
101  cout << endl;
102
103  typedef ConstMap<Graph::Edge, int> EdgeCap;
104  EdgeCap ge1(1);
105  typedef ConstMap<Graph::Node, int> NodeCap;
106  NodeCap gn1(1);
107  typedef Graph::EdgeMap<int> EdgeFlow;
108  EdgeFlow gef(g); //0
109  typedef Graph::NodeMap<int> NodeFlow;
110  NodeFlow gnf(g); //0
111
112  typedef stGW::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
113  typedef stGW::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
114  CapMap cm(ge1, gn1);
115  FlowMap fm(gef, gnf);
116
117  //Timer ts;
118  cout << "max bipartite matching with stGraphWrapper..." << endl;
119  ts.reset();
120  //stGW::EdgeMap<int> flow(stgw);
121  MaxFlow<stGW, int, CapMap, FlowMap>
122    max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
123  max_flow_test1.run();
124//  while (max_flow_test.augmentOnShortestPath()) { }
125//  typedef ListGraph MutableGraph;
126//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
127//  while (max_flow_test.augmentOnBlockingFlow2()) {
128//   cout << max_flow_test.flowValue() << endl;
129//  }
130  cout << "matching value: " << max_flow_test1.flowValue() << endl;
131  cout << "elapsed time: " << ts << endl;
132//   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
133//     if (gef[e]) cout << e << endl;
134//   }
135  cout << endl;
136
137  cout << "max bipartite matching with stGraphWrapper..." << endl;
138  ts.reset();
139  FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
140  FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
141  MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
142    Graph::EdgeMap<int>, Graph::NodeMap<int> >
143    matching_test(g, ge1, gn1, gef, gnf);
144  matching_test.run();
145
146  cout << "matching value: " << matching_test.matchingValue() << endl;
147  cout << "elapsed time: " << ts << endl;
148//   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
149//     if (gef[e]) cout << e << endl;
150//   }
151  cout << endl;
152
153  cout << "max bipartite matching with MaxBipartiteMatching..." << endl;
154  ts.reset();
155  FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
156  //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
157  typedef MaxBipartiteMatching<Graph, ConstMap<Graph::Edge, int>,
158    ConstMap<Graph::Node, int>,
159    Graph::EdgeMap<int>, Graph::NodeMap<int> > MaxBipartiteMatching;
160  MaxBipartiteMatching matching_test_1(g, ge1, gn1, gef/*, gnf*/);
161  matching_test_1.run();
162
163  cout << "matching value: " << matching_test_1.matchingValue() << endl;
164  cout << "elapsed time: " << ts << endl;
165//   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
166//     if (gef[e]) cout << e << endl;
167//   }
168  cout << endl;
169
170  cout << "testing optimality with MaxBipartiteMatching..." << endl;
171  ts.reset();
172  matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING);
173  cout << "matching value: " << matching_test_1.matchingValue() << endl;
174  cout << "elapsed time: " << ts << endl;
175
176  cout << "testing optimality with MaxBipartiteMatching..." << endl;
177  ts.reset();
178  matching_test_1.run(MaxBipartiteMatching::GEN_MATCHING_WITH_GOOD_NODE_FLOW);
179  cout << "matching value: " << matching_test_1.matchingValue() << endl;
180  cout << "elapsed time: " << ts << endl;
181
182  return 0;
183}
Note: See TracBrowser for help on using the repository browser.