1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/leda/bipartite_matching_comparison.cc Mon Aug 23 11:44:36 2004 +0000
1.3 @@ -0,0 +1,152 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +#include <vector>
1.8 +#include <cstdlib>
1.9 +
1.10 +#include <LEDA/graph.h>
1.11 +#include <LEDA/mcb_matching.h>
1.12 +#include <LEDA/list.h>
1.13 +#include <LEDA/graph_gen.h>
1.14 +
1.15 +#include <leda_graph_wrapper.h>
1.16 +#include <sage_graph.h>
1.17 +//#include <smart_graph.h>
1.18 +//#include <dimacs.h>
1.19 +#include <hugo/time_measure.h>
1.20 +#include <for_each_macros.h>
1.21 +#include <hugo/graph_wrapper.h>
1.22 +#include <bipartite_graph_wrapper.h>
1.23 +#include <hugo/maps.h>
1.24 +#include <hugo/max_flow.h>
1.25 +
1.26 +using std::cin;
1.27 +using std::cout;
1.28 +using std::endl;
1.29 +
1.30 +using namespace hugo;
1.31 +
1.32 +int main() {
1.33 + //for leda graph
1.34 + leda::graph lg;
1.35 + //lg.make_undirected();
1.36 + typedef LedaGraphWrapper<leda::graph> Graph;
1.37 + Graph g(lg);
1.38 +
1.39 + //for UndirSageGraph
1.40 + //typedef UndirSageGraph Graph;
1.41 + //Graph g;
1.42 +
1.43 + typedef Graph::Node Node;
1.44 + typedef Graph::NodeIt NodeIt;
1.45 + typedef Graph::Edge Edge;
1.46 + typedef Graph::EdgeIt EdgeIt;
1.47 + typedef Graph::OutEdgeIt OutEdgeIt;
1.48 +
1.49 + std::vector<Graph::Node> s_nodes;
1.50 + std::vector<Graph::Node> t_nodes;
1.51 +
1.52 + int a;
1.53 + cout << "number of nodes in the first color class=";
1.54 + cin >> a;
1.55 + int b;
1.56 + cout << "number of nodes in the second color class=";
1.57 + cin >> b;
1.58 + int m;
1.59 + cout << "number of edges=";
1.60 + cin >> m;
1.61 + int k;
1.62 + 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";
1.63 + cout << "number of groups in LEDA random group graph=";
1.64 + cin >> k;
1.65 + cout << endl;
1.66 +
1.67 + leda_list<leda_node> lS;
1.68 + leda_list<leda_node> lT;
1.69 + random_bigraph(lg, a, b, m, lS, lT, k);
1.70 +
1.71 + Graph::NodeMap<int> ref_map(g, -1);
1.72 + IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
1.73 +
1.74 + //generating leda random group graph
1.75 + leda_node ln;
1.76 + forall(ln, lS) bipartite_map.insert(ln, false);
1.77 + forall(ln, lT) bipartite_map.insert(ln, true);
1.78 +
1.79 + //making bipartite graph
1.80 + typedef BipartiteGraphWrapper<Graph> BGW;
1.81 + BGW bgw(g, bipartite_map);
1.82 +
1.83 +
1.84 + //st-wrapper
1.85 + typedef stBipartiteGraphWrapper<BGW> stGW;
1.86 + stGW stgw(bgw);
1.87 + ConstMap<stGW::Edge, int> const1map(1);
1.88 + stGW::EdgeMap<int> flow(stgw);
1.89 +
1.90 + Timer ts;
1.91 +
1.92 + ts.reset();
1.93 + FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.94 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.95 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
1.96 + max_flow_test.run();
1.97 + cout << "HUGO max matching algorithm based on preflow." << endl
1.98 + << "Size of matching: "
1.99 + << max_flow_test.flowValue() << endl;
1.100 + cout << "elapsed time: " << ts << endl << endl;
1.101 +
1.102 + ts.reset();
1.103 + leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
1.104 + cout << "LEDA max matching algorithm." << endl
1.105 + << "Size of matching: "
1.106 + << ml.size() << endl;
1.107 + cout << "elapsed time: " << ts << endl << endl;
1.108 +
1.109 +// ts.reset();
1.110 +// FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
1.111 +// typedef SageGraph MutableGraph;
1.112 +// while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
1.113 +// cout << "HUGO max matching algorithm based on blocking flow augmentation."
1.114 +// << endl << "Matching size: "
1.115 +// << max_flow_test.flowValue() << endl;
1.116 +// cout << "elapsed time: " << ts << endl << endl;
1.117 +
1.118 + {
1.119 + SageGraph hg;
1.120 + SageGraph::Node s=hg.addNode();
1.121 + SageGraph::Node t=hg.addNode();
1.122 + BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw);
1.123 + BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw);
1.124 +
1.125 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
1.126 + b_s_nodes.set(n, hg.addNode());
1.127 + hg.addEdge(s, b_s_nodes[n]);
1.128 + }
1.129 + FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
1.130 + b_t_nodes.set(n, hg.addNode());
1.131 + hg.addEdge(b_t_nodes[n], t);
1.132 + }
1.133 +
1.134 + FOR_EACH_LOC(BGW::EdgeIt, e, bgw)
1.135 + hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]);
1.136 +
1.137 + ConstMap<SageGraph::Edge, int> cm(1);
1.138 + SageGraph::EdgeMap<int> flow(hg); //0
1.139 +
1.140 + Timer ts;
1.141 +
1.142 + ts.reset();
1.143 + MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>,
1.144 + SageGraph::EdgeMap<int> >
1.145 + max_flow_test(hg, s, t, cm, flow);
1.146 + max_flow_test.run();
1.147 + cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
1.148 + << endl
1.149 + << "Size of matching: "
1.150 + << max_flow_test.flowValue() << endl;
1.151 + cout << "elapsed time: " << ts << endl << endl;
1.152 + }
1.153 +
1.154 + return 0;
1.155 +}