COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_matching_try_3.cc @ 568:ed0a4de23923

Last change on this file since 568:ed0a4de23923 was 559:82a8f2bc5758, checked in by marci, 21 years ago

A max bipartite matching class in src/work/marci/max_bipartite_matching.h
which can be used for computing maximum cardinality ordinary matching, b-matching and capacitated b-matching.

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