COIN-OR::LEMON - Graph Library

Changeset 661:d306e777117e in lemon-0.x


Ignore:
Timestamp:
05/25/04 17:11:11 (15 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@864
Message:

Corrected some obvious errors.

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/mincostflows.h

    r634 r661  
    1212#include <hugo/maps.h>
    1313#include <vector>
    14 #include <for_each_macros.h>
     14#include <hugo/for_each_macros.h>
    1515
    1616namespace hugo {
     
    9191    EdgeIntMap flow;
    9292    //To store the potentila (dual variables)
    93     typename Graph::template NodeMap<Length> potential;
     93    typedef typename Graph::template NodeMap<Length> PotentialMap;
     94    PotentialMap potential;
    9495   
    9596
     
    185186  ///Returns a const reference to the NodeMap \c potential (the dual solution).
    186187    /// \pre \ref run() must be called before using this function.
    187     const EdgeIntMap &getPotential() const { return potential;}
     188    const PotentialMap &getPotential() const { return potential;}
    188189
    189190    ///This function checks, whether the given solution is optimal
  • src/work/athos/makefile

    r607 r661  
    1 BINARIES = minlengthpaths_test minlength_demo
     1BINARIES = min_cost_flow
    22INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
    33include ../makefile
  • src/work/athos/min_cost_flow.cc

    r659 r661  
    11#include <iostream>
    2 #include "test_tools.h"
     2//#include "test_tools.h"
    33#include <hugo/list_graph.h>
    44#include <mincostflow.h>
     
    5252 
    5353
    54   ListGraph::EdgeMap<int> length(graph);
     54  ListGraph::EdgeMap<int> cost(graph);
    5555
    56   length.set(s_v1, 6);
    57   length.set(v1_v2, 4);
    58   length.set(s_v3, 10);
    59   length.set(v2_v4, 5);
    60   length.set(v2_v5, 1);
    61   length.set(v3_v5, 4);
    62   length.set(v4_t, 8);
    63   length.set(v5_t, 8);
     56  cost.set(s_v1, 6);
     57  cost.set(v1_v2, 4);
     58  cost.set(s_v3, 10);
     59  cost.set(v2_v4, 5);
     60  cost.set(v2_v5, 1);
     61  cost.set(v3_v5, 4);
     62  cost.set(v4_t, 8);
     63  cost.set(v5_t, 8);
    6464
    6565  /*
     
    8080
    8181  MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::NodeMap<int> >
    82     min_cost_flow_test(graph, length, supply_demand);
     82    min_cost_flow_test(graph, cost, supply_demand);
    8383
    8484  int k=1;
    8585
    8686  /*
    87   check(  min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total length should be 19");
     87  check(  min_cost_flow_test.run(s,t,k) == 1 && min_cost_flow_test.totalLength() == 19,"One path, total cost should be 19");
    8888
    8989  check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
     
    9191  k=2;
    9292 
    93   check(  min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total length should be 41");
     93  check(  min_cost_flow_test.run(s,t,k) == 2 && min_cost_flow_test.totalLength() == 41,"Two paths, total cost should be 41");
    9494
    9595  check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
     
    9898  k=4;
    9999
    100   check(  min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total length should be 64");
     100  check(  min_cost_flow_test.run(s,t,k) == 3 && min_cost_flow_test.totalLength() == 64,"Three paths, total cost should be 64");
    101101
    102102  check(min_cost_flow_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
  • src/work/athos/mincostflow.h

    r659 r661  
    1212#include <vector>
    1313#include <list>
    14 #include <for_each_macros.h>
    15 #include <hugo/union_find.h>
     14#include <hugo/for_each_macros.h>
     15#include <hugo/unionfind.h>
    1616
    1717namespace hugo {
     
    2020/// @{
    2121
    22   ///\brief Implementation of an algorithm for finding the minimum cost flow
    23   /// of given value in an uncapacitated network
     22  ///\brief Implementation of an algorithm for solving the minimum cost general
     23  /// flow problem in an uncapacitated network
    2424  ///
    2525  ///
     
    3131  /// \warning It is assumed here that the problem has a feasible solution
    3232  ///
    33   /// The range of the length (weight) function is nonnegative reals but
     33  /// The range of the cost (weight) function is nonnegative reals but
    3434  /// the range of capacity function is the set of nonnegative integers.
    3535  /// It is not a polinomial time algorithm for counting the minimum cost
     
    3838  ///
    3939  ///\author Attila Bernath
    40   template <typename Graph, typename LengthMap, typename SupplyDemandMap>
     40  template <typename Graph, typename CostMap, typename SupplyDemandMap>
    4141  class MinCostFlow {
    4242
    43     typedef typename LengthMap::ValueType Length;
     43    typedef typename CostMap::ValueType Cost;
    4444
    4545
     
    5050    typedef typename Graph::Edge Edge;
    5151    typedef typename Graph::OutEdgeIt OutEdgeIt;
    52     typedef typename Graph::template EdgeMap<int> EdgeIntMap;
     52    typedef typename Graph::template EdgeMap<SupplyDemand> FlowMap;
     53    typedef ConstMap<Edge,SupplyDemand> ConstEdgeMap;
    5354
    5455    //    typedef ConstMap<Edge,int> ConstMap;
    5556
    56     typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
    57     typedef typename ResGraphType::Edge ResGraphEdge;
    58 
    59     class ModLengthMap {   
    60       //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
    61       typedef typename Graph::template NodeMap<Length> NodeMap;
    62       const ResGraphType& res_graph;
     57    typedef ResGraphWrapper<const Graph,int,ConstEdgeMap,FlowMap> ResGraph;
     58    typedef typename ResGraph::Edge ResGraphEdge;
     59
     60    class ModCostMap {   
     61      //typedef typename ResGraph::template NodeMap<Cost> NodeMap;
     62      typedef typename Graph::template NodeMap<Cost> NodeMap;
     63      const ResGraph& res_graph;
    6364      //      const EdgeIntMap& rev;
    64       const LengthMap &ol;
     65      const CostMap &ol;
    6566      const NodeMap &pot;
    6667    public :
    67       typedef typename LengthMap::KeyType KeyType;
    68       typedef typename LengthMap::ValueType ValueType;
     68      typedef typename CostMap::KeyType KeyType;
     69      typedef typename CostMap::ValueType ValueType;
    6970       
    70       ValueType operator[](typename ResGraphType::Edge e) const {     
     71      ValueType operator[](typename ResGraph::Edge e) const {     
    7172        if (res_graph.forward(e))
    7273          return  ol[e]-(pot[res_graph.head(e)]-pot[res_graph.tail(e)]);   
     
    7576      }     
    7677       
    77       ModLengthMap(const ResGraphType& _res_graph,
    78                    const LengthMap &o,  const NodeMap &p) :
     78      ModCostMap(const ResGraph& _res_graph,
     79                   const CostMap &o,  const NodeMap &p) :
    7980        res_graph(_res_graph), /*rev(_rev),*/ ol(o), pot(p){};
    80     };//ModLengthMap
     81    };//ModCostMap
    8182
    8283
     
    8586    //Input
    8687    const Graph& graph;
    87     const LengthMap& length;
     88    const CostMap& cost;
    8889    const SupplyDemandMap& supply_demand;//supply or demand of nodes
    8990
     
    9293
    9394    //To store the flow
    94     EdgeIntMap flow;
     95    FlowMap flow;
    9596    //To store the potentila (dual variables)
    96     typename Graph::template NodeMap<Length> potential;
     97    typename Graph::template NodeMap<Cost> potential;
    9798    //To store excess-deficit values
    9899    SupplyDemandMap excess_deficit;
    99100   
    100101
    101     Length total_length;
     102    Cost total_cost;
    102103
    103104
     
    105106
    106107
    107     MinCostFlow(Graph& _graph, LengthMap& _length, SupplyDemandMap& _supply_demand) : graph(_graph),
    108       length(_length), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
     108    MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph),
     109      cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
    109110
    110111   
     
    118119
    119120      //Resetting variables from previous runs
    120       //total_length = 0;
     121      //total_cost = 0;
    121122
    122123      typedef typename Graph::template NodeMap<int> HeapMap;
     
    176177      SupplyDemand max_excess = delta;
    177178     
    178       //ConstMap<Edge,SupplyDemand> ConstEdgeMap;
    179 
     179      ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph
     180      ConstEdgeMap const_inf_map(MAX_INT);
     181     
    180182      //We need a residual graph which is uncapacitated
    181       ResGraphType res_graph(graph, flow);
     183      ResGraph res_graph(graph, const_inf_map, flow);
    182184     
    183185      //An EdgeMap to tell which arcs are abundant
     
    196198        ResAbGraph;
    197199      //Again uncapacitated
    198       ResAbGraph res_ab_graph(abundant_graph, flow);
     200      ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);
    199201     
    200202      //We need things for the bfs
     
    210212        bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
    211213     
    212       ModLengthMap mod_length(res_graph, length, potential);
    213 
    214       Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
     214      ModCostMap mod_cost(res_graph, cost, potential);
     215
     216      Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);
    215217
    216218
     
    316318         
    317319          //We have to change the potential
    318           FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
     320          FOR_EACH_LOC(typename ResGraph::NodeIt, n, res_graph){
    319321            potential[n] += dijkstra.distMap()[n];
    320322          }
     
    329331            res_graph.augment(e,delta);
    330332            /*
    331             //Let's update the total length
     333            //Let's update the total cost
    332334            if (res_graph.forward(e))
    333               total_length += length[e];
     335              total_cost += cost[e];
    334336            else
    335               total_length -= length[e];           
     337              total_cost -= cost[e];       
    336338            */
    337339          }
     
    401403
    402404
    403     ///This function gives back the total length of the found paths.
     405    ///This function gives back the total cost of the found paths.
    404406    ///Assumes that \c run() has been run and nothing changed since then.
    405     Length totalLength(){
    406       return total_length;
     407    Cost totalCost(){
     408      return total_cost;
    407409    }
    408410
     
    421423    ///\todo Is this OK here?
    422424    bool checkComplementarySlackness(){
    423       Length mod_pot;
    424       Length fl_e;
     425      Cost mod_pot;
     426      Cost fl_e;
    425427      FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){
    426428        //C^{\Pi}_{i,j}
    427         mod_pot = length[e]-potential[graph.head(e)]+potential[graph.tail(e)];
     429        mod_pot = cost[e]-potential[graph.head(e)]+potential[graph.tail(e)];
    428430        fl_e = flow[e];
    429431        //      std::cout << fl_e << std::endl;
Note: See TracChangeset for help on using the changeset viewer.