# HG changeset patch
# User athos
# Date 1085504486 0
# Node ID 0155001b6f65c14a3e3192d1ad9e24d27b632a8c
# Parent  d306e777117ec00e25dd38ebe9a31219d7fb65f4
Almost compiles.

diff -r d306e777117e -r 0155001b6f65 src/work/athos/min_cost_flow.cc
--- a/src/work/athos/min_cost_flow.cc	Tue May 25 15:11:11 2004 +0000
+++ b/src/work/athos/min_cost_flow.cc	Tue May 25 17:01:26 2004 +0000
@@ -41,6 +41,13 @@
   Node v5=graph.addNode();
   Node t=graph.addNode();
 
+  ListGraph::NodeMap<int> supply_demand(graph);
+
+  supply_demand.set(s, 2);
+  supply_demand.set(v1, 3);
+  supply_demand.set(v3, -1);
+  supply_demand.set(t, -4);
+
   Edge s_v1=graph.addEdge(s, v1);
   Edge v1_v2=graph.addEdge(v1, v2);
   Edge s_v3=graph.addEdge(s, v3);
@@ -81,7 +88,8 @@
   MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
     min_cost_flow_test(graph, cost, supply_demand);
 
-  int k=1;
+  min_cost_flow_test.run();
+  //int k=1;
 
   /*
   check(  min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
diff -r d306e777117e -r 0155001b6f65 src/work/athos/mincostflow.h
--- a/src/work/athos/mincostflow.h	Tue May 25 15:11:11 2004 +0000
+++ b/src/work/athos/mincostflow.h	Tue May 25 17:01:26 2004 +0000
@@ -11,8 +11,11 @@
 #include <hugo/maps.h>
 #include <vector>
 #include <list>
+#include <values.h>
 #include <hugo/for_each_macros.h>
 #include <hugo/unionfind.h>
+#include <hugo/bin_heap.h>
+#include <bfs_dfs.h>
 
 namespace hugo {
 
@@ -93,8 +96,9 @@
 
     //To store the flow
     FlowMap flow; 
-    //To store the potentila (dual variables)
-    typename Graph::template NodeMap<Cost> potential;
+    //To store the potential (dual variables)
+    typedef typename Graph::template NodeMap<Cost> PotentialMap;
+    PotentialMap potential;
     //To store excess-deficit values
     SupplyDemandMap excess_deficit;
     
@@ -105,8 +109,13 @@
   public :
 
 
-    MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph), 
-      cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
+   MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand):
+     graph(_graph), 
+     cost(_cost), 
+     supply_demand(_supply_demand), 
+     flow(_graph), 
+     potential(_graph),
+     excess_deficit(_graph){ }
 
     
     ///Runs the algorithm.
@@ -121,7 +130,7 @@
       //total_cost = 0;
 
       typedef typename Graph::template NodeMap<int> HeapMap;
-      typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
+      typedef BinHeap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
 	std::greater<SupplyDemand> > 	HeapType;
 
       //A heap for the excess nodes
@@ -133,7 +142,7 @@
       HeapType deficit_nodes(deficit_nodes_map);
 
       //A container to store nonabundant arcs
-      list<Edge> nonabundant_arcs;
+      std::list<Edge> nonabundant_arcs;
 
 	
       FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
@@ -147,7 +156,7 @@
       typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
 
       //A union-find structure to store the abundant components
-      UFE::MapType abund_comp_map(graph);
+      typename UFE::MapType abund_comp_map(graph);
       UFE abundant_components(abund_comp_map);
 
 
@@ -177,39 +186,48 @@
       SupplyDemand max_excess = delta;
       
       ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph
-      ConstEdgeMap const_inf_map(MAX_INT);
+      ConstEdgeMap const_inf_map(MAXINT);
       
       //We need a residual graph which is uncapacitated
       ResGraph res_graph(graph, const_inf_map, flow);
       
       //An EdgeMap to tell which arcs are abundant
-      template typename Graph::EdgeMap<bool> abundant_arcs(graph);
+      typename Graph::template EdgeMap<bool> abundant_arcs(graph);
 
       //Let's construct the sugraph consisting only of the abundant edges
       typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
       ConstNodeMap const_true_map(true);
-      typedef SubGraphWrapper< Graph, ConstNodeMap, 
-	 template typename Graph::EdgeMap<bool> > 
+      typedef SubGraphWrapper< const Graph, ConstNodeMap, 
+	 typename Graph::template EdgeMap<bool> > 
 	AbundantGraph;
       AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs );
       
       //Let's construct the residual graph for the abundant graph
-      typedef ResGraphWrapper<const AbundantGraph,int,CapacityMap,EdgeIntMap> 
+      typedef ResGraphWrapper<const AbundantGraph,int,ConstEdgeMap,FlowMap> 
 	ResAbGraph;
       //Again uncapacitated
       ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);
       
       //We need things for the bfs
-      typename ResAbGraph::NodeMap<bool> bfs_reached(res_ab_graph);
-      typename ResAbGraph::NodeMap<typename ResAbGraph::Edge> 
+      typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph);
+      typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge> 
 	bfs_pred(res_ab_graph); 
-      NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy(res_ab_graph);
+      NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
       //We want to run bfs-es (more) on this graph 'res_ab_graph'
       Bfs < ResAbGraph , 
-	typename ResAbGraph::NodeMap<bool>, 
-	typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>,
+	typename ResAbGraph::template NodeMap<bool>, 
+	typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
 	NullMap<typename ResAbGraph::Node, int> > 
 	bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
+      /*This is what Marci wants for a bfs
+	template <typename Graph, 
+	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
+	    typename PredMap
+	    =typename Graph::template NodeMap<typename Graph::Edge>, 
+	    typename DistMap=typename Graph::template NodeMap<int> > 
+	    class Bfs : public BfsIterator<Graph, ReachedMap> {
+
+       */
       
       ModCostMap mod_cost(res_graph, cost, potential);
 
@@ -230,7 +248,7 @@
 	//Merge and stuff
 	{
 	  SupplyDemand buf=8*number_of_nodes*delta;
-	  list<Edge>::iterator i = nonabundant_arcs.begin();
+	  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));
@@ -301,7 +319,7 @@
 	}
 
 
-	while(max_excess > (n-1)*delta/n){
+	while(max_excess > (number_of_nodes-1)*delta/number_of_nodes){
 	  
 	  
 	  //s es t valasztasa
@@ -410,11 +428,11 @@
 
     ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
     ///be called before using this function.
-    const EdgeIntMap &getFlow() const { return flow;}
+    const FlowMap &getFlow() const { return flow;}
 
   ///Returns a const reference to the NodeMap \c potential (the dual solution).
     /// \pre \ref run() must be called before using this function.
-    const EdgeIntMap &getPotential() const { return potential;}
+    const PotentialMap &getPotential() const { return potential;}
 
     ///This function checks, whether the given solution is optimal
     ///Running after a \c run() should return with true