COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/bipartite_matching_comparison.cc @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 15 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 4.2 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/mcb_matching.h>
9#include <LEDA/list.h>
10#include <LEDA/graph_gen.h>
11
12#include <leda_graph_wrapper.h>
13#include <sage_graph.h>
14//#include <smart_graph.h>
15//#include <dimacs.h>
16#include <lemon/time_measure.h>
17#include <for_each_macros.h>
18#include <lemon/graph_wrapper.h>
19#include <bipartite_graph_wrapper.h>
20#include <lemon/maps.h>
21#include <lemon/max_flow.h>
22
23using std::cin;
24using std::cout;
25using std::endl;
26
27using namespace lemon;
28
29int main() {
30  //for leda graph
31  leda::graph lg;
32  //lg.make_undirected();
33  typedef LedaGraphWrapper<leda::graph> Graph;
34  Graph g(lg);
35
36  //for UndirSageGraph
37  //typedef UndirSageGraph Graph;
38  //Graph g;
39
40  typedef Graph::Node Node;
41  typedef Graph::NodeIt NodeIt;
42  typedef Graph::Edge Edge;
43  typedef Graph::EdgeIt EdgeIt;
44  typedef Graph::OutEdgeIt OutEdgeIt;
45
46  std::vector<Graph::Node> s_nodes;
47  std::vector<Graph::Node> t_nodes;
48
49  int a;
50  cout << "number of nodes in the first color class=";
51  cin >> a;
52  int b;
53  cout << "number of nodes in the second color class=";
54  cin >> b;
55  int m;
56  cout << "number of edges=";
57  cin >> m;
58  int k;
59  cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
60  cout << "number of groups in LEDA random group graph=";
61  cin >> k;
62  cout << endl;
63 
64  leda_list<leda_node> lS;
65  leda_list<leda_node> lT;
66  random_bigraph(lg, a, b, m, lS, lT, k);
67
68  Graph::NodeMap<int> ref_map(g, -1);
69  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
70
71  //generating leda random group graph
72  leda_node ln;
73  forall(ln, lS) bipartite_map.insert(ln, false);
74  forall(ln, lT) bipartite_map.insert(ln, true);
75
76  //making bipartite graph
77  typedef BipartiteGraphWrapper<Graph> BGW;
78  BGW bgw(g, bipartite_map);
79
80
81  //st-wrapper
82  typedef stBipartiteGraphWrapper<BGW> stGW;
83  stGW stgw(bgw);
84  ConstMap<stGW::Edge, int> const1map(1);
85  stGW::EdgeMap<int> flow(stgw);
86
87  Timer ts;
88
89  ts.reset();
90  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
91  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
92    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
93  max_flow_test.run();
94  cout << "LEMON max matching algorithm based on preflow." << endl
95            << "Size of matching: "
96            << max_flow_test.flowValue() << endl;
97  cout << "elapsed time: " << ts << endl << endl;
98
99  ts.reset(); 
100  leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
101  cout << "LEDA max matching algorithm." << endl
102            << "Size of matching: "
103            << ml.size() << endl;
104  cout << "elapsed time: " << ts << endl << endl;
105
106//   ts.reset();
107//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
108//   typedef SageGraph MutableGraph;
109//   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
110//   cout << "LEMON max matching algorithm based on blocking flow augmentation."
111//          << endl << "Matching size: "
112//          << max_flow_test.flowValue() << endl;
113//   cout << "elapsed time: " << ts << endl << endl;
114
115  {
116  SageGraph hg;
117  SageGraph::Node s=hg.addNode(); 
118  SageGraph::Node t=hg.addNode();
119  BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw); 
120  BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw);
121 
122  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
123    b_s_nodes.set(n, hg.addNode());
124    hg.addEdge(s, b_s_nodes[n]);
125  }
126  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
127    b_t_nodes.set(n, hg.addNode());
128    hg.addEdge(b_t_nodes[n], t);
129  }
130
131  FOR_EACH_LOC(BGW::EdgeIt, e, bgw)
132    hg.addEdge(b_s_nodes[bgw.source(e)], b_t_nodes[bgw.target(e)]);
133
134  ConstMap<SageGraph::Edge, int> cm(1);
135  SageGraph::EdgeMap<int> flow(hg); //0
136 
137  Timer ts;
138
139  ts.reset();
140  MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>,
141    SageGraph::EdgeMap<int> >
142    max_flow_test(hg, s, t, cm, flow);
143  max_flow_test.run();
144  cout << "LEMON max matching algorithm on SageGraph by copying the graph, based on preflow."
145            << endl
146            << "Size of matching: "
147            << max_flow_test.flowValue() << endl;
148  cout << "elapsed time: " << ts << endl << endl;
149  }
150
151  return 0;
152}
Note: See TracBrowser for help on using the repository browser.