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;
2.1 --- a/src/hugo/minlengthpaths.h Wed Sep 15 14:38:13 2004 +0000
2.2 +++ b/src/hugo/minlengthpaths.h Thu Sep 16 10:26:14 2004 +0000
2.3 @@ -7,8 +7,6 @@
2.4 ///\brief An algorithm for finding k paths of minimal total length.
2.5
2.6
2.7 -//#include <hugo/dijkstra.h>
2.8 -//#include <hugo/graph_wrapper.h>
2.9 #include <hugo/maps.h>
2.10 #include <vector>
2.11 #include <hugo/mincostflows.h>
2.12 @@ -18,16 +16,18 @@
2.13 /// \addtogroup flowalgs
2.14 /// @{
2.15
2.16 - ///\brief Implementation of an algorithm for finding k paths between 2 nodes
2.17 + ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
2.18 /// of minimal total length
2.19 ///
2.20 - /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
2.21 + /// The class \ref hugo::MinLengthPaths implements
2.22 /// an algorithm for finding k edge-disjoint paths
2.23 /// from a given source node to a given target node in an
2.24 - /// edge-weighted directed graph having minimal total weigth (length).
2.25 + /// edge-weighted directed graph having minimal total weight (length).
2.26 ///
2.27 - ///\warning It is assumed that the lengths are positive, since the
2.28 - /// general flow-decomposition is not implemented yet.
2.29 + ///\warning Length values should be nonnegative.
2.30 + ///
2.31 + ///\param Graph The directed graph type the algorithm runs on.
2.32 + ///\param LengthMap The type of the length map (values should be nonnegative).
2.33 ///
2.34 ///\author Attila Bernath
2.35 template <typename Graph, typename LengthMap>
2.36 @@ -59,6 +59,10 @@
2.37 public :
2.38
2.39
2.40 + /// The constructor of the class.
2.41 +
2.42 + ///\param _G The directed graph the algorithm runs on.
2.43 + ///\param _length The length (weight or cost) of the edges.
2.44 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
2.45 const1map(1), mincost_flow(_G, _length, const1map){}
2.46
2.47 @@ -67,11 +71,15 @@
2.48 ///Runs the algorithm.
2.49 ///Returns k if there are at least k edge-disjoint paths from s to t.
2.50 ///Otherwise it returns the number of found edge-disjoint paths from s to t.
2.51 + ///
2.52 + ///\param s The source node.
2.53 + ///\param t The target node.
2.54 + ///\param k How many paths are we looking for?
2.55 + ///
2.56 int run(Node s, Node t, int k) {
2.57
2.58 int i = mincost_flow.run(s,t,k);
2.59 -
2.60 -
2.61 +
2.62
2.63 //Let's find the paths
2.64 //We put the paths into stl vectors (as an inner representation).
2.65 @@ -111,7 +119,7 @@
2.66 }
2.67
2.68
2.69 - ///Total length of the paths
2.70 + ///Returns the total length of the paths
2.71
2.72 ///This function gives back the total length of the found paths.
2.73 ///\pre \ref run() must
2.74 @@ -120,14 +128,14 @@
2.75 return mincost_flow.totalLength();
2.76 }
2.77
2.78 - ///Return the found flow.
2.79 + ///Returns the found flow.
2.80
2.81 ///This function returns a const reference to the EdgeMap \c flow.
2.82 ///\pre \ref run() must
2.83 ///be called before using this function.
2.84 const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
2.85
2.86 - /// Return the optimal dual solution
2.87 + /// Returns the optimal dual solution
2.88
2.89 ///This function returns a const reference to the NodeMap
2.90 ///\c potential (the dual solution).
2.91 @@ -136,12 +144,12 @@
2.92
2.93 ///Checks whether the complementary slackness holds.
2.94
2.95 - ///This function checks, whether the given solution is optimal
2.96 - ///Running after a \c run() should return with true
2.97 + ///This function checks, whether the given solution is optimal.
2.98 + ///It should return true after calling \ref run()
2.99 ///Currently this function only checks optimality,
2.100 ///doesn't bother with feasibility
2.101 + ///It is meant for testing purposes.
2.102 ///
2.103 - ///\todo Is this OK here?
2.104 bool checkComplementarySlackness(){
2.105 return mincost_flow.checkComplementarySlackness();
2.106 }
2.107 @@ -154,9 +162,13 @@
2.108 ///be a path of graph \c G.
2.109 ///If \c j is not less than the result of previous \c run,
2.110 ///then the result here will be an empty path (\c j can be 0 as well).
2.111 + ///
2.112 + ///\param Path The type of the path structure to put the result to (must meet hugo path concept).
2.113 + ///\param p The path to put the result to
2.114 + ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
2.115 template<typename Path>
2.116 void getPath(Path& p, size_t j){
2.117 -
2.118 +
2.119 p.clear();
2.120 if (j>paths.size()-1){
2.121 return;