DirPath fejlodes.
Kiserleti struktura a forditasi idoben kapcsolhato konzisztencia es range
ellenorzesekre.
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 <graph_wrapper.h>
23 * Inicializalja a veletlenszamgeneratort.
24 * Figyelem, ez nem jo igazi random szamokhoz,
25 * erre ne bizzad a titkaidat!
29 unsigned int seed = getpid();
37 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
41 return int( double(m) * rand() / (RAND_MAX + 1.0) );
49 //lg.make_undirected();
50 typedef LedaGraphWrapper<leda::graph> Graph;
54 //typedef UndirListGraph Graph;
57 typedef Graph::Node Node;
58 typedef Graph::NodeIt NodeIt;
59 typedef Graph::Edge Edge;
60 typedef Graph::EdgeIt EdgeIt;
61 typedef Graph::OutEdgeIt OutEdgeIt;
63 std::vector<Graph::Node> s_nodes;
64 std::vector<Graph::Node> t_nodes;
67 std::cout << "number of nodes in the first color class=";
70 std::cout << "number of nodes in the second color class=";
73 std::cout << "number of edges=";
76 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";
77 std::cout << "number of groups in LEDA random group graph=";
79 std::cout << std::endl;
81 leda_list<leda_node> lS;
82 leda_list<leda_node> lT;
83 random_bigraph(lg, a, b, m, lS, lT, k);
85 Graph::NodeMap<int> ref_map(g, -1);
86 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
88 //generating leda random group graph
90 forall(ln, lS) bipartite_map.insert(ln, false);
91 forall(ln, lT) bipartite_map.insert(ln, true);
93 //making bipartite graph
94 typedef BipartiteGraphWrapper<Graph> BGW;
95 BGW bgw(g, bipartite_map);
99 typedef stGraphWrapper<BGW> stGW;
101 ConstMap<stGW::Edge, int> const1map(1);
102 stGW::EdgeMap<int> flow(stgw);
107 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
108 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
109 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
111 std::cout << "HUGO max matching algorithm based on preflow." << std::endl
112 << "Size of matching: "
113 << max_flow_test.flowValue() << std::endl;
114 std::cout << "elapsed time: " << ts << std::endl << std::endl;
117 leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
118 std::cout << "LEDA max matching algorithm." << std::endl
119 << "Size of matching: "
120 << ml.size() << std::endl;
121 std::cout << "elapsed time: " << ts << std::endl;
125 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
126 typedef ListGraph MutableGraph;
127 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
128 std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
129 << std::endl << "Matching size: "
130 << max_flow_test.flowValue() << std::endl;
131 std::cout << "elapsed time: " << ts << std::endl;