1.1 --- a/src/work/athos/min_cost_flow.cc Tue May 25 15:11:11 2004 +0000
1.2 +++ b/src/work/athos/min_cost_flow.cc Tue May 25 17:01:26 2004 +0000
1.3 @@ -41,6 +41,13 @@
1.4 Node v5=graph.addNode();
1.5 Node t=graph.addNode();
1.6
1.7 + ListGraph::NodeMap<int> supply_demand(graph);
1.8 +
1.9 + supply_demand.set(s, 2);
1.10 + supply_demand.set(v1, 3);
1.11 + supply_demand.set(v3, -1);
1.12 + supply_demand.set(t, -4);
1.13 +
1.14 Edge s_v1=graph.addEdge(s, v1);
1.15 Edge v1_v2=graph.addEdge(v1, v2);
1.16 Edge s_v3=graph.addEdge(s, v3);
1.17 @@ -81,7 +88,8 @@
1.18 MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
1.19 min_cost_flow_test(graph, cost, supply_demand);
1.20
1.21 - int k=1;
1.22 + min_cost_flow_test.run();
1.23 + //int k=1;
1.24
1.25 /*
1.26 check( min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
2.1 --- a/src/work/athos/mincostflow.h Tue May 25 15:11:11 2004 +0000
2.2 +++ b/src/work/athos/mincostflow.h Tue May 25 17:01:26 2004 +0000
2.3 @@ -11,8 +11,11 @@
2.4 #include <hugo/maps.h>
2.5 #include <vector>
2.6 #include <list>
2.7 +#include <values.h>
2.8 #include <hugo/for_each_macros.h>
2.9 #include <hugo/unionfind.h>
2.10 +#include <hugo/bin_heap.h>
2.11 +#include <bfs_dfs.h>
2.12
2.13 namespace hugo {
2.14
2.15 @@ -93,8 +96,9 @@
2.16
2.17 //To store the flow
2.18 FlowMap flow;
2.19 - //To store the potentila (dual variables)
2.20 - typename Graph::template NodeMap<Cost> potential;
2.21 + //To store the potential (dual variables)
2.22 + typedef typename Graph::template NodeMap<Cost> PotentialMap;
2.23 + PotentialMap potential;
2.24 //To store excess-deficit values
2.25 SupplyDemandMap excess_deficit;
2.26
2.27 @@ -105,8 +109,13 @@
2.28 public :
2.29
2.30
2.31 - MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph),
2.32 - cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
2.33 + MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand):
2.34 + graph(_graph),
2.35 + cost(_cost),
2.36 + supply_demand(_supply_demand),
2.37 + flow(_graph),
2.38 + potential(_graph),
2.39 + excess_deficit(_graph){ }
2.40
2.41
2.42 ///Runs the algorithm.
2.43 @@ -121,7 +130,7 @@
2.44 //total_cost = 0;
2.45
2.46 typedef typename Graph::template NodeMap<int> HeapMap;
2.47 - typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
2.48 + typedef BinHeap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
2.49 std::greater<SupplyDemand> > HeapType;
2.50
2.51 //A heap for the excess nodes
2.52 @@ -133,7 +142,7 @@
2.53 HeapType deficit_nodes(deficit_nodes_map);
2.54
2.55 //A container to store nonabundant arcs
2.56 - list<Edge> nonabundant_arcs;
2.57 + std::list<Edge> nonabundant_arcs;
2.58
2.59
2.60 FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
2.61 @@ -147,7 +156,7 @@
2.62 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
2.63
2.64 //A union-find structure to store the abundant components
2.65 - UFE::MapType abund_comp_map(graph);
2.66 + typename UFE::MapType abund_comp_map(graph);
2.67 UFE abundant_components(abund_comp_map);
2.68
2.69
2.70 @@ -177,39 +186,48 @@
2.71 SupplyDemand max_excess = delta;
2.72
2.73 ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph
2.74 - ConstEdgeMap const_inf_map(MAX_INT);
2.75 + ConstEdgeMap const_inf_map(MAXINT);
2.76
2.77 //We need a residual graph which is uncapacitated
2.78 ResGraph res_graph(graph, const_inf_map, flow);
2.79
2.80 //An EdgeMap to tell which arcs are abundant
2.81 - template typename Graph::EdgeMap<bool> abundant_arcs(graph);
2.82 + typename Graph::template EdgeMap<bool> abundant_arcs(graph);
2.83
2.84 //Let's construct the sugraph consisting only of the abundant edges
2.85 typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
2.86 ConstNodeMap const_true_map(true);
2.87 - typedef SubGraphWrapper< Graph, ConstNodeMap,
2.88 - template typename Graph::EdgeMap<bool> >
2.89 + typedef SubGraphWrapper< const Graph, ConstNodeMap,
2.90 + typename Graph::template EdgeMap<bool> >
2.91 AbundantGraph;
2.92 AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs );
2.93
2.94 //Let's construct the residual graph for the abundant graph
2.95 - typedef ResGraphWrapper<const AbundantGraph,int,CapacityMap,EdgeIntMap>
2.96 + typedef ResGraphWrapper<const AbundantGraph,int,ConstEdgeMap,FlowMap>
2.97 ResAbGraph;
2.98 //Again uncapacitated
2.99 ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);
2.100
2.101 //We need things for the bfs
2.102 - typename ResAbGraph::NodeMap<bool> bfs_reached(res_ab_graph);
2.103 - typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>
2.104 + typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph);
2.105 + typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>
2.106 bfs_pred(res_ab_graph);
2.107 - NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy(res_ab_graph);
2.108 + NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
2.109 //We want to run bfs-es (more) on this graph 'res_ab_graph'
2.110 Bfs < ResAbGraph ,
2.111 - typename ResAbGraph::NodeMap<bool>,
2.112 - typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>,
2.113 + typename ResAbGraph::template NodeMap<bool>,
2.114 + typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
2.115 NullMap<typename ResAbGraph::Node, int> >
2.116 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
2.117 + /*This is what Marci wants for a bfs
2.118 + template <typename Graph,
2.119 + typename ReachedMap=typename Graph::template NodeMap<bool>,
2.120 + typename PredMap
2.121 + =typename Graph::template NodeMap<typename Graph::Edge>,
2.122 + typename DistMap=typename Graph::template NodeMap<int> >
2.123 + class Bfs : public BfsIterator<Graph, ReachedMap> {
2.124 +
2.125 + */
2.126
2.127 ModCostMap mod_cost(res_graph, cost, potential);
2.128
2.129 @@ -230,7 +248,7 @@
2.130 //Merge and stuff
2.131 {
2.132 SupplyDemand buf=8*number_of_nodes*delta;
2.133 - list<Edge>::iterator i = nonabundant_arcs.begin();
2.134 + typename std::list<Edge>::iterator i = nonabundant_arcs.begin();
2.135 while ( i != nonabundant_arcs.end() ){
2.136 if (flow[i]>=buf){
2.137 Node a = abundant_components.find(res_graph.head(i));
2.138 @@ -301,7 +319,7 @@
2.139 }
2.140
2.141
2.142 - while(max_excess > (n-1)*delta/n){
2.143 + while(max_excess > (number_of_nodes-1)*delta/number_of_nodes){
2.144
2.145
2.146 //s es t valasztasa
2.147 @@ -410,11 +428,11 @@
2.148
2.149 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
2.150 ///be called before using this function.
2.151 - const EdgeIntMap &getFlow() const { return flow;}
2.152 + const FlowMap &getFlow() const { return flow;}
2.153
2.154 ///Returns a const reference to the NodeMap \c potential (the dual solution).
2.155 /// \pre \ref run() must be called before using this function.
2.156 - const EdgeIntMap &getPotential() const { return potential;}
2.157 + const PotentialMap &getPotential() const { return potential;}
2.158
2.159 ///This function checks, whether the given solution is optimal
2.160 ///Running after a \c run() should return with true