53 //Graph::EdgeMap<int> cap(G); |
53 //Graph::EdgeMap<int> cap(G); |
54 //readDimacsMaxFlow(std::cin, G, s, t, cap); |
54 //readDimacsMaxFlow(std::cin, G, s, t, cap); |
55 std::vector<Node> s_nodes; |
55 std::vector<Node> s_nodes; |
56 std::vector<Node> t_nodes; |
56 std::vector<Node> t_nodes; |
57 |
57 |
58 for(int i=0; i<20; ++i) { |
58 for(int i=0; i<4; ++i) { |
59 s_nodes.push_back(G.addNode()); |
59 s_nodes.push_back(G.addNode()); |
60 } |
60 } |
61 for(int i=0; i<20; ++i) { |
61 for(int i=0; i<4; ++i) { |
62 t_nodes.push_back(G.addNode()); |
62 t_nodes.push_back(G.addNode()); |
63 } |
63 } |
64 random_init(); |
64 // random_init(); |
65 for(int i=0; i<50; ++i) { |
65 // for(int i=0; i<6; ++i) { |
66 G.addEdge(s_nodes[random(20)], t_nodes[random(20)]); |
66 // G.addEdge(s_nodes[random(4)], t_nodes[random(4)]); |
67 } |
67 // } |
|
68 |
|
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]); |
|
75 |
|
76 |
68 Graph::NodeMap<bool> s_map(G); //false |
77 Graph::NodeMap<bool> s_map(G); //false |
69 Graph::NodeMap<bool> t_map(G); //false |
78 Graph::NodeMap<bool> t_map(G); //false |
70 |
79 |
71 for(int i=0; i<20; ++i) { |
80 for(int i=0; i<4; ++i) { |
72 s_map.set(s_nodes[i], true); |
81 s_map.set(s_nodes[i], true); |
73 t_map.set(t_nodes[i], true); |
82 t_map.set(t_nodes[i], true); |
74 } |
83 } |
|
84 |
|
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)) << " "; |
|
91 cout << "in edges: "; |
|
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)) << " "; |
|
94 cout << endl; |
|
95 } |
|
96 |
75 |
97 |
76 { |
98 { |
77 std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl; |
99 std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl; |
78 Graph::EdgeMap<int> flow(G); //0 flow |
100 Graph::EdgeMap<int> flow(G); //0 flow |
79 Graph::EdgeMap<int> cap(G, 1); |
101 Graph::EdgeMap<int> cap(G, 1); |
90 // } |
112 // } |
91 // std::cout<<std::endl; |
113 // std::cout<<std::endl; |
92 ++i; |
114 ++i; |
93 } |
115 } |
94 |
116 |
95 // std::cout << "maximum flow: "<< std::endl; |
117 std::cout << "maximum matching: "<< std::endl; |
96 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { |
118 for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) |
97 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
119 if (flow.get(e)) |
98 // } |
120 std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
99 // std::cout<<std::endl; |
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)) |
|
124 if (!flow.get(e)) |
|
125 std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; |
|
126 std::cout<<std::endl; |
|
127 |
100 std::cout << "elapsed time: " << ts << std::endl; |
128 std::cout << "elapsed time: " << ts << std::endl; |
101 std::cout << "number of augmentation phases: " << i << std::endl; |
129 std::cout << "number of augmentation phases: " << i << std::endl; |
102 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
130 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
103 } |
131 } |
104 |
132 |