COIN-OR::LEMON - Graph Library

Changeset 941:186aa53d2802 in lemon-0.x for src/lemon/suurballe.h


Ignore:
Timestamp:
10/08/04 15:07:51 (20 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()

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.