.
7 #include <LEDA/graph.h>
8 #include <leda_graph_wrapper.h>
10 #include <time_measure.h>
11 #include <edmonds_karp.h>
14 * Inicializalja a veletlenszamgeneratort.
15 * Figyelem, ez nem jo igazi random szamokhoz,
16 * erre ne bizzad a titkaidat!
20 unsigned int seed = getpid();
28 * Egy veletlen int-et ad vissza 0 es m-1 kozott.
32 return int( double(m) * rand() / (RAND_MAX + 1.0) );
42 typedef LedaGraphWrapper<leda::graph> Graph;
45 typedef Graph::Node Node;
46 typedef Graph::NodeIt NodeIt;
47 typedef Graph::Edge Edge;
48 typedef Graph::EdgeIt EdgeIt;
49 typedef Graph::OutEdgeIt OutEdgeIt;
50 typedef Graph::InEdgeIt InEdgeIt;
53 //Graph::EdgeMap<int> cap(G);
54 //readDimacsMaxFlow(std::cin, G, s, t, cap);
55 std::vector<Node> s_nodes;
56 std::vector<Node> t_nodes;
58 for(int i=0; i<4; ++i) {
59 s_nodes.push_back(G.addNode());
61 for(int i=0; i<4; ++i) {
62 t_nodes.push_back(G.addNode());
65 // for(int i=0; i<6; ++i) {
66 // G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
69 G.addEdge(s_nodes[2], t_nodes[4-4]);
70 G.addEdge(s_nodes[2], t_nodes[7-4]);
71 G.addEdge(s_nodes[2], t_nodes[4-4]);
72 G.addEdge(s_nodes[3], t_nodes[6-4]);
73 G.addEdge(s_nodes[3], t_nodes[5-4]);
74 G.addEdge(s_nodes[3], t_nodes[5-4]);
77 Graph::NodeMap<bool> s_map(G); //false
78 Graph::NodeMap<bool> t_map(G); //false
80 for(int i=0; i<4; ++i) {
81 s_map.set(s_nodes[i], true);
82 t_map.set(t_nodes[i], true);
85 cout << "bfs and dfs iterator demo on the directed graph" << endl;
86 for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
87 cout << G.id(n) << ": ";
88 cout << "out edges: ";
89 for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
90 cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
92 for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
93 cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
99 std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
100 Graph::EdgeMap<int> flow(G); //0 flow
101 Graph::EdgeMap<int> cap(G, 1);
106 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
107 //max_flow_test.augmentWithBlockingFlow<Graph>();
109 while (max_flow_test.augmentOnShortestPath()) {
110 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
111 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
113 // std::cout<<std::endl;
117 std::cout << "maximum matching: "<< std::endl;
118 for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
120 std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
121 std::cout<<std::endl;
122 std::cout << "edges which are not in this maximum matching: "<< std::endl;
123 for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))
125 std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
126 std::cout<<std::endl;
128 std::cout << "elapsed time: " << ts << std::endl;
129 std::cout << "number of augmentation phases: " << i << std::endl;
130 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;