Changeset 662:0155001b6f65 in lemon0.x
 Timestamp:
 05/25/04 19:01:26 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@865
 Location:
 src/work/athos
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/min_cost_flow.cc
r661 r662 42 42 Node t=graph.addNode(); 43 43 44 ListGraph::NodeMap<int> supply_demand(graph); 45 46 supply_demand.set(s, 2); 47 supply_demand.set(v1, 3); 48 supply_demand.set(v3, 1); 49 supply_demand.set(t, 4); 50 44 51 Edge s_v1=graph.addEdge(s, v1); 45 52 Edge v1_v2=graph.addEdge(v1, v2); … … 82 89 min_cost_flow_test(graph, cost, supply_demand); 83 90 84 int k=1; 91 min_cost_flow_test.run(); 92 //int k=1; 85 93 86 94 /* 
src/work/athos/mincostflow.h
r661 r662 12 12 #include <vector> 13 13 #include <list> 14 #include <values.h> 14 15 #include <hugo/for_each_macros.h> 15 16 #include <hugo/unionfind.h> 17 #include <hugo/bin_heap.h> 18 #include <bfs_dfs.h> 16 19 17 20 namespace hugo { … … 94 97 //To store the flow 95 98 FlowMap flow; 96 //To store the potentila (dual variables) 97 typename Graph::template NodeMap<Cost> potential; 99 //To store the potential (dual variables) 100 typedef typename Graph::template NodeMap<Cost> PotentialMap; 101 PotentialMap potential; 98 102 //To store excessdeficit values 99 103 SupplyDemandMap excess_deficit; … … 106 110 107 111 108 MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph), 109 cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ } 112 MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand): 113 graph(_graph), 114 cost(_cost), 115 supply_demand(_supply_demand), 116 flow(_graph), 117 potential(_graph), 118 excess_deficit(_graph){ } 110 119 111 120 … … 122 131 123 132 typedef typename Graph::template NodeMap<int> HeapMap; 124 typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,133 typedef BinHeap< Node, SupplyDemand, typename Graph::template NodeMap<int>, 125 134 std::greater<SupplyDemand> > HeapType; 126 135 … … 134 143 135 144 //A container to store nonabundant arcs 136 list<Edge> nonabundant_arcs;145 std::list<Edge> nonabundant_arcs; 137 146 138 147 … … 148 157 149 158 //A unionfind structure to store the abundant components 150 UFE::MapType abund_comp_map(graph);159 typename UFE::MapType abund_comp_map(graph); 151 160 UFE abundant_components(abund_comp_map); 152 161 … … 178 187 179 188 ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph 180 ConstEdgeMap const_inf_map(MAX _INT);189 ConstEdgeMap const_inf_map(MAXINT); 181 190 182 191 //We need a residual graph which is uncapacitated … … 184 193 185 194 //An EdgeMap to tell which arcs are abundant 186 t emplate typename Graph::EdgeMap<bool> abundant_arcs(graph);195 typename Graph::template EdgeMap<bool> abundant_arcs(graph); 187 196 188 197 //Let's construct the sugraph consisting only of the abundant edges 189 198 typedef ConstMap< typename Graph::Node, bool > ConstNodeMap; 190 199 ConstNodeMap const_true_map(true); 191 typedef SubGraphWrapper< Graph, ConstNodeMap,192 t emplate typename Graph::EdgeMap<bool> >200 typedef SubGraphWrapper< const Graph, ConstNodeMap, 201 typename Graph::template EdgeMap<bool> > 193 202 AbundantGraph; 194 203 AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs ); 195 204 196 205 //Let's construct the residual graph for the abundant graph 197 typedef ResGraphWrapper<const AbundantGraph,int,C apacityMap,EdgeIntMap>206 typedef ResGraphWrapper<const AbundantGraph,int,ConstEdgeMap,FlowMap> 198 207 ResAbGraph; 199 208 //Again uncapacitated … … 201 210 202 211 //We need things for the bfs 203 typename ResAbGraph:: NodeMap<bool> bfs_reached(res_ab_graph);204 typename ResAbGraph:: NodeMap<typename ResAbGraph::Edge>212 typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph); 213 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge> 205 214 bfs_pred(res_ab_graph); 206 NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy (res_ab_graph);215 NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy; 207 216 //We want to run bfses (more) on this graph 'res_ab_graph' 208 217 Bfs < ResAbGraph , 209 typename ResAbGraph:: NodeMap<bool>,210 typename ResAbGraph:: NodeMap<typename ResAbGraph::Edge>,218 typename ResAbGraph::template NodeMap<bool>, 219 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>, 211 220 NullMap<typename ResAbGraph::Node, int> > 212 221 bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy); 222 /*This is what Marci wants for a bfs 223 template <typename Graph, 224 typename ReachedMap=typename Graph::template NodeMap<bool>, 225 typename PredMap 226 =typename Graph::template NodeMap<typename Graph::Edge>, 227 typename DistMap=typename Graph::template NodeMap<int> > 228 class Bfs : public BfsIterator<Graph, ReachedMap> { 229 230 */ 213 231 214 232 ModCostMap mod_cost(res_graph, cost, potential); … … 231 249 { 232 250 SupplyDemand buf=8*number_of_nodes*delta; 233 list<Edge>::iterator i = nonabundant_arcs.begin();251 typename std::list<Edge>::iterator i = nonabundant_arcs.begin(); 234 252 while ( i != nonabundant_arcs.end() ){ 235 253 if (flow[i]>=buf){ … … 302 320 303 321 304 while(max_excess > (n 1)*delta/n){322 while(max_excess > (number_of_nodes1)*delta/number_of_nodes){ 305 323 306 324 … … 411 429 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must 412 430 ///be called before using this function. 413 const EdgeIntMap &getFlow() const { return flow;}431 const FlowMap &getFlow() const { return flow;} 414 432 415 433 ///Returns a const reference to the NodeMap \c potential (the dual solution). 416 434 /// \pre \ref run() must be called before using this function. 417 const EdgeIntMap &getPotential() const { return potential;}435 const PotentialMap &getPotential() const { return potential;} 418 436 419 437 ///This function checks, whether the given solution is optimal
Note: See TracChangeset
for help on using the changeset viewer.