COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
03/17/04 19:18:26 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@275
Message:

max cardinality bipartite matching demo, something to play with it

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/max_bipartite_matching_demo.cc

    r197 r198  
    9292//   G.addEdge(s_nodes[3], t_nodes[4-4]);
    9393
    94 
     94  leda_list<leda_node> A;
     95  leda_list<leda_node> B;
    9596  Graph::NodeMap<bool> s_map(G); //false
    9697  Graph::NodeMap<bool> t_map(G); //false
    9798 
    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]; }
    100101
    101102//   cout << "bfs and dfs iterator demo on the directed graph" << endl;
     
    113114
    114115  {
    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;
    116117    Graph::EdgeMap<int> flow(G); //0 flow
    117118    Graph::EdgeMap<int> cap(G, 1);
     
    145146  }
    146147
    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 flow
    150     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//   }
    179180
    180181  {
     
    183184    //Graph::EdgeMap<int> cap(G, 1);
    184185
     186    leda_node_array<bool> NC(g);
     187
    185188    Timer ts;
    186189    ts.reset();
     
    189192    //int i=0;
    190193    //while (max_flow_test.augmentOnShortestPath()) { ++i; }
    191 
     194   
     195    //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false);
    192196    leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);   
    193197   
Note: See TracChangeset for help on using the changeset viewer.