COIN-OR::LEMON - Graph Library

Changeset 198:5cec393baade in lemon-0.x


Ignore:
Timestamp:
03/17/04 19:18:26 (16 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

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r197 r198  
    552552    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    553553    typedef typename AugGraph::Edge AugEdge;
     554    typename Graph::NodeMap<int> used; //0
    554555
    555556  public:
    556557    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
    557       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
     558      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
    558559    bool augmentOnShortestPath() {
    559560      AugGraph res_graph(*G, *flow, *capacity);
     
    564565      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    565566      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    566         if (S->get(s)) {
    567           Number u=0;
    568           for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    569             u+=flow->get(e);
    570           if (u<1) {
     567        if ((S->get(s)) && (used.get(s)<1) ) {
     568          //Number u=0;
     569          //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     570          //u+=flow->get(e);
     571          //if (u<1) {
    571572            res_bfs.pushAndSetReached(s);
    572573            pred.set(s, AugEdge(INVALID));
    573           }
     574            //}
    574575        }
    575576      }
     
    591592          }
    592593          n=res_graph.head(e);
    593           if (T->get(n)) {
    594             Number u=0;
    595             for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    596               u+=flow->get(f);
    597             if (u<1) {
     594          if (T->get(n) && (used.get(n)<1) ) {
     595            //Number u=0;
     596            //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
     597            //u+=flow->get(f);
     598            //if (u<1) {
    598599              _augment=true;
    599600              break;
    600             }
     601              //}
    601602          }
    602603        }
     
    607608      if (_augment) {
    608609        //Node n=t;
     610        used.set(n, 1); //mind2 vegen jav
    609611        Number augment_value=free.get(n);
    610612        while (res_graph.valid(pred.get(n))) {
     
    613615          n=res_graph.tail(e);
    614616        }
     617        used.set(n, 1); //mind2 vegen jav
    615618      }
    616619
  • src/work/marci/leda_graph_wrapper.h

    r189 r198  
    7171      bool operator==(Node n) const { return _n==n._n; } //FIXME
    7272      bool operator!=(Node n) const { return _n!=n._n; } //FIXME
     73      operator leda_node () { return _n; }
    7374    };
    7475   
     
    101102      //Edge(const Edge &) {}
    102103      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; }
    104106    };
    105107   
  • 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.