7 #include <LEDA/graph.h>
8 #include <LEDA/mcb_matching.h>
10 #include <LEDA/graph_gen.h>
12 #include <leda_graph_wrapper.h>
13 #include <sage_graph.h>
14 //#include <smart_graph.h>
16 #include <hugo/time_measure.h>
17 #include <hugo/for_each_macros.h>
18 #include <hugo/graph_wrapper.h>
19 #include <bipartite_graph_wrapper.h>
20 #include <hugo/maps.h>
24 * Inicializalja a veletlenszamgeneratort.
25 * Figyelem, ez nem jo igazi random szamokhoz,
26 * erre ne bizzad a titkaidat!
30 unsigned int seed = getpid();
38 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
42 return int( double(m) * rand() / (RAND_MAX + 1.0) );
50 //lg.make_undirected();
51 typedef LedaGraphWrapper<leda::graph> Graph;
55 //typedef UndirSageGraph Graph;
58 typedef Graph::Node Node;
59 typedef Graph::NodeIt NodeIt;
60 typedef Graph::Edge Edge;
61 typedef Graph::EdgeIt EdgeIt;
62 typedef Graph::OutEdgeIt OutEdgeIt;
64 std::vector<Graph::Node> s_nodes;
65 std::vector<Graph::Node> t_nodes;
68 std::cout << "number of nodes in the first color class=";
71 std::cout << "number of nodes in the second color class=";
74 std::cout << "number of edges=";
77 std::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";
78 std::cout << "number of groups in LEDA random group graph=";
80 std::cout << std::endl;
82 leda_list<leda_node> lS;
83 leda_list<leda_node> lT;
84 random_bigraph(lg, a, b, m, lS, lT, k);
86 Graph::NodeMap<int> ref_map(g, -1);
87 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
89 //generating leda random group graph
91 forall(ln, lS) bipartite_map.insert(ln, false);
92 forall(ln, lT) bipartite_map.insert(ln, true);
94 //making bipartite graph
95 typedef BipartiteGraphWrapper<Graph> BGW;
96 BGW bgw(g, bipartite_map);
100 typedef stBipartiteGraphWrapper<BGW> stGW;
102 ConstMap<stGW::Edge, int> const1map(1);
103 stGW::EdgeMap<int> flow(stgw);
108 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
109 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
110 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
112 std::cout << "HUGO max matching algorithm based on preflow." << std::endl
113 << "Size of matching: "
114 << max_flow_test.flowValue() << std::endl;
115 std::cout << "elapsed time: " << ts << std::endl << std::endl;
118 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
119 std::cout << "LEDA max matching algorithm." << std::endl
120 << "Size of matching: "
121 << ml.size() << std::endl;
122 std::cout << "elapsed time: " << ts << std::endl;
126 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
127 typedef SageGraph MutableGraph;
128 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
129 std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
130 << std::endl << "Matching size: "
131 << max_flow_test.flowValue() << std::endl;
132 std::cout << "elapsed time: " << ts << std::endl;