Changeset 198:5cec393baade in lemon-0.x for src/work/marci
- Timestamp:
- 03/17/04 19:18:26 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@275
- Location:
- src/work/marci
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified src/work/marci/leda_graph_wrapper.h ¶
r189 r198 71 71 bool operator==(Node n) const { return _n==n._n; } //FIXME 72 72 bool operator!=(Node n) const { return _n!=n._n; } //FIXME 73 operator leda_node () { return _n; } 73 74 }; 74 75 … … 101 102 //Edge(const Edge &) {} 102 103 bool operator==(Edge e) const { return _e==e._e; } //FIXME 103 bool operator!=(Edge e) const { return _e!=e._e; } //FIXME 104 bool operator!=(Edge e) const { return _e!=e._e; } //FIXME 105 operator leda_edge () { return _e; } 104 106 }; 105 107 -
TabularUnified src/work/marci/max_bipartite_matching_demo.cc ¶
r197 r198 92 92 // G.addEdge(s_nodes[3], t_nodes[4-4]); 93 93 94 94 leda_list<leda_node> A; 95 leda_list<leda_node> B; 95 96 Graph::NodeMap<bool> s_map(G); //false 96 97 Graph::NodeMap<bool> t_map(G); //false 97 98 98 for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true);99 for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true);99 for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; } 100 for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; } 100 101 101 102 // cout << "bfs and dfs iterator demo on the directed graph" << endl; … … 113 114 114 115 { 115 std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;116 std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl; 116 117 Graph::EdgeMap<int> flow(G); //0 flow 117 118 Graph::EdgeMap<int> cap(G, 1); … … 145 146 } 146 147 147 {148 std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;149 Graph::EdgeMap<int> flow(G); //0 flow150 Graph::EdgeMap<int> cap(G, 1);151 152 Timer ts;153 ts.reset();154 155 MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);156 int i=0;157 while (max_flow_test.augmentOnBlockingFlow2()) {158 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))159 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";160 // std::cout<<std::endl;161 ++i;162 }163 164 // std::cout << "maximum matching: "<< std::endl;165 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))166 // if (flow.get(e))167 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";168 // std::cout<<std::endl;169 // std::cout << "edges which are not in this maximum matching: "<< std::endl;170 // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))171 // if (!flow.get(e))172 // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";173 // std::cout<<std::endl;174 175 std::cout << "elapsed time: " << ts << std::endl;176 std::cout << "number of augmentation phases: " << i << std::endl;177 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;178 }148 // { 149 // std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl; 150 // Graph::EdgeMap<int> flow(G); //0 flow 151 // Graph::EdgeMap<int> cap(G, 1); 152 153 // Timer ts; 154 // ts.reset(); 155 156 // MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap); 157 // int i=0; 158 // while (max_flow_test.augmentOnBlockingFlow2()) { 159 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 160 // // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; 161 // // std::cout<<std::endl; 162 // ++i; 163 // } 164 165 // // std::cout << "maximum matching: "<< std::endl; 166 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 167 // // if (flow.get(e)) 168 // // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; 169 // // std::cout<<std::endl; 170 // // std::cout << "edges which are not in this maximum matching: "<< std::endl; 171 // // for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 172 // // if (!flow.get(e)) 173 // // std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " "; 174 // // std::cout<<std::endl; 175 176 // std::cout << "elapsed time: " << ts << std::endl; 177 // std::cout << "number of augmentation phases: " << i << std::endl; 178 // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 179 // } 179 180 180 181 { … … 183 184 //Graph::EdgeMap<int> cap(G, 1); 184 185 186 leda_node_array<bool> NC(g); 187 185 188 Timer ts; 186 189 ts.reset(); … … 189 192 //int i=0; 190 193 //while (max_flow_test.augmentOnShortestPath()) { ++i; } 191 194 195 //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false); 192 196 leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g); 193 197
Note: See TracChangeset
for help on using the changeset viewer.