COIN-OR::LEMON - Graph Library

Changeset 860:3577b3db6089 in lemon-0.x


Ignore:
Timestamp:
09/16/04 12:26:14 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1160
Message:

Completed documentation for mincostflows and minlengthpaths.

Location:
src/hugo
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/mincostflows.h

    r788 r860  
    2424  /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
    2525  /// an algorithm for finding a flow of value \c k
    26   ///(for small values of \c k) having minimal total cost 
     26  /// having minimal total cost 
    2727  /// from a given source node to a given target node in an
    2828  /// edge-weighted directed graph having nonnegative integer capacities.
    29   /// The range of the length (weight) function is nonnegative reals but
    30   /// the range of capacity function is the set of nonnegative integers.
    31   /// It is not a polinomial time algorithm for counting the minimum cost
    32   /// maximal flow, since it counts the minimum cost flow for every value 0..M
    33   /// where \c M is the value of the maximal flow.
     29  /// The range of the length (weight or cost) function can be nonnegative reals but
     30  /// the range of the capacity function has to be the set of nonnegative integers.
     31  /// This algorithm is intended to use only for for small values of \c k, since  /// it is not a polinomial time algorithm for finding the minimum cost
     32  /// maximal flow (in order to find the minimum cost flow of value \c k it
     33  /// finds the minimum cost flow of value \c i for every
     34  /// \c i between 0 and \c k).
     35  ///
     36  ///\param Graph The directed graph type the algorithm runs on.
     37  ///\param LengthMap The type of the length map.
     38  ///\param CapacityMap The capacity map type.
    3439  ///
    3540  ///\author Attila Bernath
    3641  template <typename Graph, typename LengthMap, typename CapacityMap>
    3742  class MinCostFlows {
     43
     44
    3845
    3946    typedef typename LengthMap::ValueType Length;
     
    4855    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    4956
    50     //    typedef ConstMap<Edge,int> ConstMap;
    5157
    5258    typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
     
    5460
    5561    class ModLengthMap {   
    56       //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
    5762      typedef typename Graph::template NodeMap<Length> NodeMap;
    5863      const ResGraphType& G;
    59       //      const EdgeIntMap& rev;
    6064      const LengthMap &ol;
    6165      const NodeMap &pot;
     
    99103  public :
    100104
    101 
     105    /// The constructor of the class.
     106   
     107    ///\param _G The directed graph the algorithm runs on.
     108    ///\param _length The length (weight or cost) of the edges.
     109    ///\param _cap The capacity of the edges.
    102110    MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
    103111      length(_length), capacity(_cap), flow(_G), potential(_G){ }
     
    105113   
    106114    ///Runs the algorithm.
    107 
     115   
    108116    ///Runs the algorithm.
    109     ///Returns k if there are at least k edge-disjoint paths from s to t.
    110     ///Otherwise it returns the number of found edge-disjoint paths from s to t.
     117    ///Returns k if there is a flow of value at least k edge-disjoint
     118    ///from s to t.
     119    ///Otherwise it returns the maximum value of a flow from s to t.
     120    ///
     121    ///\param s The source node.
     122    ///\param t The target node.
     123    ///\param k The value of the flow we are looking for.
     124    ///
    111125    ///\todo May be it does make sense to be able to start with a nonzero
    112126    /// feasible primal-dual solution pair as well.
     
    134148        dijkstra.run(s);
    135149        if (!dijkstra.reached(t)){
    136           //There are no k paths from s to t
     150          //There are no flow of value k from s to t
    137151          break;
    138152        };
     
    166180
    167181
    168 
    169     ///This function gives back the total length of the found paths.
     182    /// Gives back the total weight of the found flow.
     183
     184    ///This function gives back the total weight of the found flow.
    170185    ///Assumes that \c run() has been run and nothing changed since then.
    171186    Length totalLength(){
     
    173188    }
    174189
    175     ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
     190    ///Returns a const reference to the EdgeMap \c flow.
     191
     192    ///Returns a const reference to the EdgeMap \c flow.
     193    ///\pre \ref run() must
    176194    ///be called before using this function.
    177195    const EdgeIntMap &getFlow() const { return flow;}
    178196
    179   ///Returns a const reference to the NodeMap \c potential (the dual solution).
     197    ///Returns a const reference to the NodeMap \c potential (the dual solution).
     198
     199    ///Returns a const reference to the NodeMap \c potential (the dual solution).
    180200    /// \pre \ref run() must be called before using this function.
    181201    const PotentialMap &getPotential() const { return potential;}
    182202
     203    /// Checking the complementary slackness optimality criteria
     204
    183205    ///This function checks, whether the given solution is optimal
    184     ///Running after a \c run() should return with true
    185     ///In this "state of the art" this only check optimality, doesn't bother with feasibility
     206    ///If executed after the call of \c run() then it should return with true.
     207    ///This function only checks optimality, doesn't bother with feasibility.
     208    ///It is meant for testing purposes.
    186209    ///
    187     ///\todo Is this OK here?
    188210    bool checkComplementarySlackness(){
    189211      Length mod_pot;
  • src/hugo/minlengthpaths.h

    r853 r860  
    88
    99
    10 //#include <hugo/dijkstra.h>
    11 //#include <hugo/graph_wrapper.h>
    1210#include <hugo/maps.h>
    1311#include <vector>
     
    1917/// @{
    2018
    21   ///\brief Implementation of an algorithm for finding k paths between 2 nodes
     19  ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
    2220  /// of minimal total length
    2321  ///
    24   /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
     22  /// The class \ref hugo::MinLengthPaths implements
    2523  /// an algorithm for finding k edge-disjoint paths
    2624  /// from a given source node to a given target node in an
    27   /// edge-weighted directed graph having minimal total weigth (length).
     25  /// edge-weighted directed graph having minimal total weight (length).
    2826  ///
    29   ///\warning It is assumed that the lengths are positive, since the
    30   /// general flow-decomposition is not implemented yet.
     27  ///\warning Length values should be nonnegative.
     28  ///
     29  ///\param Graph The directed graph type the algorithm runs on.
     30  ///\param LengthMap The type of the length map (values should be nonnegative).
    3131  ///
    3232  ///\author Attila Bernath
     
    6060
    6161
     62    /// The constructor of the class.
     63   
     64    ///\param _G The directed graph the algorithm runs on.
     65    ///\param _length The length (weight or cost) of the edges.
    6266    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
    6367      const1map(1), mincost_flow(_G, _length, const1map){}
     
    6872    ///Returns k if there are at least k edge-disjoint paths from s to t.
    6973    ///Otherwise it returns the number of found edge-disjoint paths from s to t.
     74    ///
     75    ///\param s The source node.
     76    ///\param t The target node.
     77    ///\param k How many paths are we looking for?
     78    ///
    7079    int run(Node s, Node t, int k) {
    7180
    7281      int i = mincost_flow.run(s,t,k);
    73      
    74 
     82   
    7583
    7684      //Let's find the paths
     
    112120
    113121   
    114     ///Total length of the paths
     122    ///Returns the total length of the paths
    115123   
    116124    ///This function gives back the total length of the found paths.
     
    121129    }
    122130
    123     ///Return the found flow.
     131    ///Returns the found flow.
    124132
    125133    ///This function returns a const reference to the EdgeMap \c flow.
     
    128136    const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
    129137
    130     /// Return the optimal dual solution
     138    /// Returns the optimal dual solution
    131139   
    132140    ///This function returns a const reference to the NodeMap
     
    137145    ///Checks whether the complementary slackness holds.
    138146
    139     ///This function checks, whether the given solution is optimal
    140     ///Running after a \c run() should return with true
     147    ///This function checks, whether the given solution is optimal.
     148    ///It should return true after calling \ref run()
    141149    ///Currently this function only checks optimality,
    142150    ///doesn't bother with feasibility
     151    ///It is meant for testing purposes.
    143152    ///
    144     ///\todo Is this OK here?
    145153    bool checkComplementarySlackness(){
    146154      return mincost_flow.checkComplementarySlackness();
     
    155163    ///If \c j is not less than the result of previous \c run,
    156164    ///then the result here will be an empty path (\c j can be 0 as well).
     165    ///
     166    ///\param Path The type of the path structure to put the result to (must meet hugo path concept).
     167    ///\param p The path to put the result to
     168    ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
    157169    template<typename Path>
    158170    void getPath(Path& p, size_t j){
    159      
     171
    160172      p.clear();
    161173      if (j>paths.size()-1){
Note: See TracChangeset for help on using the changeset viewer.