COIN-OR::LEMON - Graph Library

Changeset 2276:1a8a66b6c6ce in lemon-0.x


Ignore:
Timestamp:
10/30/06 18:22:14 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3039
Message:

Min cost flow is renamed to SspMinCostFlow?

Files:
1 added
1 deleted
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r2260 r2276  
    7777        lemon/max_matching.h \
    7878        lemon/min_cost_arborescence.h \
    79         lemon/min_cost_flow.h \
    8079        lemon/min_cut.h \
    8180        lemon/mip_glpk.h \
     
    9190        lemon/simann.h \
    9291        lemon/smart_graph.h \
     92        lemon/ssp_min_cost_flow.h \
    9393        lemon/sub_graph.h \
    9494        lemon/suurballe.h \
  • lemon/suurballe.h

    r1956 r2276  
    2727#include <lemon/maps.h>
    2828#include <vector>
    29 #include <lemon/min_cost_flow.h>
     29#include <lemon/ssp_min_cost_flow.h>
    3030
    3131namespace lemon {
     
    3434/// @{
    3535
    36   ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
    37   /// of minimal total length
     36  ///\brief Implementation of an algorithm for finding k edge-disjoint
     37  /// paths between 2 nodes of minimal total length
    3838  ///
    3939  /// The class \ref lemon::Suurballe implements
     
    5050  ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm
    5151  ///for finding minimum cost flows. In fact, this implementation just
    52   ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and
     52  ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and
    5353  ///Edmonds-Karp published in 1972, therefore it is possibly right to
    5454  ///state that they are
     
    8080    ConstMap const1map;
    8181    //This MinCostFlow instance will actually solve the problem
    82     MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
     82    SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
    8383
    8484    //Container to store found paths
     
    8888
    8989
    90     /*! \brief The constructor of the class.
    91    
    92     \param _G The directed graph the algorithm runs on.
    93     \param _length The length (weight or cost) of the edges.
    94     \param _s Source node.
    95     \param _t Target node.
    96     */
     90    /// \brief The constructor of the class.
     91    ///
     92    /// \param _G The directed graph the algorithm runs on.
     93    /// \param _length The length (weight or cost) of the edges.
     94    /// \param _s Source node.
     95    /// \param _t Target node.
    9796    Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
    9897      G(_G), s(_s), t(_t), const1map(1),
    9998      min_cost_flow(_G, _length, const1map, _s, _t) { }
    10099
    101     ///Runs the algorithm.
    102 
    103     ///Runs the algorithm.
    104     ///Returns k if there are at least k edge-disjoint paths from s to t.
    105     ///Otherwise it returns the number of edge-disjoint paths found
    106     ///from s to t.
    107     ///
    108     ///\param k How many paths are we looking for?
     100    /// \brief Runs the algorithm.
     101    ///
     102    /// Runs the algorithm.
     103    /// Returns k if there are at least k edge-disjoint paths from s to t.
     104    /// Otherwise it returns the number of edge-disjoint paths found
     105    /// from s to t.
     106    ///
     107    /// \param k How many paths are we looking for?
    109108    ///
    110109    int run(int k) {
     
    145144
    146145   
    147     ///Returns the total length of the paths.
    148    
    149     ///This function gives back the total length of the found paths.
     146    /// \brief Returns the total length of the paths.
     147    ///
     148    /// This function gives back the total length of the found paths.
    150149    Length totalLength(){
    151150      return min_cost_flow.totalLength();
    152151    }
    153152
    154     ///Returns the found flow.
    155 
    156     ///This function returns a const reference to the EdgeMap \c flow.
     153    /// \brief Returns the found flow.
     154    ///
     155    /// This function returns a const reference to the EdgeMap \c flow.
    157156    const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
    158157
    159     /// Returns the optimal dual solution
    160    
    161     ///This function returns a const reference to the NodeMap
    162     ///\c potential (the dual solution).
     158    /// \brief Returns the optimal dual solution
     159    ///
     160    /// This function returns a const reference to the NodeMap \c
     161    /// potential (the dual solution).
    163162    const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
    164163
    165     ///Checks whether the complementary slackness holds.
    166 
    167     ///This function checks, whether the given solution is optimal.
    168     ///Currently this function only checks optimality,
    169     ///doesn't bother with feasibility.
    170     ///It is meant for testing purposes.
     164    /// \brief Checks whether the complementary slackness holds.
     165    ///
     166    /// This function checks, whether the given solution is optimal.
     167    /// Currently this function only checks optimality, doesn't bother
     168    /// with feasibility.  It is meant for testing purposes.
    171169    bool checkComplementarySlackness(){
    172170      return min_cost_flow.checkComplementarySlackness();
    173171    }
    174172
    175     ///Read the found paths.
    176    
    177     ///This function gives back the \c j-th path in argument p.
    178     ///Assumes that \c run() has been run and nothing has changed since then.
    179     /// \warning It is assumed that \c p is constructed to
    180     ///be a path of graph \c G.
    181     ///If \c j is not less than the result of previous \c run,
    182     ///then the result here will be an empty path (\c j can be 0 as well).
    183     ///
    184     ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
    185     ///\param p The path to put the result to.
    186     ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively).
     173    /// \brief Read the found paths.
     174    ///
     175    /// This function gives back the \c j-th path in argument p.
     176    /// Assumes that \c run() has been run and nothing has changed
     177    /// since then.
     178    ///
     179    /// \warning It is assumed that \c p is constructed to be a path
     180    /// of graph \c G.  If \c j is not less than the result of
     181    /// previous \c run, then the result here will be an empty path
     182    /// (\c j can be 0 as well).
     183    ///
     184    /// \param Path The type of the path structure to put the result
     185    /// to (must meet lemon path concept).
     186    /// \param p The path to put the result to.
     187    /// \param j Which path you want to get from the found paths (in a
     188    /// real application you would get the found paths iteratively).
    187189    template<typename Path>
    188190    void getPath(Path& p, size_t j){
  • test/min_cost_flow_test.cc

    r1956 r2276  
    2020#include "test_tools.h"
    2121#include <lemon/list_graph.h>
    22 #include <lemon/min_cost_flow.h>
     22#include <lemon/ssp_min_cost_flow.h>
    2323//#include <path.h>
    2424//#include <maps.h>
     
    9393  std::cout << "Mincostflows algorithm test..." << std::endl;
    9494
    95   MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     95  SspMinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    9696    surb_test(graph, length, capacity, s, t);
    9797
Note: See TracChangeset for help on using the changeset viewer.