# Changeset 860:3577b3db6089 in lemon-0.x

Ignore:
Timestamp:
09/16/04 12:26:14 (17 years ago)
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

Unmodified
Added
Removed
• ## src/hugo/mincostflows.h

 r788 /// 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 capacity function is the set of nonnegative integers. /// It is not a polinomial time algorithm for counting the minimum cost /// maximal flow, since it counts the minimum cost flow for every value 0..M /// where \c M is the value of the maximal flow. /// The range of the length (weight or cost) function can be nonnegative reals but /// the range of the capacity function has to be the set of nonnegative integers. /// 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 (in order to find the minimum cost flow of value \c k it /// 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 class MinCostFlows { typedef typename LengthMap::ValueType Length; typedef typename Graph::template EdgeMap EdgeIntMap; //    typedef ConstMap ConstMap; typedef ResGraphWrapper ResGraphType; class ModLengthMap { //typedef typename ResGraphType::template NodeMap NodeMap; typedef typename Graph::template NodeMap NodeMap; const ResGraphType& G; //      const EdgeIntMap& rev; const LengthMap &ol; const NodeMap &pot; 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. ///Otherwise it returns the number of found edge-disjoint paths from s to t. ///Returns k if there is a flow of value at least k edge-disjoint ///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. 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; }; ///This function gives back the total length of the found paths. /// Gives back the total weight of the found flow. ///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(){ } ///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). ///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 ///In this "state of the art" this only check optimality, doesn't bother with feasibility ///If executed after the call of \c run() then it should return with true. ///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;
• ## src/hugo/minlengthpaths.h

 r853 //#include //#include #include #include /// @{ ///\brief Implementation of an algorithm for finding k paths between 2 nodes ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes /// of minimal total length /// /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements /// The class \ref hugo::MinLengthPaths implements /// an algorithm for finding k edge-disjoint paths /// from a given source node to a given target node in an /// edge-weighted directed graph having minimal total weigth (length). /// edge-weighted directed graph having minimal total weight (length). /// ///\warning It is assumed that the lengths are positive, since the /// general flow-decomposition is not implemented yet. ///\warning Length values should be nonnegative. /// ///\param Graph The directed graph type the algorithm runs on. ///\param LengthMap The type of the length map (values should be nonnegative). /// ///\author Attila Bernath /// The constructor of the class. ///\param _G The directed graph the algorithm runs on. ///\param _length The length (weight or cost) of the edges. MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), const1map(1), mincost_flow(_G, _length, const1map){} ///Returns k if there are at least k edge-disjoint paths from s to t. ///Otherwise it returns the number of found edge-disjoint paths from s to t. /// ///\param s The source node. ///\param t The target node. ///\param k How many paths are we looking for? /// int run(Node s, Node t, int k) { int i = mincost_flow.run(s,t,k); //Let's find the paths ///Total length of the paths ///Returns the total length of the paths ///This function gives back the total length of the found paths. } ///Return the found flow. ///Returns the found flow. ///This function returns a const reference to the EdgeMap \c flow. const EdgeIntMap &getFlow() const { return mincost_flow.flow;} /// Return the optimal dual solution /// Returns the optimal dual solution ///This function returns a const reference to the NodeMap ///Checks whether the complementary slackness holds. ///This function checks, whether the given solution is optimal ///Running after a \c run() should return with true ///This function checks, whether the given solution is optimal. ///It should return true after calling \ref run() ///Currently this function only checks optimality, ///doesn't bother with feasibility ///It is meant for testing purposes. /// ///\todo Is this OK here? bool checkComplementarySlackness(){ return mincost_flow.checkComplementarySlackness(); ///If \c j is not less than the result of previous \c run, ///then the result here will be an empty path (\c j can be 0 as well). /// ///\param Path The type of the path structure to put the result to (must meet hugo path concept). ///\param p The path to put the result to ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively) template void getPath(Path& p, size_t j){ p.clear(); if (j>paths.size()-1){
Note: See TracChangeset for help on using the changeset viewer.