Changeset 775:e46a1f0623a0 in lemon-0.x for src/work

Timestamp:

08/31/04 13:26:59 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1068

Message:

ResGraphWrapper?<Graph> is done, so does dimacs.h.

Location:

src/work/marci

Files:

• augmenting_flow.h (modified) (16 diffs)
• makefile (modified) (1 diff)
• max_flow_demo.cc (modified) (3 diffs)

src/work/marci/augmenting_flow.h

@@ -1021 +1021 @@
       case AFTER_AUGMENTING:
 //      std::cout << "AFTER_AUGMENTING" << std::endl;
-        for(g->first(v); g->valid(v); g->next(v)) {
+        for(g->first(v); v!=INVALID; ++v) {
           if (level[v]) {
             M.set(v, true);
@@ -1031 +1031 @@
       case AFTER_FAST_AUGMENTING:
 //      std::cout << "AFTER_FAST_AUGMENTING" << std::endl;
-        for(g->first(v); g->valid(v); g->next(v)) {
+        for(g->first(v); v!=INVALID; ++v) {
           if (level[v]==number_of_augmentations) {
             M.set(v, true);
@@ -1054 +1054 @@
 
         OutEdgeIt e;
-        for(g->first(e,w) ; g->valid(e); g->next(e)) {
+        for(g->first(e,w) ; e!=INVALID; ++e) {
           Node v=g->head(e);
           if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
@@ -1063 +1063 @@
 
         InEdgeIt f;
-        for(g->first(f,w) ; g->valid(f); g->next(f)) {
+        for(g->first(f,w) ; f!=INVALID; ++f) {
           Node v=g->tail(f);
           if (!M[v] && (*flow)[f] > 0 ) {
@@ -1134 +1134 @@
     while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
-      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
         Node v=res_graph.tail(e);
         Node w=res_graph.head(e);
         pred.set(w, e);
-        if (res_graph.valid(pred[v])) {
+        if (pred[v]!=INVALID) {
           free.set(w, std::min(free[v], res_graph.resCap(e)));
         } else {
@@ -1152 +1152 @@
       Node n=t;
       Num augment_value=free[t];
-      while (res_graph.valid(pred[n])) {
+      while (pred[n]!=INVALID) {
         ResGWEdge e=pred[n];
         res_graph.augment(e, augment_value);
@@ -1191 +1191 @@
     while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
-      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
         Node v=res_graph.tail(e);
         Node w=res_graph.head(e);
         pred.set(w, e);
-        if (res_graph.valid(pred[v])) {
+        if (pred[v]!=INVALID) {
           free.set(w, std::min(free[v], res_graph.resCap(e)));
         } else {
@@ -1209 +1209 @@
       Node n=t;
       Num augment_value=free[t];
-      while (res_graph.valid(pred[n])) {
+      while (pred[n]!=INVALID) {
         ResGWEdge e=pred[n];
         res_graph.augment(e, augment_value);
@@ -1245 +1245 @@
     {
       typename ResGW::NodeIt n;
-      for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
+      for(res_graph.first(n); n!=INVALID; ++n) {
         res_graph_to_F.set(n, F.addNode());
       }
@@ -1257 +1257 @@
     while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
-      if (res_graph.valid(e)) {
+      if (e!=INVALID) {
         if (bfs.isBNodeNewlyReached()) {
           dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
@@ -1300 +1300 @@
             typename MG::Node w=F.bNode(dfs);
             pred.set(w, dfs);
-            if (F.valid(pred[v])) {
+            if (pred[v]!=INVALID) {
               free.set(w, std::min(free[v], residual_capacity[dfs]));
             } else {
@@ -1320 +1320 @@
         typename MG::Node n=tF;
         Num augment_value=free[tF];
-        while (F.valid(pred[n])) {
+        while (pred[n]!=INVALID) {
           typename MG::Edge e=pred[n];
           res_graph.augment(original_edge[e], augment_value);
@@ -1338 +1338 @@
 
 
-
-
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
   bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
@@ -1355 +1353 @@
     while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
-      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
+      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
         dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
       }
@@ -1372 +1370 @@
       first_out_edges(filter_res_graph);
     typename FilterResGW::NodeIt v;
-    for(filter_res_graph.first(v); filter_res_graph.valid(v);
-        filter_res_graph.next(v))
+    for(filter_res_graph.first(v); v!=INVALID; ++v)
       {
         typename FilterResGW::OutEdgeIt e;
@@ -1419 +1416 @@
 
               pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
-              if (erasing_res_graph.valid(pred[v])) {
+              if (pred[v]!=INVALID) {
                 free1.set
                   (w, std::min(free1[v], res_graph.resCap

src/work/marci/makefile

@@ -5 +5 @@
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7
+BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba8
 #BINARIES = preflow_bug
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda

src/work/marci/max_flow_demo.cc

@@ -17 +17 @@
 
 // Use a DIMACS max flow file as stdin.
-// read_dimacs_demo < dimacs_max_flow_file
-
-
-//   struct Ize {
-//   };
-  
-//   struct Mize {
-//     Ize bumm;
-//   };
-
-//   template <typename B>
-//     class Huha {
-//     public:
-//       int u;
-//       B brr;
-//     };
-
+// max_flow_demo < dimacs_max_flow_file
 
 int main(int, char **) {
@@ -44 +28 @@
   typedef Graph::Node Node;
   typedef Graph::EdgeIt EdgeIt;
-
-
-//   Mize mize[10];
-//   Mize bize[0];
-//   Mize zize;
-//   typedef Mize Tize[0];
-
-//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
-//   std::cout << sizeof(bize) << std::endl;
-
-
-//   Huha<Tize> k;
-//   std::cout << sizeof(k) << std::endl;
-
-
-//   struct Bumm {
-//     //int a;
-//     bool b;
-//   };
-
-//   std::cout << sizeof(Bumm) << std::endl;
-
 
   Graph g;
@@ -142 +104 @@
 
 //   {
-//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
 //     ts.reset();
 //     int i=0;
-//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
+//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
 //     std::cout << "elapsed time: " << ts << std::endl;
 //     std::cout << "number of augmentation phases: " << i << std::endl; 
-//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
+
+//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+//      std::cout << "Slackness does not hold!" << std::endl;
+//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+//      std::cout << "Slackness does not hold!" << std::endl;
+//     }
 //   }
-
-  {
-    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
-    ts.reset();
-    int i=0;
-    while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
-    std::cout << "elapsed time: " << ts << std::endl;
-    std::cout << "number of augmentation phases: " << i << std::endl; 
-    std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
-
-    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
-      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
-        std::cout << "Slackness does not hold!" << std::endl;
-      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
-        std::cout << "Slackness does not hold!" << std::endl;
-    }
-  }
 
   {