1.1 --- a/src/work/marci/leda/comparison.cc Mon Aug 23 11:28:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,152 +0,0 @@
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 -}