COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/comparison.cc @ 769:eb61fbc64c16

Last change on this file since 769:eb61fbc64c16 was 769:eb61fbc64c16, checked in by marci, 17 years ago

.

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