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 <list_graph.h>
14 //#include <smart_graph.h>
16 #include <time_measure.h>
17 #include <for_each_macros.h>
18 //#include <bfs_iterator.h>
19 #include <graph_wrapper.h>
21 #include <edmonds_karp.h>
25 * Inicializalja a veletlenszamgeneratort.
26 * Figyelem, ez nem jo igazi random szamokhoz,
27 * erre ne bizzad a titkaidat!
31 unsigned int seed = getpid();
39 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
43 return int( double(m) * rand() / (RAND_MAX + 1.0) );
51 //lg.make_undirected();
52 typedef LedaGraphWrapper<leda::graph> Graph;
56 //typedef UndirListGraph Graph;
59 typedef Graph::Node Node;
60 typedef Graph::NodeIt NodeIt;
61 typedef Graph::Edge Edge;
62 typedef Graph::EdgeIt EdgeIt;
63 typedef Graph::OutEdgeIt OutEdgeIt;
65 std::vector<Graph::Node> s_nodes;
66 std::vector<Graph::Node> t_nodes;
69 std::cout << "number of nodes in the first color class=";
72 std::cout << "number of nodes in the second color class=";
75 std::cout << "number of edges=";
78 std::cout << "number of groups in LEDA random group graph=";
81 leda_list<leda_node> lS;
82 leda_list<leda_node> lT;
83 random_bigraph(lg, a, b, m, lS, lT, k);
85 // for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
86 // for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
89 // for(int i=0; i<m; ++i) {
90 // g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
93 Graph::NodeMap<int> ref_map(g, -1);
95 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
96 // for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
97 // for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
99 forall(ln, lS) bipartite_map.insert(ln, false);
100 forall(ln, lT) bipartite_map.insert(ln, true);
102 typedef BipartiteGraphWrapper<Graph> BGW;
103 BGW bgw(g, bipartite_map);
105 // BGW::NodeMap<int> dbyj(bgw);
106 // BGW::EdgeMap<int> dbyxcj(bgw);
108 typedef stGraphWrapper<BGW> stGW;
110 ConstMap<stGW::Edge, int> const1map(1);
111 stGW::EdgeMap<int> flow(stgw);
114 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
116 // stGW::EdgeMap<int> pre_flow(stgw);
117 Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
118 pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow, true);
120 std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl;
121 std::cout << "elapsed time: " << ts << std::endl;
122 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
123 // std::cout << e << ": " << pre_flow[e] << "\n";
128 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
129 // stGW::EdgeMap<int> pre_flow(stgw);
130 //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
131 // pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
132 //pre_flow_test.run();
133 std::cout << "LEDA matching value: " << ml.size() << std::endl;
134 std::cout << "elapsed time: " << ts << std::endl;
135 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
136 // std::cout << e << ": " << pre_flow[e] << "\n";
140 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
142 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
143 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
144 // while (max_flow_test.augmentOnShortestPath()) { }
145 typedef ListGraph MutableGraph;
146 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
147 while (max_flow_test.augmentOnBlockingFlow2()) {
148 std::cout << max_flow_test.flowValue() << std::endl;
150 std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl;
151 std::cout << "elapsed time: " << ts << std::endl;
152 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
153 // std::cout << e << ": " << max_flow[e] << "\n";
155 // std::cout << "\n";