47 typedef Graph::Edge Edge; |
47 typedef Graph::Edge Edge; |
48 typedef Graph::EdgeIt EdgeIt; |
48 typedef Graph::EdgeIt EdgeIt; |
49 typedef Graph::OutEdgeIt OutEdgeIt; |
49 typedef Graph::OutEdgeIt OutEdgeIt; |
50 typedef Graph::InEdgeIt InEdgeIt; |
50 typedef Graph::InEdgeIt InEdgeIt; |
51 |
51 |
52 Node s, t; |
52 //Node s, t; |
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 |
63 } |
63 } |
64 random_init(); |
64 random_init(); |
65 for(int i=0; i<50; ++i) { |
65 for(int i=0; i<50; ++i) { |
66 G.addEdge(s_nodes[random(20)], t_nodes[random(20)]); |
66 G.addEdge(s_nodes[random(20)], t_nodes[random(20)]); |
67 } |
67 } |
68 Graph::NodeMap<bool> s_map; //false |
68 Graph::NodeMap<bool> s_map(G); //false |
69 Graph::NodeMap<bool> t_map; //false |
69 Graph::NodeMap<bool> t_map(G); //false |
70 |
70 |
71 for(int i=0; i<20; ++i) { |
71 for(int i=0; i<20; ++i) { |
72 s_map.set(s_nodes[i], true); |
72 s_map.set(s_nodes[i], true); |
73 t_map.set(t_nodes[i], true); |
73 t_map.set(t_nodes[i], true); |
74 } |
74 } |
75 |
75 |
76 { |
76 { |
77 std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl; |
77 std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl; |
78 Graph::EdgeMap<int> flow(G); //0 flow |
78 Graph::EdgeMap<int> flow(G); //0 flow |
79 Graph::EdgeMap<int> capacity(G, 1); |
79 Graph::EdgeMap<int> cap(G, 1); |
80 |
80 |
81 Timer ts; |
81 Timer ts; |
82 ts.reset(); |
82 ts.reset(); |
83 |
83 |
84 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |
84 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); |