COIN-OR::LEMON - Graph Library

Changeset 769:eb61fbc64c16 in lemon-0.x


Ignore:
Timestamp:
08/23/04 13:26:09 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1032
Message:

.

Location:
src/work/marci/leda
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/leda/bipartite_matching_leda.cc

    r648 r769  
    1515//#include <dimacs.h>
    1616#include <hugo/time_measure.h>
    17 #include <hugo/for_each_macros.h>
     17#include <for_each_macros.h>
    1818#include <hugo/graph_wrapper.h>
    1919#include <bipartite_graph_wrapper.h>
    2020#include <hugo/maps.h>
    21 #include <max_flow.h>
     21#include <hugo/max_flow.h>
    2222
    2323/**
     
    9696  BGW::EdgeMap<int> dbyxcj(bgw);
    9797
    98   typedef stGraphWrapper<BGW> stGW;
     98  typedef stBipartiteGraphWrapper<BGW> stGW;
    9999  stGW stgw(bgw);
    100100  ConstMap<stGW::Edge, int> const1map(1);
     
    110110  typedef SageGraph MutableGraph;
    111111//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    112   while (max_flow_test.augmentOnBlockingFlow2()) {
    113    std::cout << max_flow_test.flowValue() << std::endl;
    114   }
     112//   while (max_flow_test.augmentOnBlockingFlow2()) {
     113//    std::cout << max_flow_test.flowValue() << std::endl;
     114//   }
     115  max_flow_test.run();
    115116  std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    116117  std::cout << "elapsed time: " << ts << std::endl;
  • src/work/marci/leda/bipartite_matching_leda_gen.cc

    r768 r769  
    1515//#include <dimacs.h>
    1616#include <hugo/time_measure.h>
    17 #include <hugo/for_each_macros.h>
     17#include <for_each_macros.h>
    1818#include <hugo/graph_wrapper.h>
    1919#include <bipartite_graph_wrapper.h>
    2020#include <hugo/maps.h>
    21 #include <max_flow.h>
     21#include <hugo/max_flow.h>
     22#include <augmenting_flow.h>
    2223
    2324/**
     
    126127  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    127128  typedef SageGraph MutableGraph;
    128   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
     129  AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
     130    max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
     131  while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
    129132  std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
    130133            << std::endl << "Matching size: "
    131             << max_flow_test.flowValue() << std::endl;
     134            << max_flow_test_1.flowValue() << std::endl;
    132135  std::cout << "elapsed time: " << ts << std::endl;
    133136
  • src/work/marci/leda/comparison.cc

    r768 r769  
    1515//#include <dimacs.h>
    1616#include <hugo/time_measure.h>
    17 #include <hugo/for_each_macros.h>
     17#include <for_each_macros.h>
    1818#include <hugo/graph_wrapper.h>
    1919#include <bipartite_graph_wrapper.h>
    2020#include <hugo/maps.h>
    21 #include <max_flow.h>
     21#include <hugo/max_flow.h>
    2222
    23 /**
    24  * Inicializalja a veletlenszamgeneratort.
    25  * Figyelem, ez nem jo igazi random szamokhoz,
    26  * erre ne bizzad a titkaidat!
    27  */
    28 void random_init()
    29 {
    30         unsigned int seed = getpid();
    31         seed |= seed << 15;
    32         seed ^= time(0);
    33 
    34         srand(seed);
    35 }
    36 
    37 /**
    38  * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    39  */
    40 int random(int m)
    41 {
    42   return int( double(m) * rand() / (RAND_MAX + 1.0) );
    43 }
     23using std::cout;
     24using std::endl;
    4425
    4526using namespace hugo;
     
    6647
    6748  int a;
    68   std::cout << "number of nodes in the first color class=";
     49  cout << "number of nodes in the first color class=";
    6950  std::cin >> a;
    7051  int b;
    71   std::cout << "number of nodes in the second color class=";
     52  cout << "number of nodes in the second color class=";
    7253  std::cin >> b;
    7354  int m;
    74   std::cout << "number of edges=";
     55  cout << "number of edges=";
    7556  std::cin >> m;
    7657  int k;
    77   std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
    78   std::cout << "number of groups in LEDA random group graph=";
     58  cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
     59  cout << "number of groups in LEDA random group graph=";
    7960  std::cin >> k;
    80   std::cout << std::endl;
     61  cout << endl;
    8162 
    8263  leda_list<leda_node> lS;
     
    11091    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    11192  max_flow_test.run();
    112   std::cout << "HUGO max matching algorithm based on preflow." << std::endl
     93  cout << "HUGO max matching algorithm based on preflow." << endl
    11394            << "Size of matching: "
    114             << max_flow_test.flowValue() << std::endl;
    115   std::cout << "elapsed time: " << ts << std::endl << std::endl;
     95            << max_flow_test.flowValue() << endl;
     96  cout << "elapsed time: " << ts << endl << endl;
    11697
    11798  ts.reset(); 
    11899  leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
    119   std::cout << "LEDA max matching algorithm." << std::endl
     100  cout << "LEDA max matching algorithm." << endl
    120101            << "Size of matching: "
    121             << ml.size() << std::endl;
    122   std::cout << "elapsed time: " << ts << std::endl << std::endl;
     102            << ml.size() << endl;
     103  cout << "elapsed time: " << ts << endl << endl;
    123104
    124105//   ts.reset();
     
    126107//   typedef SageGraph MutableGraph;
    127108//   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
    128 //   std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
    129 //          << std::endl << "Matching size: "
    130 //          << max_flow_test.flowValue() << std::endl;
    131 //   std::cout << "elapsed time: " << ts << std::endl << std::endl;
     109//   cout << "HUGO max matching algorithm based on blocking flow augmentation."
     110//          << endl << "Matching size: "
     111//          << max_flow_test.flowValue() << endl;
     112//   cout << "elapsed time: " << ts << endl << endl;
    132113
    133114  {
     
    160141    max_flow_test(hg, s, t, cm, flow);
    161142  max_flow_test.run();
    162   std::cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
    163             << std::endl
     143  cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow."
     144            << endl
    164145            << "Size of matching: "
    165             << max_flow_test.flowValue() << std::endl;
    166   std::cout << "elapsed time: " << ts << std::endl << std::endl;
     146            << max_flow_test.flowValue() << endl;
     147  cout << "elapsed time: " << ts << endl << endl;
    167148  }
    168149
Note: See TracChangeset for help on using the changeset viewer.