Changeset 769:eb61fbc64c16 in lemon-0.x for src

Timestamp:

08/23/04 13:26:09 (20 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:

• bipartite_matching_leda.cc (modified) (3 diffs)
• bipartite_matching_leda_gen.cc (modified) (2 diffs)
• comparison.cc (modified) (5 diffs)

src/work/marci/leda/bipartite_matching_leda.cc

@@ -15 +15 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
-#include <hugo/for_each_macros.h>
+#include <for_each_macros.h>
 #include <hugo/graph_wrapper.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
-#include <max_flow.h>
+#include <hugo/max_flow.h>
 
 /**
@@ -96 +96 @@
   BGW::EdgeMap<int> dbyxcj(bgw);
 
-  typedef stGraphWrapper<BGW> stGW;
+  typedef stBipartiteGraphWrapper<BGW> stGW;
   stGW stgw(bgw);
   ConstMap<stGW::Edge, int> const1map(1);
@@ -110 +110 @@
   typedef SageGraph MutableGraph;
 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
-  while (max_flow_test.augmentOnBlockingFlow2()) {
-   std::cout << max_flow_test.flowValue() << std::endl;
-  }
+//   while (max_flow_test.augmentOnBlockingFlow2()) {
+//    std::cout << max_flow_test.flowValue() << std::endl;
+//   }
+  max_flow_test.run();
   std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
   std::cout << "elapsed time: " << ts << std::endl;

src/work/marci/leda/bipartite_matching_leda_gen.cc

@@ -15 +15 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
-#include <hugo/for_each_macros.h>
+#include <for_each_macros.h>
 #include <hugo/graph_wrapper.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
-#include <max_flow.h>
+#include <hugo/max_flow.h>
+#include <augmenting_flow.h>
 
 /**
@@ -126 +127 @@
   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
   typedef SageGraph MutableGraph;
-  while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
+  AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
+    max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
+  while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
   std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 
             << std::endl << "Matching size: " 
-            << max_flow_test.flowValue() << std::endl;
+            << max_flow_test_1.flowValue() << std::endl;
   std::cout << "elapsed time: " << ts << std::endl;
 

src/work/marci/leda/comparison.cc

@@ -15 +15 @@
 //#include <dimacs.h>
 #include <hugo/time_measure.h>
-#include <hugo/for_each_macros.h>
+#include <for_each_macros.h>
 #include <hugo/graph_wrapper.h>
 #include <bipartite_graph_wrapper.h>
 #include <hugo/maps.h>
-#include <max_flow.h>
+#include <hugo/max_flow.h>
 
-/**
- * Inicializalja a veletlenszamgeneratort.
- * Figyelem, ez nem jo igazi random szamokhoz,
- * erre ne bizzad a titkaidat!
- */
-void random_init()
-{
-        unsigned int seed = getpid();
-        seed |= seed << 15;
-        seed ^= time(0);
-
-        srand(seed);
-}
-
-/**
- * Egy veletlen int-et ad vissza 0 es m-1 kozott.
- */
-int random(int m)
-{
-  return int( double(m) * rand() / (RAND_MAX + 1.0) );
-}
+using std::cout;
+using std::endl;
 
 using namespace hugo;
@@ -66 +47 @@
 
   int a;
-  std::cout << "number of nodes in the first color class=";
+  cout << "number of nodes in the first color class=";
   std::cin >> a; 
   int b;
-  std::cout << "number of nodes in the second color class=";
+  cout << "number of nodes in the second color class=";
   std::cin >> b; 
   int m;
-  std::cout << "number of edges=";
+  cout << "number of edges=";
   std::cin >> m; 
   int k;
-  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";
-  std::cout << "number of groups in LEDA random group graph=";
+  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";
+  cout << "number of groups in LEDA random group graph=";
   std::cin >> k; 
-  std::cout << std::endl;
+  cout << endl;
   
   leda_list<leda_node> lS;
@@ -110 +91 @@
     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
   max_flow_test.run();
-  std::cout << "HUGO max matching algorithm based on preflow." << std::endl 
+  cout << "HUGO max matching algorithm based on preflow." << endl 
             << "Size of matching: " 
-            << max_flow_test.flowValue() << std::endl;
-  std::cout << "elapsed time: " << ts << std::endl << std::endl;
+            << max_flow_test.flowValue() << endl;
+  cout << "elapsed time: " << ts << endl << endl;
 
   ts.reset();  
   leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
-  std::cout << "LEDA max matching algorithm." << std::endl 
+  cout << "LEDA max matching algorithm." << endl 
             << "Size of matching: " 
-            << ml.size() << std::endl;
-  std::cout << "elapsed time: " << ts << std::endl << std::endl;
+            << ml.size() << endl;
+  cout << "elapsed time: " << ts << endl << endl;
 
 //   ts.reset();
@@ -126 +107 @@
 //   typedef SageGraph MutableGraph;
 //   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
-//   std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 
-//          << std::endl << "Matching size: " 
-//          << max_flow_test.flowValue() << std::endl;
-//   std::cout << "elapsed time: " << ts << std::endl << std::endl;
+//   cout << "HUGO max matching algorithm based on blocking flow augmentation." 
+//          << endl << "Matching size: " 
+//          << max_flow_test.flowValue() << endl;
+//   cout << "elapsed time: " << ts << endl << endl;
 
   {
@@ -160 +141 @@
     max_flow_test(hg, s, t, cm, flow);
   max_flow_test.run();
-  std::cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow." 
-            << std::endl 
+  cout << "HUGO max matching algorithm on SageGraph by copying the graph, based on preflow." 
+            << endl 
             << "Size of matching: " 
-            << max_flow_test.flowValue() << std::endl;
-  std::cout << "elapsed time: " << ts << std::endl << std::endl;
+            << max_flow_test.flowValue() << endl;
+  cout << "elapsed time: " << ts << endl << endl;
   }