Changeset 662:0155001b6f65 in lemon-0.x for src/work/athos

Timestamp:

05/25/04 19:01:26 (21 years ago)

Author:

athos

Branch:

default

Phase:

public

Convert:

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

Message:

Almost compiles.

Location:

src/work/athos

Files:

• min_cost_flow.cc (modified) (2 diffs)
• mincostflow.h (modified) (12 diffs)

src/work/athos/min_cost_flow.cc

@@ -42 +42 @@
   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);
@@ -82 +89 @@
     min_cost_flow_test(graph, cost, supply_demand);
 
-  int k=1;
+  min_cost_flow_test.run();
+  //int k=1;
 
   /*

src/work/athos/mincostflow.h

@@ -12 +12 @@
 #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 {
@@ -94 +97 @@
     //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;
@@ -106 +110 @@
 
 
-    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){ }
 
     
@@ -122 +131 @@
 
       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;
 
@@ -134 +143 @@
 
       //A container to store nonabundant arcs
-      list<Edge> nonabundant_arcs;
+      std::list<Edge> nonabundant_arcs;
 
         
@@ -148 +157 @@
 
       //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);
 
@@ -178 +187 @@
       
       ///\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
@@ -184 +193 @@
       
       //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
@@ -201 +210 @@
       
       //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);
@@ -231 +249 @@
         {
           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){
@@ -302 +320 @@
 
 
-        while(max_excess > (n-1)*delta/n){
+        while(max_excess > (number_of_nodes-1)*delta/number_of_nodes){
           
           
@@ -411 +429 @@
     ///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