COIN-OR::LEMON - Graph Library

Changeset 941:186aa53d2802 in lemon-0.x


Ignore:
Timestamp:
10/08/04 15:07:51 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1283
Message:

Suurballe and MinCostFlow? classes are now able to increase the flow 1 by 1 with
this->augment()

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/min_cost_flow.h

    r921 r941  
    7171    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    7272
    73 
    7473    typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
    7574    typedef typename ResGW::Edge ResGraphEdge;
    7675
     76  protected:
     77
     78    const Graph& g;
     79    const LengthMap& length;
     80    const CapacityMap& capacity;
     81
     82    EdgeIntMap flow;
     83    typedef typename Graph::template NodeMap<Length> PotentialMap;
     84    PotentialMap potential;
     85
     86    Node s;
     87    Node t;
     88   
     89    Length total_length;
     90
    7791    class ModLengthMap {   
    7892      typedef typename Graph::template NodeMap<Length> NodeMap;
    79       const ResGW& G;
    80       const LengthMap &ol;
     93      const ResGW& g;
     94      const LengthMap &length;
    8195      const NodeMap &pot;
    8296    public :
    8397      typedef typename LengthMap::KeyType KeyType;
    8498      typedef typename LengthMap::ValueType ValueType;
     99
     100      ModLengthMap(const ResGW& _g,
     101                   const LengthMap &_length, const NodeMap &_pot) :
     102        g(_g), /*rev(_rev),*/ length(_length), pot(_pot) { }
    85103       
    86104      ValueType operator[](typename ResGW::Edge e) const {     
    87         if (G.forward(e))
    88           return  ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
     105        if (g.forward(e))
     106          return  length[e]-(pot[g.head(e)]-pot[g.tail(e)]);   
    89107        else
    90           return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
     108          return -length[e]-(pot[g.head(e)]-pot[g.tail(e)]);   
    91109      }     
    92110       
    93       ModLengthMap(const ResGW& _G,
    94                    const LengthMap &o,  const NodeMap &p) :
    95         G(_G), /*rev(_rev),*/ ol(o), pot(p){};
    96     };//ModLengthMap
    97 
    98 
    99   protected:
    100    
    101     //Input
    102     const Graph& G;
    103     const LengthMap& length;
    104     const CapacityMap& capacity;
    105 
    106 
    107     //auxiliary variables
    108 
    109     //To store the flow
    110     EdgeIntMap flow;
    111     //To store the potential (dual variables)
    112     typedef typename Graph::template NodeMap<Length> PotentialMap;
    113     PotentialMap potential;
    114    
    115 
    116     Length total_length;
    117 
     111    }; //ModLengthMap
     112
     113    ResGW res_graph;
     114    ModLengthMap mod_length;
     115    Dijkstra<ResGW, ModLengthMap> dijkstra;
    118116
    119117  public :
    120118
    121     /// The constructor of the class.
    122    
    123     ///\param _G The directed graph the algorithm runs on.
    124     ///\param _length The length (weight or cost) of the edges.
    125     ///\param _cap The capacity of the edges.
    126     MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
    127       length(_length), capacity(_cap), flow(_G), potential(_G){ }
    128 
    129    
    130     ///Runs the algorithm.
    131    
    132     ///Runs the algorithm.
    133     ///Returns k if there is a flow of value at least k edge-disjoint
    134     ///from s to t.
    135     ///Otherwise it returns the maximum value of a flow from s to t.
    136     ///
    137     ///\param s The source node.
    138     ///\param t The target node.
    139     ///\param k The value of the flow we are looking for.
    140     ///
    141     ///\todo May be it does make sense to be able to start with a nonzero
    142     /// feasible primal-dual solution pair as well.
    143     int run(Node s, Node t, int k) {
    144 
    145       //Resetting variables from previous runs
    146       total_length = 0;
    147      
    148       for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
    149 
    150       //Initialize the potential to zero
    151       for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
    152      
    153      
    154       //We need a residual graph
    155       ResGW res_graph(G, capacity, flow);
    156 
    157 
    158       ModLengthMap mod_length(res_graph, length, potential);
    159 
    160       Dijkstra<ResGW, ModLengthMap> dijkstra(res_graph, mod_length);
    161 
    162       int i;
    163       for (i=0; i<k; ++i){
    164         dijkstra.run(s);
    165         if (!dijkstra.reached(t)){
    166           //There are no flow of value k from s to t
    167           break;
    168         };
     119    /*! \brief The constructor of the class.
     120   
     121    \param _g The directed graph the algorithm runs on.
     122    \param _length The length (weight or cost) of the edges.
     123    \param _cap The capacity of the edges.
     124    \param _s Source node.
     125    \param _t Target node.
     126    */
     127    MinCostFlow(Graph& _g, LengthMap& _length, CapacityMap& _cap,
     128                Node _s, Node _t) :
     129      g(_g), length(_length), capacity(_cap), flow(_g), potential(_g),
     130      s(_s), t(_t),
     131      res_graph(g, capacity, flow),
     132      mod_length(res_graph, length, potential),
     133      dijkstra(res_graph, mod_length) {
     134      reset();
     135      }
     136
     137    /*! Tries to augment the flow between s and t by 1.
     138      The return value shows if the augmentation is successful.
     139     */
     140    bool augment() {
     141      dijkstra.run(s);
     142      if (!dijkstra.reached(t)) {
     143
     144        //Unsuccessful augmentation.
     145        return false;
     146      } else {
     147
     148        //We have to change the potential
     149        for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
     150          potential[n] += dijkstra.distMap()[n];
    169151       
    170         //We have to change the potential
    171         for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
    172           potential[n] += dijkstra.distMap()[n];
    173 
    174 
    175152        //Augmenting on the sortest path
    176153        Node n=t;
     
    187164        }
    188165
    189          
     166        return true;
    190167      }
    191      
    192 
     168    }
     169   
     170    /*! \brief Runs the algorithm.
     171   
     172    Runs the algorithm.
     173    Returns k if there is a flow of value at least k from s to t.
     174    Otherwise it returns the maximum value of a flow from s to t.
     175   
     176    \param k The value of the flow we are looking for.
     177   
     178    \todo May be it does make sense to be able to start with a nonzero
     179    feasible primal-dual solution pair as well.
     180   
     181    \todo If the actual flow value is bigger than k, then everything is
     182    cleared and the algorithm starts from zero flow. Is it a good approach?
     183    */
     184    int run(int k) {
     185      if (flowValue()>k) reset();
     186      while (flowValue()<k && augment()) { }
     187      return flowValue();
     188    }
     189
     190    /*! \brief The class is reset to zero flow and potential.
     191      The class is reset to zero flow and potential.
     192     */
     193    void reset() {
     194      total_length=0;
     195      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
     196      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) potential.set(n, 0); 
     197    }
     198
     199    /*! Returns the value of the actual flow.
     200     */
     201    int flowValue() const {
     202      int i=0;
     203      for (typename Graph::OutEdgeIt e(g, s); e!=INVALID; ++e) i+=flow[e];
     204      for (typename Graph::InEdgeIt e(g, s); e!=INVALID; ++e) i-=flow[e];
    193205      return i;
    194206    }
    195207
    196 
    197 
    198     /// Gives back the total weight of the found flow.
    199 
    200     ///This function gives back the total weight of the found flow.
    201     ///Assumes that \c run() has been run and nothing changed since then.
     208    /// Total weight of the found flow.
     209
     210    /// This function gives back the total weight of the found flow.
    202211    Length totalLength(){
    203212      return total_length;
     
    207216
    208217    ///Returns a const reference to the EdgeMap \c flow.
    209     ///\pre \ref run() must
    210     ///be called before using this function.
    211218    const EdgeIntMap &getFlow() const { return flow;}
    212219
    213     ///Returns a const reference to the NodeMap \c potential (the dual solution).
    214 
    215     ///Returns a const reference to the NodeMap \c potential (the dual solution).
    216     /// \pre \ref run() must be called before using this function.
     220    /*! \brief Returns a const reference to the NodeMap \c potential (the dual solution).
     221
     222    Returns a const reference to the NodeMap \c potential (the dual solution).
     223    */
    217224    const PotentialMap &getPotential() const { return potential;}
    218225
    219     /// Checking the complementary slackness optimality criteria
    220 
    221     ///This function checks, whether the given solution is optimal
    222     ///If executed after the call of \c run() then it should return with true.
    223     ///This function only checks optimality, doesn't bother with feasibility.
    224     ///It is meant for testing purposes.
    225     ///
     226    /*! \brief Checking the complementary slackness optimality criteria.
     227
     228    This function checks, whether the given flow and potential
     229    satisfiy the complementary slackness cnditions (i.e. these are optimal).
     230    This function only checks optimality, doesn't bother with feasibility.
     231    For testing purpose.
     232    */
    226233    bool checkComplementarySlackness(){
    227234      Length mod_pot;
    228235      Length fl_e;
    229         for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
     236        for(typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
    230237        //C^{\Pi}_{i,j}
    231         mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
     238        mod_pot = length[e]-potential[g.head(e)]+potential[g.tail(e)];
    232239        fl_e = flow[e];
    233240        if (0<fl_e && fl_e<capacity[e]) {
     
    247254    }
    248255   
    249 
    250256  }; //class MinCostFlow
    251257
  • src/lemon/suurballe.h

    r921 r941  
    6969    typedef ConstMap<Edge,int> ConstMap;
    7070
    71     //Input
    7271    const Graph& G;
     72
     73    Node s;
     74    Node t;
    7375
    7476    //Auxiliary variables
     
    7678    ConstMap const1map;
    7779    //This MinCostFlow instance will actually solve the problem
    78     MinCostFlow<Graph, LengthMap, ConstMap> mincost_flow;
     80    MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
    7981
    8082    //Container to store found paths
     
    8486
    8587
    86     /// The constructor of the class.
    87    
    88     ///\param _G The directed graph the algorithm runs on.
    89     ///\param _length The length (weight or cost) of the edges.
    90     Suurballe(Graph& _G, LengthMap& _length) : G(_G),
    91       const1map(1), mincost_flow(_G, _length, const1map){}
     88    /*! \brief The constructor of the class.
     89   
     90    \param _G The directed graph the algorithm runs on.
     91    \param _length The length (weight or cost) of the edges.
     92    \param _s Source node.
     93    \param _t Target node.
     94    */
     95    Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
     96      G(_G), s(_s), t(_t), const1map(1),
     97      min_cost_flow(_G, _length, const1map, _s, _t) { }
    9298
    9399    ///Runs the algorithm.
     
    95101    ///Runs the algorithm.
    96102    ///Returns k if there are at least k edge-disjoint paths from s to t.
    97     ///Otherwise it returns the number of found edge-disjoint paths from s to t.
     103    ///Otherwise it returns the number of edge-disjoint paths found
     104    ///from s to t.
    98105    ///
    99     ///\param s The source node.
    100     ///\param t The target node.
    101106    ///\param k How many paths are we looking for?
    102107    ///
    103     int run(Node s, Node t, int k) {
    104 
    105       int i = mincost_flow.run(s,t,k);
    106    
     108    int run(int k) {
     109      int i = min_cost_flow.run(k);
    107110
    108111      //Let's find the paths
     
    111114      //We suppose the lengths to be positive now.
    112115
    113       //We don't want to change the flow of mincost_flow, so we make a copy
     116      //We don't want to change the flow of min_cost_flow, so we make a copy
    114117      //The name here suggests that the flow has only 0/1 values.
    115118      EdgeIntMap reversed(G);
    116119
    117120      for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
    118         reversed[e] = mincost_flow.getFlow()[e];
     121        reversed[e] = min_cost_flow.getFlow()[e];
    119122     
    120123      paths.clear();
     
    144147
    145148   
    146     ///Returns the total length of the paths
     149    ///Returns the total length of the paths.
    147150   
    148151    ///This function gives back the total length of the found paths.
    149     ///\pre \ref run() must
    150     ///be called before using this function.
    151152    Length totalLength(){
    152       return mincost_flow.totalLength();
     153      return min_cost_flow.totalLength();
    153154    }
    154155
     
    156157
    157158    ///This function returns a const reference to the EdgeMap \c flow.
    158     ///\pre \ref run() must
    159     ///be called before using this function.
    160     const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
     159    const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
    161160
    162161    /// Returns the optimal dual solution
     
    164163    ///This function returns a const reference to the NodeMap
    165164    ///\c potential (the dual solution).
    166     /// \pre \ref run() must be called before using this function.
    167     const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
     165    const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
    168166
    169167    ///Checks whether the complementary slackness holds.
    170168
    171169    ///This function checks, whether the given solution is optimal.
    172     ///It should return true after calling \ref run()
    173170    ///Currently this function only checks optimality,
    174171    ///doesn't bother with feasibility
    175172    ///It is meant for testing purposes.
    176     ///
    177173    bool checkComplementarySlackness(){
    178       return mincost_flow.checkComplementarySlackness();
     174      return min_cost_flow.checkComplementarySlackness();
    179175    }
    180176
  • src/test/min_cost_flow_test.cc

    r921 r941  
    2222//#include <maps.h>
    2323
    24 using namespace std;
    2524using namespace lemon;
    26 
    2725
    2826
     
    4240int main()
    4341{
     42  typedef ListGraph Graph;
     43  typedef Graph::Node Node;
     44  typedef Graph::Edge Edge;
    4445
    45   typedef ListGraph::Node Node;
    46   typedef ListGraph::Edge Edge;
    47 
    48   ListGraph graph;
     46  Graph graph;
    4947
    5048  //Ahuja könyv példája
     
    6866 
    6967
    70   ListGraph::EdgeMap<int> length(graph);
     68  Graph::EdgeMap<int> length(graph);
    7169
    7270  length.set(s_v1, 6);
     
    7977  length.set(v5_t, 8);
    8078
    81   ListGraph::EdgeMap<int> capacity(graph);
     79  Graph::EdgeMap<int> capacity(graph);
    8280
    8381  capacity.set(s_v1, 2);
     
    9391  std::cout << "Mincostflows algorithm test..." << std::endl;
    9492
    95   MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
    96     surb_test(graph, length, capacity);
     93  MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     94    surb_test(graph, length, capacity, s, t);
    9795
    9896  int k=1;
    9997
    100   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
     98  surb_test.augment();
     99  check(  surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
     100
     101  check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
    101102
    102103  check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
     
    104105  k=2;
    105106 
    106   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
     107  check(  surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
    107108
    108109  check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
    109110 
    110  
     111  surb_test.augment();
     112  surb_test.augment();
     113  surb_test.augment();
    111114  k=4;
    112115
    113   check(  surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
     116  check(  surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
    114117
    115118  check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
    116119
    117120
    118   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    119        << endl;
     121  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
     122            << std::endl;
    120123
    121124  return passed ? 0 : 1;
  • src/test/suurballe_test.cc

    r921 r941  
    2121#include "test_tools.h"
    2222
    23 using namespace std;
    2423using namespace lemon;
    25 
    2624
    2725
     
    3129int main()
    3230{
     31  typedef ListGraph Graph;
     32  typedef Graph::Node Node;
     33  typedef Graph::Edge Edge;
    3334
    34   typedef ListGraph::Node Node;
    35   typedef ListGraph::Edge Edge;
    36 
    37   ListGraph graph;
     35  Graph graph;
    3836
    3937  //Ahuja könyv példája
     
    5755 
    5856
    59   ListGraph::EdgeMap<int> length(graph);
     57  Graph::EdgeMap<int> length(graph);
    6058
    6159  length.set(s_v1, 6);
     
    7270 
    7371  int k=3;
    74   Suurballe< ListGraph, ListGraph::EdgeMap<int> >
    75     surb_test(graph, length);
     72  Suurballe< Graph, Graph::EdgeMap<int> >
     73    surb_test(graph, length, s, t);
    7674
    77   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,
     75  check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
    7876          "Two paths, total length should be 46");
    7977
     
    8179          "Complementary slackness conditions are not met.");
    8280
    83   //  typedef DirPath<ListGraph> DPath;
     81  //  typedef DirPath<Graph> DPath;
    8482  //  DPath P(graph);
    8583
     
    8785  surb_test.getPath(P,0);
    8886  check(P.length() == 4, "First path should contain 4 edges."); 
    89   cout<<P.length()<<endl;
     87  std::cout<<P.length()<<std::endl;
    9088  surb_test.getPath(P,1);
    9189  check(P.length() == 3, "Second path: 3 edges.");
    92   cout<<P.length()<<endl;
     90  std::cout<<P.length()<<std::endl;
    9391  */ 
    9492
    9593  k=1;
    96   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,
     94  check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
    9795          "One path, total length should be 19");
    9896
     
    103101  //  check(P.length() == 4, "First path should contain 4 edges."); 
    104102
    105   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    106        << endl;
     103  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
     104            << std::endl;
    107105
    108106  return passed ? 0 : 1;
Note: See TracChangeset for help on using the changeset viewer.