1.1 --- a/src/hugo/minlengthpaths.h Wed Sep 15 14:38:13 2004 +0000
1.2 +++ b/src/hugo/minlengthpaths.h Thu Sep 16 10:26:14 2004 +0000
1.3 @@ -7,8 +7,6 @@
1.4 ///\brief An algorithm for finding k paths of minimal total length.
1.5
1.6
1.7 -//#include <hugo/dijkstra.h>
1.8 -//#include <hugo/graph_wrapper.h>
1.9 #include <hugo/maps.h>
1.10 #include <vector>
1.11 #include <hugo/mincostflows.h>
1.12 @@ -18,16 +16,18 @@
1.13 /// \addtogroup flowalgs
1.14 /// @{
1.15
1.16 - ///\brief Implementation of an algorithm for finding k paths between 2 nodes
1.17 + ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes
1.18 /// of minimal total length
1.19 ///
1.20 - /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
1.21 + /// The class \ref hugo::MinLengthPaths implements
1.22 /// an algorithm for finding k edge-disjoint paths
1.23 /// from a given source node to a given target node in an
1.24 - /// edge-weighted directed graph having minimal total weigth (length).
1.25 + /// edge-weighted directed graph having minimal total weight (length).
1.26 ///
1.27 - ///\warning It is assumed that the lengths are positive, since the
1.28 - /// general flow-decomposition is not implemented yet.
1.29 + ///\warning Length values should be nonnegative.
1.30 + ///
1.31 + ///\param Graph The directed graph type the algorithm runs on.
1.32 + ///\param LengthMap The type of the length map (values should be nonnegative).
1.33 ///
1.34 ///\author Attila Bernath
1.35 template <typename Graph, typename LengthMap>
1.36 @@ -59,6 +59,10 @@
1.37 public :
1.38
1.39
1.40 + /// The constructor of the class.
1.41 +
1.42 + ///\param _G The directed graph the algorithm runs on.
1.43 + ///\param _length The length (weight or cost) of the edges.
1.44 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
1.45 const1map(1), mincost_flow(_G, _length, const1map){}
1.46
1.47 @@ -67,11 +71,15 @@
1.48 ///Runs the algorithm.
1.49 ///Returns k if there are at least k edge-disjoint paths from s to t.
1.50 ///Otherwise it returns the number of found edge-disjoint paths from s to t.
1.51 + ///
1.52 + ///\param s The source node.
1.53 + ///\param t The target node.
1.54 + ///\param k How many paths are we looking for?
1.55 + ///
1.56 int run(Node s, Node t, int k) {
1.57
1.58 int i = mincost_flow.run(s,t,k);
1.59 -
1.60 -
1.61 +
1.62
1.63 //Let's find the paths
1.64 //We put the paths into stl vectors (as an inner representation).
1.65 @@ -111,7 +119,7 @@
1.66 }
1.67
1.68
1.69 - ///Total length of the paths
1.70 + ///Returns the total length of the paths
1.71
1.72 ///This function gives back the total length of the found paths.
1.73 ///\pre \ref run() must
1.74 @@ -120,14 +128,14 @@
1.75 return mincost_flow.totalLength();
1.76 }
1.77
1.78 - ///Return the found flow.
1.79 + ///Returns the found flow.
1.80
1.81 ///This function returns a const reference to the EdgeMap \c flow.
1.82 ///\pre \ref run() must
1.83 ///be called before using this function.
1.84 const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
1.85
1.86 - /// Return the optimal dual solution
1.87 + /// Returns the optimal dual solution
1.88
1.89 ///This function returns a const reference to the NodeMap
1.90 ///\c potential (the dual solution).
1.91 @@ -136,12 +144,12 @@
1.92
1.93 ///Checks whether the complementary slackness holds.
1.94
1.95 - ///This function checks, whether the given solution is optimal
1.96 - ///Running after a \c run() should return with true
1.97 + ///This function checks, whether the given solution is optimal.
1.98 + ///It should return true after calling \ref run()
1.99 ///Currently this function only checks optimality,
1.100 ///doesn't bother with feasibility
1.101 + ///It is meant for testing purposes.
1.102 ///
1.103 - ///\todo Is this OK here?
1.104 bool checkComplementarySlackness(){
1.105 return mincost_flow.checkComplementarySlackness();
1.106 }
1.107 @@ -154,9 +162,13 @@
1.108 ///be a path of graph \c G.
1.109 ///If \c j is not less than the result of previous \c run,
1.110 ///then the result here will be an empty path (\c j can be 0 as well).
1.111 + ///
1.112 + ///\param Path The type of the path structure to put the result to (must meet hugo path concept).
1.113 + ///\param p The path to put the result to
1.114 + ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
1.115 template<typename Path>
1.116 void getPath(Path& p, size_t j){
1.117 -
1.118 +
1.119 p.clear();
1.120 if (j>paths.size()-1){
1.121 return;