# HG changeset patch
# User athos
# Date 1086087624 0
# Node ID 708df4dc6ab6ef86f8f8cab0770fffaa9dc001c8
# Parent  e45bf7830d8c3ceaffafd70632c1cd72274c2dc1
Compiles now

diff -r e45bf7830d8c -r 708df4dc6ab6 src/work/athos/bfs_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/bfs_test.cc	Tue Jun 01 11:00:24 2004 +0000
@@ -0,0 +1,79 @@
+// -*- c++ -*-
+#include <iostream>
+#include <fstream>
+
+#include <sage_graph.h>
+//#include <smart_graph.h>
+#include <hugo/dimacs.h>
+#include <hugo/time_measure.h>
+#include <hugo/for_each_macros.h>
+#include <bfs_dfs.h>
+
+using namespace hugo;
+
+int main() {
+  typedef SageGraph Graph; 
+  typedef Graph::Node Node;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::Edge Edge;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::OutEdgeIt OutEdgeIt;
+
+  Graph g;
+  Node s, t;
+  Graph::EdgeMap<int> cap(g);
+  //readDimacsMaxFlow(std::cin, g, s, t, cap);
+  readDimacs(std::cin, g);
+
+  Graph::NodeMap<OutEdgeIt> pred(g);
+
+  Timer ts;
+  /*
+  {
+    ts.reset();
+    Graph::NodeMap<bool> reached(g);
+    reached.set(s, true);
+    pred.set(s, INVALID);
+    std::queue<Node> bfs_queue;
+    bfs_queue.push(t);
+    while (!bfs_queue.empty()) {
+      Node v=bfs_queue.front();	
+      bfs_queue.pop();
+      OutEdgeIt e;
+      for(g.first(e,v); g.valid(e); g.next(e)) {
+	Node w=g.head(e);
+	if (!reached[w]) {
+	  bfs_queue.push(w);
+	  reached.set(w, true);
+	  pred.set(w, e);
+	}
+      }
+    }
+
+    std::cout << ts << std::endl;
+  }
+  */
+
+  {
+    ts.reset();
+    Graph::NodeMap<bool> bfs_reached(g);
+    Graph::NodeMap<Edge> bfs_pred(g); 
+    Graph::NodeMap<int> bfs_dist(g);
+      
+    Bfs< Graph, Graph::NodeMap<bool>, 
+      Graph::NodeMap<Edge>, Graph::NodeMap<int> > 
+      bfs(g,bfs_reached, bfs_pred, bfs_dist );
+    bfs.run(s);
+    /*
+    pred.set(s, INVALID);
+    while (!bfs.finished()) { 
+      ++bfs; 
+      if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
+	pred.set(bfs.bNode(), bfs);
+    }
+    */
+    std::cout << ts << std::endl;
+  }
+
+  return 0;
+}
diff -r e45bf7830d8c -r 708df4dc6ab6 src/work/athos/makefile
--- a/src/work/athos/makefile	Tue Jun 01 08:30:20 2004 +0000
+++ b/src/work/athos/makefile	Tue Jun 01 11:00:24 2004 +0000
@@ -1,4 +1,4 @@
-BINARIES = min_cost_flow
+BINARIES = bfs_test min_cost_flow
 INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos} 
 include ../makefile
 
diff -r e45bf7830d8c -r 708df4dc6ab6 src/work/athos/mincostflow.h
--- a/src/work/athos/mincostflow.h	Tue Jun 01 08:30:20 2004 +0000
+++ b/src/work/athos/mincostflow.h	Tue Jun 01 11:00:24 2004 +0000
@@ -213,8 +213,11 @@
       typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge> 
 	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>,
 	NullMap<typename ResAbGraph::Node, int> > 
@@ -233,6 +236,8 @@
 
       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){
 
@@ -250,9 +255,9 @@
 	  SupplyDemand buf=8*number_of_nodes*delta;
 	  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){
 		abundant_components.join(a,b);
@@ -269,28 +274,31 @@
 		//If the non_root node has excess/deficit at all
 		if (qty_to_augment>0){
 		  //Find path and augment
-		  bfs.run(non_root);
+		  bfs.run(typename AbundantGraph::Node(non_root));
 		  //root should be reached
 		  
 		  //Augmenting on the found path
 		  Node n=root;
 		  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);
 		  }
 	  
 		  //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);
 		  }
 
 		  //Update the excess_deficit map
@@ -303,7 +311,7 @@
 	      //What happens to i?
 	      //Marci and Zsolt says I shouldn't do such things
 	      nonabundant_arcs.erase(i++);
-	      abundant_arcs[i] = true;
+	      abundant_arcs[*i] = true;
 	    }
 	    else
 	      ++i;
@@ -369,7 +377,7 @@
 	    
 	  } 
 	  else{
-	    excess_nodes[s] -= delta;
+	    excess_nodes.set(s, excess_nodes[s] - delta);
 	  }
 	  //Update the deficit_nodes heap
 	  if (delta >= deficit_nodes[t]){
@@ -379,7 +387,7 @@
 	    
 	  } 
 	  else{
-	    deficit_nodes[t] -= delta;
+	    deficit_nodes.set(t, deficit_nodes[t] - delta);
 	  }
 	  //Dijkstra part ends here
 	  
@@ -414,7 +422,7 @@
       }//while(max_excess > 0)
       
 
-      return i;
+      //return i;
     }
 
 
diff -r e45bf7830d8c -r 708df4dc6ab6 src/work/marci/bfs_dfs.h
--- a/src/work/marci/bfs_dfs.h	Tue Jun 01 08:30:20 2004 +0000
+++ b/src/work/marci/bfs_dfs.h	Tue Jun 01 11:00:24 2004 +0000
@@ -151,7 +151,9 @@
     /// The algorithm will search in a bfs order for 
     /// 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.
     /// If \c s was not marked previously, then 
@@ -296,7 +298,7 @@
     /// The algorithm will search in a dfs order for 
     /// 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.
     /// If \c s was not marked previously, then