COIN-OR::LEMON - Graph Library

Changeset 197:fff43d9c7110 in lemon-0.x


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

.

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r196 r197  
    565565      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    566566        if (S->get(s)) {
    567           Number f=0;
     567          Number u=0;
    568568          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    569             f+=flow->get(e);
    570           if (f<1) {
     569            u+=flow->get(e);
     570          if (u<1) {
    571571            res_bfs.pushAndSetReached(s);
    572572            pred.set(s, AugEdge(INVALID));
     
    590590            free.set(w, res_graph.free(e));
    591591          }
    592           if (T->get(res_graph.head(e))) {
    593             n=res_graph.head(e);
    594             _augment=true;
    595             break;
     592          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) {
     598              _augment=true;
     599              break;
     600            }
    596601          }
    597602        }
     
    621626//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
    622627
    623 //       bfs.pushAndSetReached(s);
     628
     629
     630
     631
     632//       //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     633//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     634//      if (S->get(s)) {
     635//        Number u=0;
     636//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     637//          u+=flow->get(e);
     638//        if (u<1) {
     639//          res_bfs.pushAndSetReached(s);
     640//          //pred.set(s, AugEdge(INVALID));
     641//        }
     642//      }
     643//       }
     644
     645
     646
     647
     648//       //bfs.pushAndSetReached(s);
    624649//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    625650//       while ( !bfs.finished() ) {
     
    713738//       return _augment;
    714739//     }
    715 //     bool augmentOnBlockingFlow2() {
    716 //       bool _augment=false;
    717 
    718 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
    719 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
    720 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
    721 //       typedef typename EAugGraph::Edge EAugEdge;
    722 
    723 //       EAugGraph res_graph(*G, *flow, *capacity);
    724 
    725 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    726 //       BfsIterator4<
    727 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    728 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
    729 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    730      
    731 //       bfs.pushAndSetReached(s);
    732 
    733 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
    734 //      NodeMap<int>& dist=res_graph.dist;
    735 
    736 //       while ( !bfs.finished() ) {
    737 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    738 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    739 //        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    740 //      }
    741 //      ++bfs; 
    742 //       } //computing distances from s in the residual graph
    743 
    744 //       bool __augment=true;
    745 
    746 //       while (__augment) {
    747 
    748 //      __augment=false;
    749 //      //computing blocking flow with dfs
    750 //      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    751 //      DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
    752 //        dfs(res_graph);
    753 //      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
    754 //      pred.set(s, EAugEdge(INVALID));
    755 //      //invalid iterators for sources
    756 
    757 //      typename EAugGraph::NodeMap<Number> free(res_graph);
    758 
    759 //      dfs.pushAndSetReached(s);
    760 //      while (!dfs.finished()) {
    761 //        ++dfs;
    762 //        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
    763 //          if (dfs.isBNodeNewlyReached()) {
     740    bool augmentOnBlockingFlow2() {
     741      bool _augment=false;
     742
     743      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
     744      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     745      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
     746      typedef typename EAugGraph::Edge EAugEdge;
     747
     748      EAugGraph res_graph(*G, *flow, *capacity);
     749
     750      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
     751      BfsIterator4<
     752        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
     753        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
     754        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
     755
     756
     757      //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     758      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     759        if (S->get(s)) {
     760          Number u=0;
     761          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     762            u+=flow->get(e);
     763          if (u<1) {
     764            bfs.pushAndSetReached(s);
     765            //pred.set(s, AugEdge(INVALID));
     766          }
     767        }
     768      }
     769
     770     
     771      //bfs.pushAndSetReached(s);
     772
     773      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     774        NodeMap<int>& dist=res_graph.dist;
     775
     776      while ( !bfs.finished() ) {
     777        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     778        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     779          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     780        }
     781        ++bfs; 
     782      } //computing distances from s in the residual graph
     783
     784      bool __augment=true;
     785
     786      while (__augment) {
     787
     788        __augment=false;
     789        //computing blocking flow with dfs
     790        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
     791        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
     792          dfs(res_graph);
     793        typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
     794        //pred.set(s, EAugEdge(INVALID));
     795        //invalid iterators for sources
     796
     797        typename EAugGraph::NodeMap<Number> free(res_graph);
     798
     799
     800        //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     801      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     802        if (S->get(s)) {
     803          Number u=0;
     804          for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     805            u+=flow->get(e);
     806          if (u<1) {
     807            dfs.pushAndSetReached(s);
     808            //pred.set(s, AugEdge(INVALID));
     809          }
     810        }
     811      }
     812
     813
     814
     815      //dfs.pushAndSetReached(s);
     816      typename EAugGraph::Node n;
     817        while (!dfs.finished()) {
     818          ++dfs;
     819          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
     820            if (dfs.isBNodeNewlyReached()) {
    764821         
    765 //            typename EAugGraph::Node v=res_graph.aNode(dfs);
    766 //            typename EAugGraph::Node w=res_graph.bNode(dfs);
    767 
    768 //            pred.set(w, EAugOutEdgeIt(dfs));
    769 //            if (res_graph.valid(pred.get(v))) {
    770 //              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
    771 //            } else {
    772 //              free.set(w, res_graph.free(dfs));
    773 //            }
    774              
    775 //            if (w==t) {
    776 //              __augment=true;
    777 //              _augment=true;
    778 //              break;
    779 //            }
    780 //          } else {
    781 //            res_graph.erase(dfs);
    782 //          }
    783 //        }
    784 
    785 //      }
    786 
    787 //      if (__augment) {
    788 //        typename EAugGraph::Node n=t;
    789 //        Number augment_value=free.get(t);
    790 //        while (res_graph.valid(pred.get(n))) {
    791 //          EAugEdge e=pred.get(n);
    792 //          res_graph.augment(e, augment_value);
    793 //          n=res_graph.tail(e);
    794 //          if (res_graph.free(e)==0)
    795 //            res_graph.erase(e);
    796 //        }
    797 //      }
    798      
    799 //       }
     822              typename EAugGraph::Node v=res_graph.aNode(dfs);
     823              typename EAugGraph::Node w=res_graph.bNode(dfs);
     824
     825              pred.set(w, EAugOutEdgeIt(dfs));
     826              if (res_graph.valid(pred.get(v))) {
     827                free.set(w, std::min(free.get(v), res_graph.free(dfs)));
     828              } else {
     829                free.set(w, res_graph.free(dfs));
     830              }
     831             
     832              n=w;
     833              if (T->get(w)) {
     834                Number u=0;
     835                for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
     836                  u+=flow->get(f);
     837                if (u<1) {
     838                  __augment=true;
     839                  _augment=true;
     840                  break;
     841                }
     842              }
     843            } else {
     844              res_graph.erase(dfs);
     845            }
     846          }
     847
     848        }
     849
     850        if (__augment) {
     851          // typename EAugGraph::Node n=t;
     852          Number augment_value=free.get(n);
     853          while (res_graph.valid(pred.get(n))) {
     854            EAugEdge e=pred.get(n);
     855            res_graph.augment(e, augment_value);
     856            n=res_graph.tail(e);
     857            if (res_graph.free(e)==0)
     858              res_graph.erase(e);
     859          }
     860        }
     861     
     862      }
    800863           
    801 //       return _augment;
    802 //     }
     864      return _augment;
     865    }
    803866    void run() {
    804867      //int num_of_augmentations=0;
  • src/work/marci/max_bipartite_matching_demo.cc

    r196 r197  
    55#include <cstdlib>
    66
    7 //#include <LEDA/graph.h>
    8 //#include <leda_graph_wrapper.h>
     7#include <LEDA/graph.h>
     8#include <LEDA/mcb_matching.h>
     9#include <LEDA/list.h>
     10
     11#include <leda_graph_wrapper.h>
    912#include <list_graph.h>
    1013#include <dimacs.h>
     
    3740
    3841using std::cout;
     42using std::cin;
    3943using std::endl;
    4044
    4145int main() {
    42 //   leda::graph g;
    43 //   typedef LedaGraphWrapper<leda::graph> Graph;
    44 //   Graph G(g);
    45   typedef ListGraph Graph;
    46   Graph G;
     46   leda::graph g;
     47   typedef LedaGraphWrapper<leda::graph> Graph;
     48   Graph G(g);
     49//  typedef ListGraph Graph;
     50//  Graph G;
    4751
    4852  typedef Graph::Node Node;
     
    5963  std::vector<Node> t_nodes;
    6064
    61   for(int i=0; i<4; ++i) {
     65  int a;
     66  cout << "number of nodes in the first color class=";
     67  cin >> a;
     68  int b;
     69  cout << "number of nodes in the second color class=";
     70  cin >> b;
     71  int m;
     72  cout << "number of edges=";
     73  cin >> m;
     74 
     75
     76  for(int i=0; i<a; ++i) {
    6277    s_nodes.push_back(G.addNode());
    6378  }
    64   for(int i=0; i<4; ++i) {
     79  for(int i=0; i<a; ++i) {
    6580    t_nodes.push_back(G.addNode());
    6681  }
    6782  random_init();
    68   for(int i=0; i<6; ++i) {
    69     G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
    70   }
    71  
     83  for(int i=0; i<m; ++i) {
     84    G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
     85  }
     86 
     87//   G.addEdge(s_nodes[1], t_nodes[5-4]);
     88//   G.addEdge(s_nodes[1], t_nodes[5-4]);
     89//   G.addEdge(s_nodes[1], t_nodes[4-4]);
     90//   G.addEdge(s_nodes[1], t_nodes[4-4]);
    7291//   G.addEdge(s_nodes[2], t_nodes[4-4]);
    73 //   G.addEdge(s_nodes[2], t_nodes[7-4]);
    74 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
    75 //   G.addEdge(s_nodes[3], t_nodes[6-4]);
    76 //   G.addEdge(s_nodes[3], t_nodes[5-4]);
    77 //   G.addEdge(s_nodes[3], t_nodes[5-4]);
     92//   G.addEdge(s_nodes[3], t_nodes[4-4]);
    7893
    7994
     
    8196  Graph::NodeMap<bool> t_map(G); //false
    8297 
    83   for(int i=0; i<4; ++i) {
    84     s_map.set(s_nodes[i], true);
    85     t_map.set(t_nodes[i], true);
    86   }
    87 
    88   cout << "bfs and dfs iterator demo on the directed graph" << endl;
    89   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
    90     cout << G.id(n) << ": ";
    91     cout << "out edges: ";
    92     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
    93       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
    94     cout << "in edges: ";
    95     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
    96       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
    97     cout << endl;
    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);
     100
     101//   cout << "bfs and dfs iterator demo on the directed graph" << endl;
     102//   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
     103//     cout << G.id(n) << ": ";
     104//     cout << "out edges: ";
     105//     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
     106//       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
     107//     cout << "in edges: ";
     108//     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
     109//       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
     110//     cout << endl;
     111//   }
    99112
    100113
     
    108121
    109122    MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
    110     //max_flow_test.augmentWithBlockingFlow<Graph>();
    111123    int i=0;
    112124    while (max_flow_test.augmentOnShortestPath()) {
    113 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    114 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    115 //     }
    116 //     std::cout<<std::endl;
     125//       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     126//      std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     127//       std::cout<<std::endl;
    117128      ++i;
    118129    }
    119130
    120     std::cout << "maximum matching: "<< std::endl;
    121     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
    122       if (flow.get(e))
    123         std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
    124     std::cout<<std::endl;
    125     std::cout << "edges which are not in this maximum matching: "<< std::endl;
    126     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
    127       if (!flow.get(e))
    128         std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
    129     std::cout<<std::endl;
     131//     std::cout << "maximum matching: "<< std::endl;
     132//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     133//       if (flow.get(e))
     134//      std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     135//     std::cout<<std::endl;
     136//     std::cout << "edges which are not in this maximum matching: "<< std::endl;
     137//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     138//       if (!flow.get(e))
     139//      std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     140//     std::cout<<std::endl;
    130141   
    131142    std::cout << "elapsed time: " << ts << std::endl;
     
    133144    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    134145  }
     146
     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  }
     179
     180  {
     181    std::cout << "max bipartite matching (LEDA)..." << std::endl;
     182    //Graph::EdgeMap<int> flow(G); //0 flow
     183    //Graph::EdgeMap<int> cap(G, 1);
     184
     185    Timer ts;
     186    ts.reset();
     187
     188    //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
     189    //int i=0;
     190    //while (max_flow_test.augmentOnShortestPath()) { ++i; }
     191
     192    leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);   
     193   
     194
     195//     std::cout << "maximum matching: "<< std::endl;
     196//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     197//       if (flow.get(e))
     198//      std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     199//     std::cout<<std::endl;
     200//     std::cout << "edges which are not in this maximum matching: "<< std::endl;
     201//     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     202//       if (!flow.get(e))
     203//      std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     204//     std::cout<<std::endl;
     205   
     206   
     207    std::cout << "elapsed time: " << ts << std::endl;
     208    //std::cout << "number of augmentation phases: " << i << std::endl;
     209    std::cout << "flow value: "<< l.size() << std::endl;
     210  }
     211 
    135212 
    136213
Note: See TracChangeset for help on using the changeset viewer.