Changeset 671:708df4dc6ab6 in lemon-0.x

Timestamp:

06/01/04 13:00:24 (21 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Compiles now

Location:

src/work

Files:

• athos/bfs_test.cc (added)
• athos/makefile (modified) (1 diff)
• athos/mincostflow.h (modified) (10 diffs)
• marci/bfs_dfs.h (modified) (2 diffs)

src/work/athos/makefile

@@ -1 @@
-BINARIES = min_cost_flow
+BINARIES = bfs_test min_cost_flow
 INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos} 
 include ../makefile

src/work/athos/mincostflow.h

@@ -214 +214 @@
         bfs_pred(res_ab_graph); 
       NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
+      //Teszt celbol:
+      //BfsIterator<ResAbGraph, typename ResAbGraph::template NodeMap<bool> > 
+      //izebize(res_ab_graph, bfs_reached);
       //We want to run bfs-es (more) on this graph 'res_ab_graph'
-      Bfs < ResAbGraph , 
+      Bfs < const ResAbGraph , 
         typename ResAbGraph::template NodeMap<bool>, 
         typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
@@ -234 +237 @@
       Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);
 
+      //We will use the number of the nodes of the graph often
+      int number_of_nodes = graph.nodeNum();
 
       while (max_excess > 0){
@@ -251 +256 @@
           typename std::list<Edge>::iterator i = nonabundant_arcs.begin();
           while ( i != nonabundant_arcs.end() ){
-            if (flow[i]>=buf){
-              Node a = abundant_components.find(res_graph.head(i));
-              Node b = abundant_components.find(res_graph.tail(i));
+            if (flow[*i]>=buf){
+              Node a = abundant_components.find(res_graph.head(*i));
+              Node b = abundant_components.find(res_graph.tail(*i));
               //Merge
               if (a != b){
@@ -270 +275 @@
                 if (qty_to_augment>0){
                   //Find path and augment
-                  bfs.run(non_root);
+                  bfs.run(typename AbundantGraph::Node(non_root));
                   //root should be reached
                   
@@ -277 +282 @@
                   ResGraphEdge e;
                   while (n!=non_root){
-                    e = bfs_pred(n);
+                    e = bfs_pred[n];
                     n = res_graph.tail(e);
                     res_graph.augment(e,qty_to_augment);
@@ -283 +288 @@
           
                   //We know that non_root had positive excess
-                  excess_nodes[non_root] -= qty_to_augment;
+                  excess_nodes.set(non_root,
+                                   excess_nodes[non_root] - qty_to_augment);
                   //But what about root node
                   //It might have been positive and so became larger
                   if (excess_deficit[root]>0){
-                    excess_nodes[root] += qty_to_augment;
+                    excess_nodes.set(root, 
+                                     excess_nodes[root] + qty_to_augment);
                   }
                   else{
                     //Or negative but not turned into positive
-                    deficit_nodes[root] -= qty_to_augment;
+                    deficit_nodes.set(root, 
+                                      deficit_nodes[root] - qty_to_augment);
                   }
 
@@ -304 +312 @@
               //Marci and Zsolt says I shouldn't do such things
               nonabundant_arcs.erase(i++);
-              abundant_arcs[i] = true;
+              abundant_arcs[*i] = true;
             }
             else
@@ -370 +378 @@
           } 
           else{
-            excess_nodes[s] -= delta;
+            excess_nodes.set(s, excess_nodes[s] - delta);
           }
           //Update the deficit_nodes heap
@@ -380 +388 @@
           } 
           else{
-            deficit_nodes[t] -= delta;
+            deficit_nodes.set(t, deficit_nodes[t] - delta);
           }
           //Dijkstra part ends here
@@ -415 +423 @@
       
 
-      return i;
+      //return i;
     }
 

src/work/marci/bfs_dfs.h

@@ -152 +152 @@
     /// the nodes which are \c false initially. 
     /// The constructor makes no initial changes on the maps.
-    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
+    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : 
+      BfsIterator<Graph, ReachedMap>(_graph, _reached), 
+      pred(_pred), dist(_dist) { }
     /// \c s is marked to be reached and pushed in the bfs queue.
     /// If the queue is empty, then the first out-edge is processed.
@@ -297 +299 @@
     /// the nodes which are \c false initially. 
     /// The constructor makes no initial changes on the maps.
-    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
+    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
     /// \c s is marked to be reached and pushed in the bfs queue.
     /// If the queue is empty, then the first out-edge is processed.