COIN-OR::LEMON - Graph Library

Changeset 633:305bd9c56f10 in lemon-0.x


Ignore:
Timestamp:
05/13/04 18:00:18 (16 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@824
Message:

Slight modifications.

Location:
src
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed
  • src/hugo/mincostflows.h

    r611 r633  
    9393    typename Graph::template NodeMap<Length> potential;
    9494   
    95     //Container to store found paths
    96     //std::vector< std::vector<Edge> > paths;
    97     //typedef DirPath<Graph> DPath;
    98     //DPath paths;
    99 
    10095
    10196    Length total_length;
     
    152147        };
    153148       
     149        //We have to copy the potential
     150        FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
     151          potential[n] += dijkstra.distMap()[n];
     152        }
     153        /*
    154154        {
    155155          //We have to copy the potential
     
    159159          }
    160160        }
    161 
     161        */
    162162
    163163        //Augmenting on the sortest path
     
    226226    }
    227227   
    228     /*
    229       ///\todo To be implemented later
    230 
    231     ///This function gives back the \c j-th path in argument p.
    232     ///Assumes that \c run() has been run and nothing changed since then.
    233     /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path.
    234     template<typename DirPath>
    235     void getPath(DirPath& p, int j){
    236       p.clear();
    237       typename DirPath::Builder B(p);
    238       for(typename std::vector<Edge>::iterator i=paths[j].begin();
    239           i!=paths[j].end(); ++i ){
    240         B.pushBack(*i);
    241       }
    242 
    243       B.commit();
    244     }
    245 
    246     */
    247228
    248229  }; //class MinCostFlows
     
    252233} //namespace hugo
    253234
    254 #endif //HUGO_MINCOSTFLOW_H
     235#endif //HUGO_MINCOSTFLOWS_H
  • src/work/athos/mincostflow.h

    r611 r633  
    11// -*- c++ -*-
    2 #ifndef HUGO_MINCOSTFLOWS_H
    3 #define HUGO_MINCOSTFLOWS_H
     2#ifndef HUGO_MINCOSTFLOW_H
     3#define HUGO_MINCOSTFLOW_H
    44
    55///\ingroup galgs
     
    2323  ///
    2424  ///
    25   /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
    26   /// an algorithm for finding a flow of value \c k
    27   ///(for small values of \c k) having minimal total cost 
    28   /// from a given source node to a given target node in an
    29   /// edge-weighted directed graph having nonnegative integer capacities.
     25  /// The class \ref hugo::MinCostFlow "MinCostFlow" implements
     26  /// an algorithm for solving the following general minimum cost flow problem>
     27  ///
     28  ///
     29  ///
     30  /// \warning It is assumed here that the problem has a feasible solution
     31  ///
    3032  /// The range of the length (weight) function is nonnegative reals but
    3133  /// the range of capacity function is the set of nonnegative integers.
     
    3537  ///
    3638  ///\author Attila Bernath
    37   template <typename Graph, typename LengthMap, typename CapacityMap>
    38   class MinCostFlows {
     39  template <typename Graph, typename LengthMap, typename SupplyMap>
     40  class MinCostFlow {
    3941
    4042    typedef typename LengthMap::ValueType Length;
    4143
    42     //Warning: this should be integer type
    43     typedef typename CapacityMap::ValueType Capacity;
     44
     45    typedef typename SupplyMap::ValueType Supply;
    4446   
    4547    typedef typename Graph::Node Node;
     
    8385    const Graph& G;
    8486    const LengthMap& length;
    85     const CapacityMap& capacity;
     87    const SupplyMap& supply;//supply or demand of nodes
    8688
    8789
     
    9294    //To store the potentila (dual variables)
    9395    typename Graph::template NodeMap<Length> potential;
    94    
    95     //Container to store found paths
    96     //std::vector< std::vector<Edge> > paths;
    97     //typedef DirPath<Graph> DPath;
    98     //DPath paths;
    99 
     96    //To store excess-deficit values
     97    SupplyMap excess;
     98   
    10099
    101100    Length total_length;
     
    105104
    106105
    107     MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
    108       length(_length), capacity(_cap), flow(_G), potential(_G){ }
     106    MinCostFlow(Graph& _G, LengthMap& _length, SupplyMap& _supply) : G(_G),
     107      length(_length), supply(_supply), flow(_G), potential(_G){ }
    109108
    110109   
     
    116115    ///\todo May be it does make sense to be able to start with a nonzero
    117116    /// feasible primal-dual solution pair as well.
    118     int run(Node s, Node t, int k) {
     117    int run() {
    119118
    120119      //Resetting variables from previous runs
     
    124123        flow.set(e,0);
    125124      }
     125
     126      //Initial value for delta
     127      Supply delta = 0;
    126128     
    127129      FOR_EACH_LOC(typename Graph::NodeIt, n, G){
    128         //cout << potential[n]<<endl;
     130        if (delta < abs(supply[e])){
     131          delta = abs(supply[e]);
     132        }
     133        excess.set(n,supply[e]);
     134        //Initialize the copy of the Dijkstra potential to zero
    129135        potential.set(n,0);
    130136      }
     
    132138
    133139     
    134       //We need a residual graph
    135       ResGraphType res_graph(G, capacity, flow);
    136 
    137       //Initialize the copy of the Dijkstra potential to zero
    138      
    139       //typename ResGraphType::template NodeMap<Length> potential(res_graph);
    140 
    141 
     140      //We need a residual graph which is uncapacitated
     141      ResGraphType res_graph(G, flow);
     142
     143
     144     
    142145      ModLengthMap mod_length(res_graph, length, potential);
    143146
    144147      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
     148
    145149
    146150      int i;
     
    152156        };
    153157       
     158        //We have to copy the potential
     159        FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
     160          potential[n] += dijkstra.distMap()[n];
     161        }
     162
     163        /*
    154164        {
    155           //We have to copy the potential
     165
    156166          typename ResGraphType::NodeIt n;
    157167          for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
     
    159169          }
    160170        }
    161 
     171        */
    162172
    163173        //Augmenting on the sortest path
     
    167177          e = dijkstra.pred(n);
    168178          n = dijkstra.predNode(n);
    169           res_graph.augment(e,1);
     179          res_graph.augment(e,delta);
    170180          //Let's update the total length
    171181          if (res_graph.forward(e))
     
    226236    }
    227237   
    228     /*
    229       ///\todo To be implemented later
    230 
    231     ///This function gives back the \c j-th path in argument p.
    232     ///Assumes that \c run() has been run and nothing changed since then.
    233     /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path.
    234     template<typename DirPath>
    235     void getPath(DirPath& p, int j){
    236       p.clear();
    237       typename DirPath::Builder B(p);
    238       for(typename std::vector<Edge>::iterator i=paths[j].begin();
    239           i!=paths[j].end(); ++i ){
    240         B.pushBack(*i);
    241       }
    242 
    243       B.commit();
    244     }
    245 
    246     */
    247 
    248   }; //class MinCostFlows
     238
     239  }; //class MinCostFlow
    249240
    250241  ///@}
Note: See TracChangeset for help on using the changeset viewer.