1.1 --- a/src/hugo/mincostflows.h Wed Sep 15 14:38:13 2004 +0000
1.2 +++ b/src/hugo/mincostflows.h Thu Sep 16 10:26:14 2004 +0000
1.3 @@ -23,19 +23,26 @@
1.4 ///
1.5 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
1.6 /// an algorithm for finding a flow of value \c k
1.7 - ///(for small values of \c k) having minimal total cost
1.8 + /// having minimal total cost
1.9 /// from a given source node to a given target node in an
1.10 /// edge-weighted directed graph having nonnegative integer capacities.
1.11 - /// The range of the length (weight) function is nonnegative reals but
1.12 - /// the range of capacity function is the set of nonnegative integers.
1.13 - /// It is not a polinomial time algorithm for counting the minimum cost
1.14 - /// maximal flow, since it counts the minimum cost flow for every value 0..M
1.15 - /// where \c M is the value of the maximal flow.
1.16 + /// The range of the length (weight or cost) function can be nonnegative reals but
1.17 + /// the range of the capacity function has to be the set of nonnegative integers.
1.18 + /// 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
1.19 + /// maximal flow (in order to find the minimum cost flow of value \c k it
1.20 + /// finds the minimum cost flow of value \c i for every
1.21 + /// \c i between 0 and \c k).
1.22 + ///
1.23 + ///\param Graph The directed graph type the algorithm runs on.
1.24 + ///\param LengthMap The type of the length map.
1.25 + ///\param CapacityMap The capacity map type.
1.26 ///
1.27 ///\author Attila Bernath
1.28 template <typename Graph, typename LengthMap, typename CapacityMap>
1.29 class MinCostFlows {
1.30
1.31 +
1.32 +
1.33 typedef typename LengthMap::ValueType Length;
1.34
1.35 //Warning: this should be integer type
1.36 @@ -47,16 +54,13 @@
1.37 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.38 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
1.39
1.40 - // typedef ConstMap<Edge,int> ConstMap;
1.41
1.42 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
1.43 typedef typename ResGraphType::Edge ResGraphEdge;
1.44
1.45 class ModLengthMap {
1.46 - //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
1.47 typedef typename Graph::template NodeMap<Length> NodeMap;
1.48 const ResGraphType& G;
1.49 - // const EdgeIntMap& rev;
1.50 const LengthMap &ol;
1.51 const NodeMap &pot;
1.52 public :
1.53 @@ -98,16 +102,26 @@
1.54
1.55 public :
1.56
1.57 -
1.58 + /// The constructor of the class.
1.59 +
1.60 + ///\param _G The directed graph the algorithm runs on.
1.61 + ///\param _length The length (weight or cost) of the edges.
1.62 + ///\param _cap The capacity of the edges.
1.63 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
1.64 length(_length), capacity(_cap), flow(_G), potential(_G){ }
1.65
1.66
1.67 ///Runs the algorithm.
1.68 -
1.69 +
1.70 ///Runs the algorithm.
1.71 - ///Returns k if there are at least k edge-disjoint paths from s to t.
1.72 - ///Otherwise it returns the number of found edge-disjoint paths from s to t.
1.73 + ///Returns k if there is a flow of value at least k edge-disjoint
1.74 + ///from s to t.
1.75 + ///Otherwise it returns the maximum value of a flow from s to t.
1.76 + ///
1.77 + ///\param s The source node.
1.78 + ///\param t The target node.
1.79 + ///\param k The value of the flow we are looking for.
1.80 + ///
1.81 ///\todo May be it does make sense to be able to start with a nonzero
1.82 /// feasible primal-dual solution pair as well.
1.83 int run(Node s, Node t, int k) {
1.84 @@ -133,7 +147,7 @@
1.85 for (i=0; i<k; ++i){
1.86 dijkstra.run(s);
1.87 if (!dijkstra.reached(t)){
1.88 - //There are no k paths from s to t
1.89 + //There are no flow of value k from s to t
1.90 break;
1.91 };
1.92
1.93 @@ -165,26 +179,34 @@
1.94
1.95
1.96
1.97 + /// Gives back the total weight of the found flow.
1.98
1.99 - ///This function gives back the total length of the found paths.
1.100 + ///This function gives back the total weight of the found flow.
1.101 ///Assumes that \c run() has been run and nothing changed since then.
1.102 Length totalLength(){
1.103 return total_length;
1.104 }
1.105
1.106 - ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
1.107 + ///Returns a const reference to the EdgeMap \c flow.
1.108 +
1.109 + ///Returns a const reference to the EdgeMap \c flow.
1.110 + ///\pre \ref run() must
1.111 ///be called before using this function.
1.112 const EdgeIntMap &getFlow() const { return flow;}
1.113
1.114 - ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.115 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.116 +
1.117 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.118 /// \pre \ref run() must be called before using this function.
1.119 const PotentialMap &getPotential() const { return potential;}
1.120
1.121 + /// Checking the complementary slackness optimality criteria
1.122 +
1.123 ///This function checks, whether the given solution is optimal
1.124 - ///Running after a \c run() should return with true
1.125 - ///In this "state of the art" this only check optimality, doesn't bother with feasibility
1.126 + ///If executed after the call of \c run() then it should return with true.
1.127 + ///This function only checks optimality, doesn't bother with feasibility.
1.128 + ///It is meant for testing purposes.
1.129 ///
1.130 - ///\todo Is this OK here?
1.131 bool checkComplementarySlackness(){
1.132 Length mod_pot;
1.133 Length fl_e;