lemon-0.x: comparison src/hugo/mincostflows.h

equal deleted inserted replaced

-:46c9b06aad62
+:256be900925e
 ///(for small values of \c k) having minimal total cost between 2 nodes
 ///
 ///
 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
 /// an algorithm for finding a flow of value \c k
-///(for small values of \c k) having minimal total cost
+/// having minimal total cost
 /// from a given source node to a given target node in an
 /// edge-weighted directed graph having nonnegative integer capacities.
-/// The range of the length (weight) function is nonnegative reals but
+/// The range of the length (weight or cost) function can be nonnegative reals but
-/// the range of capacity function is the set of nonnegative integers.
+/// the range of the capacity function has to be the set of nonnegative integers.
-/// It is not a polinomial time algorithm for counting the minimum cost
+/// 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
-/// maximal flow, since it counts the minimum cost flow for every value 0..M
+/// maximal flow (in order to find the minimum cost flow of value \c k it
-/// where \c M is the value of the maximal flow.
+/// finds the minimum cost flow of value \c i for every
+/// \c i between 0 and \c k).
+///
+///\param Graph The directed graph type the algorithm runs on.
+///\param LengthMap The type of the length map.
+///\param CapacityMap The capacity map type.
 ///
 ///\author Attila Bernath
 template <typename Graph, typename LengthMap, typename CapacityMap>
 class MinCostFlows {
 typedef typename LengthMap::ValueType Length;
 //Warning: this should be integer type
 typedef typename CapacityMap::ValueType Capacity;
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Edge Edge;
 typedef typename Graph::OutEdgeIt OutEdgeIt;
 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
-//    typedef ConstMap<Edge,int> ConstMap;
 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
 typedef typename ResGraphType::Edge ResGraphEdge;
 class ModLengthMap {
-//typedef typename ResGraphType::template NodeMap<Length> NodeMap;
 typedef typename Graph::template NodeMap<Length> NodeMap;
 const ResGraphType& G;
-//      const EdgeIntMap& rev;
 const LengthMap &ol;
 const NodeMap &pot;
 public :
 typedef typename LengthMap::KeyType KeyType;
 typedef typename LengthMap::ValueType ValueType;
 Length total_length;
 public :
+/// The constructor of the class.
+///\param _G The directed graph the algorithm runs on.
+///\param _length The length (weight or cost) of the edges.
+///\param _cap The capacity of the edges.
 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
 length(_length), capacity(_cap), flow(_G), potential(_G){ }
 ///Runs the algorithm.
 ///Runs the algorithm.
-///Returns k if there are at least k edge-disjoint paths from s to t.
+///Returns k if there is a flow of value at least k edge-disjoint
-///Otherwise it returns the number of found edge-disjoint paths from s to t.
+///from s to t.
+///Otherwise it returns the maximum value of a flow from s to t.
+///
+///\param s The source node.
+///\param t The target node.
+///\param k The value of the flow we are looking for.
+///
 ///\todo May be it does make sense to be able to start with a nonzero
 /// feasible primal-dual solution pair as well.
 int run(Node s, Node t, int k) {
 //Resetting variables from previous runs
 int i;
 for (i=0; i<k; ++i){
 	dijkstra.run(s);
 	if (!dijkstra.reached(t)){
-	  //There are no k paths from s to t
+	  //There are no flow of value k from s to t
 	  break;
 	};
 	//We have to change the potential
 for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n)
 return i;
 }
+/// Gives back the total weight of the found flow.
-///This function gives back the total length of the found paths.
+///This function gives back the total weight of the found flow.
 ///Assumes that \c run() has been run and nothing changed since then.
 Length totalLength(){
 return total_length;
 }
-///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
+///Returns a const reference to the EdgeMap \c flow.
+///Returns a const reference to the EdgeMap \c flow.
+///\pre \ref run() must
 ///be called before using this function.
 const EdgeIntMap &getFlow() const { return flow;}
 ///Returns a const reference to the NodeMap \c potential (the dual solution).
+///Returns a const reference to the NodeMap \c potential (the dual solution).
 /// \pre \ref run() must be called before using this function.
 const PotentialMap &getPotential() const { return potential;}
+/// Checking the complementary slackness optimality criteria
 ///This function checks, whether the given solution is optimal
-///Running after a \c run() should return with true
+///If executed after the call of \c run() then it should return with true.
-///In this "state of the art" this only check optimality, doesn't bother with feasibility
+///This function only checks optimality, doesn't bother with feasibility.
+///It is meant for testing purposes.
 ///
-///\todo Is this OK here?
 bool checkComplementarySlackness(){
 Length mod_pot;
 Length fl_e;
 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
 	//C^{\Pi}_{i,j}

changeset 870	9bde6cd8e3da
parent 788	c3187cafcabf
child 893	89d5c283a485