1.1 --- a/src/work/athos/mincostflow.h Tue May 25 15:11:11 2004 +0000
1.2 +++ b/src/work/athos/mincostflow.h Tue May 25 17:01:26 2004 +0000
1.3 @@ -11,8 +11,11 @@
1.4 #include <hugo/maps.h>
1.5 #include <vector>
1.6 #include <list>
1.7 +#include <values.h>
1.8 #include <hugo/for_each_macros.h>
1.9 #include <hugo/unionfind.h>
1.10 +#include <hugo/bin_heap.h>
1.11 +#include <bfs_dfs.h>
1.12
1.13 namespace hugo {
1.14
1.15 @@ -93,8 +96,9 @@
1.16
1.17 //To store the flow
1.18 FlowMap flow;
1.19 - //To store the potentila (dual variables)
1.20 - typename Graph::template NodeMap<Cost> potential;
1.21 + //To store the potential (dual variables)
1.22 + typedef typename Graph::template NodeMap<Cost> PotentialMap;
1.23 + PotentialMap potential;
1.24 //To store excess-deficit values
1.25 SupplyDemandMap excess_deficit;
1.26
1.27 @@ -105,8 +109,13 @@
1.28 public :
1.29
1.30
1.31 - MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph),
1.32 - cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
1.33 + MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand):
1.34 + graph(_graph),
1.35 + cost(_cost),
1.36 + supply_demand(_supply_demand),
1.37 + flow(_graph),
1.38 + potential(_graph),
1.39 + excess_deficit(_graph){ }
1.40
1.41
1.42 ///Runs the algorithm.
1.43 @@ -121,7 +130,7 @@
1.44 //total_cost = 0;
1.45
1.46 typedef typename Graph::template NodeMap<int> HeapMap;
1.47 - typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
1.48 + typedef BinHeap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
1.49 std::greater<SupplyDemand> > HeapType;
1.50
1.51 //A heap for the excess nodes
1.52 @@ -133,7 +142,7 @@
1.53 HeapType deficit_nodes(deficit_nodes_map);
1.54
1.55 //A container to store nonabundant arcs
1.56 - list<Edge> nonabundant_arcs;
1.57 + std::list<Edge> nonabundant_arcs;
1.58
1.59
1.60 FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
1.61 @@ -147,7 +156,7 @@
1.62 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
1.63
1.64 //A union-find structure to store the abundant components
1.65 - UFE::MapType abund_comp_map(graph);
1.66 + typename UFE::MapType abund_comp_map(graph);
1.67 UFE abundant_components(abund_comp_map);
1.68
1.69
1.70 @@ -177,39 +186,48 @@
1.71 SupplyDemand max_excess = delta;
1.72
1.73 ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph
1.74 - ConstEdgeMap const_inf_map(MAX_INT);
1.75 + ConstEdgeMap const_inf_map(MAXINT);
1.76
1.77 //We need a residual graph which is uncapacitated
1.78 ResGraph res_graph(graph, const_inf_map, flow);
1.79
1.80 //An EdgeMap to tell which arcs are abundant
1.81 - template typename Graph::EdgeMap<bool> abundant_arcs(graph);
1.82 + typename Graph::template EdgeMap<bool> abundant_arcs(graph);
1.83
1.84 //Let's construct the sugraph consisting only of the abundant edges
1.85 typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
1.86 ConstNodeMap const_true_map(true);
1.87 - typedef SubGraphWrapper< Graph, ConstNodeMap,
1.88 - template typename Graph::EdgeMap<bool> >
1.89 + typedef SubGraphWrapper< const Graph, ConstNodeMap,
1.90 + typename Graph::template EdgeMap<bool> >
1.91 AbundantGraph;
1.92 AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs );
1.93
1.94 //Let's construct the residual graph for the abundant graph
1.95 - typedef ResGraphWrapper<const AbundantGraph,int,CapacityMap,EdgeIntMap>
1.96 + typedef ResGraphWrapper<const AbundantGraph,int,ConstEdgeMap,FlowMap>
1.97 ResAbGraph;
1.98 //Again uncapacitated
1.99 ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);
1.100
1.101 //We need things for the bfs
1.102 - typename ResAbGraph::NodeMap<bool> bfs_reached(res_ab_graph);
1.103 - typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>
1.104 + typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph);
1.105 + typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>
1.106 bfs_pred(res_ab_graph);
1.107 - NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy(res_ab_graph);
1.108 + NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
1.109 //We want to run bfs-es (more) on this graph 'res_ab_graph'
1.110 Bfs < ResAbGraph ,
1.111 - typename ResAbGraph::NodeMap<bool>,
1.112 - typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>,
1.113 + typename ResAbGraph::template NodeMap<bool>,
1.114 + typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
1.115 NullMap<typename ResAbGraph::Node, int> >
1.116 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
1.117 + /*This is what Marci wants for a bfs
1.118 + template <typename Graph,
1.119 + typename ReachedMap=typename Graph::template NodeMap<bool>,
1.120 + typename PredMap
1.121 + =typename Graph::template NodeMap<typename Graph::Edge>,
1.122 + typename DistMap=typename Graph::template NodeMap<int> >
1.123 + class Bfs : public BfsIterator<Graph, ReachedMap> {
1.124 +
1.125 + */
1.126
1.127 ModCostMap mod_cost(res_graph, cost, potential);
1.128
1.129 @@ -230,7 +248,7 @@
1.130 //Merge and stuff
1.131 {
1.132 SupplyDemand buf=8*number_of_nodes*delta;
1.133 - list<Edge>::iterator i = nonabundant_arcs.begin();
1.134 + typename std::list<Edge>::iterator i = nonabundant_arcs.begin();
1.135 while ( i != nonabundant_arcs.end() ){
1.136 if (flow[i]>=buf){
1.137 Node a = abundant_components.find(res_graph.head(i));
1.138 @@ -301,7 +319,7 @@
1.139 }
1.140
1.141
1.142 - while(max_excess > (n-1)*delta/n){
1.143 + while(max_excess > (number_of_nodes-1)*delta/number_of_nodes){
1.144
1.145
1.146 //s es t valasztasa
1.147 @@ -410,11 +428,11 @@
1.148
1.149 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
1.150 ///be called before using this function.
1.151 - const EdgeIntMap &getFlow() const { return flow;}
1.152 + const FlowMap &getFlow() const { return flow;}
1.153
1.154 ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.155 /// \pre \ref run() must be called before using this function.
1.156 - const EdgeIntMap &getPotential() const { return potential;}
1.157 + const PotentialMap &getPotential() const { return potential;}
1.158
1.159 ///This function checks, whether the given solution is optimal
1.160 ///Running after a \c run() should return with true