1.1 --- a/src/hugo/minlengthpaths.h Tue Sep 14 10:23:26 2004 +0000
1.2 +++ b/src/hugo/minlengthpaths.h Tue Sep 14 10:29:47 2004 +0000
1.3 @@ -66,7 +66,7 @@
1.4
1.5 ///Runs the algorithm.
1.6 ///Returns k if there are at least k edge-disjoint paths from s to t.
1.7 - ///Otherwise it returns the number of found edge-disjoint paths from s to t.
1.8 + ///Otherwise it returns the number of found edge-disjoint paths from s to t.
1.9 int run(Node s, Node t, int k) {
1.10
1.11 int i = mincost_flow.run(s,t,k);
1.12 @@ -111,34 +111,51 @@
1.13 }
1.14
1.15
1.16 + ///Total length of the paths
1.17 +
1.18 ///This function gives back the total length of the found paths.
1.19 - ///Assumes that \c run() has been run and nothing changed since then.
1.20 + ///\pre \ref run() must
1.21 + ///be called before using this function.
1.22 Length totalLength(){
1.23 return mincost_flow.totalLength();
1.24 }
1.25
1.26 - ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
1.27 + ///Return the found flow.
1.28 +
1.29 + ///This function returns a const reference to the EdgeMap \c flow.
1.30 + ///\pre \ref run() must
1.31 ///be called before using this function.
1.32 const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
1.33
1.34 - ///Returns a const reference to the NodeMap \c potential (the dual solution).
1.35 + /// Return the optimal dual solution
1.36 +
1.37 + ///This function returns a const reference to the NodeMap
1.38 + ///\c potential (the dual solution).
1.39 /// \pre \ref run() must be called before using this function.
1.40 const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
1.41
1.42 + ///Checks whether the complementary slackness holds.
1.43 +
1.44 ///This function checks, whether the given solution is optimal
1.45 ///Running after a \c run() should return with true
1.46 - ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
1.47 + ///Currently this function only checks optimality,
1.48 + ///doesn't bother with feasibility
1.49 ///
1.50 ///\todo Is this OK here?
1.51 bool checkComplementarySlackness(){
1.52 return mincost_flow.checkComplementarySlackness();
1.53 }
1.54
1.55 + ///Read the found paths.
1.56 +
1.57 ///This function gives back the \c j-th path in argument p.
1.58 ///Assumes that \c run() has been run and nothing changed since then.
1.59 - /// \warning It is assumed that \c p is constructed to be a path of graph \c G. 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).
1.60 - template<typename DirPath>
1.61 - void getPath(DirPath& p, size_t j){
1.62 + /// \warning It is assumed that \c p is constructed to
1.63 + ///be a path of graph \c G.
1.64 + ///If \c j is not less than the result of previous \c run,
1.65 + ///then the result here will be an empty path (\c j can be 0 as well).
1.66 + template<typename Path>
1.67 + void getPath(Path& p, size_t j){
1.68
1.69 p.clear();
1.70 if (j>paths.size()-1){
2.1 --- a/src/hugo/preflow.h Tue Sep 14 10:23:26 2004 +0000
2.2 +++ b/src/hugo/preflow.h Tue Sep 14 10:29:47 2004 +0000
2.3 @@ -16,22 +16,22 @@
2.4 /// \addtogroup flowalgs
2.5 /// @{
2.6
2.7 - ///Preflow algorithms class.
2.8 + ///%Preflow algorithms class.
2.9
2.10 ///This class provides an implementation of the \e preflow \e
2.11 ///algorithm producing a flow of maximum value in a directed
2.12 ///graph. The preflow algorithms are the fastest max flow algorithms
2.13 - ///up-to-date. The \e source node, the \e target node, the \e
2.14 + ///up to now. The \e source node, the \e target node, the \e
2.15 ///capacity of the edges and the \e starting \e flow value of the
2.16 ///edges should be passed to the algorithm through the
2.17 ///constructor. It is possible to change these quantities using the
2.18 ///functions \ref setSource, \ref setTarget, \ref setCap and \ref
2.19 ///setFlow.
2.20 ///
2.21 - ///After running \c phase1 or \c preflow, the actual flow
2.22 + ///After running \ref phase1() or \ref preflow(), the actual flow
2.23 ///value can be obtained by calling \ref flowValue(). The minimum
2.24 - ///value cut can be written into a \c node map of \c bools by
2.25 - ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes
2.26 + ///value cut can be written into a <tt>bool</tt> node map by
2.27 + ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes
2.28 ///the inclusionwise minimum and maximum of the minimum value cuts,
2.29 ///resp.)
2.30 ///
2.31 @@ -129,7 +129,8 @@
2.32
2.33 ///Runs the preflow algorithm.
2.34
2.35 - ///Runs the preflow algorithm.
2.36 + ///Runs the preflow algorithm.
2.37 + ///
2.38 void run() {
2.39 phase1(flow_prop);
2.40 phase2();
2.41 @@ -157,7 +158,7 @@
2.42 ///minimum value cut can already be computed, though a maximum flow
2.43 ///is not yet obtained. So after calling this method \ref flowValue
2.44 ///and \ref minCut gives proper results.
2.45 - ///\warning: \ref minMinCut and \ref maxMinCut do not
2.46 + ///\warning \ref minMinCut and \ref maxMinCut do not
2.47 ///give minimum value cuts unless calling \ref phase2.
2.48 ///\pre The starting flow must be
2.49 /// - a constant zero flow if \c fp is \c ZERO_FLOW,
2.50 @@ -178,7 +179,7 @@
2.51 ///minimum value cut can already be computed, though a maximum flow
2.52 ///is not yet obtained. So after calling this method \ref flowValue
2.53 ///and \ref actMinCut gives proper results.
2.54 - ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
2.55 + ///\warning \ref minCut, \ref minMinCut and \ref maxMinCut do not
2.56 ///give minimum value cuts unless calling \ref phase2.
2.57 void phase1()
2.58 {