Changeset 195:19f8bd411014 in lemon-0.x for src/work
- Timestamp:
- 03/17/04 16:41:00 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@272
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/max_bipartite_matching_demo.cc
r194 r195 56 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 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 62 t_nodes.push_back(G.addNode()); 63 63 } 64 random_init(); 65 for(int i=0; i<50; ++i) { 66 G.addEdge(s_nodes[random(20)], t_nodes[random(20)]); 67 } 64 // random_init(); 65 // for(int i=0; i<6; ++i) { 66 // G.addEdge(s_nodes[random(4)], t_nodes[random(4)]); 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 77 Graph::NodeMap<bool> s_map(G); //false 69 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 81 s_map.set(s_nodes[i], true); 73 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 { … … 93 115 } 94 116 95 // std::cout << "maximum flow: "<< std::endl; 96 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 97 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 98 // } 99 // std::cout<<std::endl; 117 std::cout << "maximum matching: "<< std::endl; 118 for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 119 if (flow.get(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)) 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 128 std::cout << "elapsed time: " << ts << std::endl; 101 129 std::cout << "number of augmentation phases: " << i << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.