Changeset 851:209c9d53e195 in lemon0.x
 Timestamp:
 09/14/04 12:29:47 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1150
 Location:
 src/hugo
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/minlengthpaths.h
r788 r851 67 67 ///Runs the algorithm. 68 68 ///Returns k if there are at least k edgedisjoint paths from s to t. 69 ///Otherwise it returns the number of found edgedisjoint paths from s to t.69 ///Otherwise it returns the number of found edgedisjoint paths from s to t. 70 70 int run(Node s, Node t, int k) { 71 71 … … 112 112 113 113 114 ///Total length of the paths 115 114 116 ///This function gives back the total length of the found paths. 115 ///Assumes that \c run() has been run and nothing changed since then. 117 ///\pre \ref run() must 118 ///be called before using this function. 116 119 Length totalLength(){ 117 120 return mincost_flow.totalLength(); 118 121 } 119 122 120 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must 123 ///Return the found flow. 124 125 ///This function returns a const reference to the EdgeMap \c flow. 126 ///\pre \ref run() must 121 127 ///be called before using this function. 122 128 const EdgeIntMap &getFlow() const { return mincost_flow.flow;} 123 129 124 ///Returns a const reference to the NodeMap \c potential (the dual solution). 130 /// Return the optimal dual solution 131 132 ///This function returns a const reference to the NodeMap 133 ///\c potential (the dual solution). 125 134 /// \pre \ref run() must be called before using this function. 126 135 const EdgeIntMap &getPotential() const { return mincost_flow.potential;} 127 136 137 ///Checks whether the complementary slackness holds. 138 128 139 ///This function checks, whether the given solution is optimal 129 140 ///Running after a \c run() should return with true 130 ///In this "state of the art" this only checks optimality, doesn't bother with feasibility 141 ///Currently this function only checks optimality, 142 ///doesn't bother with feasibility 131 143 /// 132 144 ///\todo Is this OK here? … … 135 147 } 136 148 149 ///Read the found paths. 150 137 151 ///This function gives back the \c jth path in argument p. 138 152 ///Assumes that \c run() has been run and nothing changed since then. 139 /// \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). 140 template<typename DirPath> 141 void getPath(DirPath& p, size_t j){ 153 /// \warning It is assumed that \c p is constructed to 154 ///be a path of graph \c G. 155 ///If \c j is not less than the result of previous \c run, 156 ///then the result here will be an empty path (\c j can be 0 as well). 157 template<typename Path> 158 void getPath(Path& p, size_t j){ 142 159 143 160 p.clear(); 
src/hugo/preflow.h
r849 r851 17 17 /// @{ 18 18 19 /// Preflow algorithms class.19 ///%Preflow algorithms class. 20 20 21 21 ///This class provides an implementation of the \e preflow \e 22 22 ///algorithm producing a flow of maximum value in a directed 23 23 ///graph. The preflow algorithms are the fastest max flow algorithms 24 ///up todate. The \e source node, the \e target node, the \e24 ///up to now. The \e source node, the \e target node, the \e 25 25 ///capacity of the edges and the \e starting \e flow value of the 26 26 ///edges should be passed to the algorithm through the … … 29 29 ///setFlow. 30 30 /// 31 ///After running \ c phase1 or \c preflow, the actual flow31 ///After running \ref phase1() or \ref preflow(), the actual flow 32 32 ///value can be obtained by calling \ref flowValue(). The minimum 33 ///value cut can be written into a \c node map of \c boolsby34 ///calling \ref minCut . (\ref minMinCut and \ref maxMinCutwrites33 ///value cut can be written into a <tt>bool</tt> node map by 34 ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes 35 35 ///the inclusionwise minimum and maximum of the minimum value cuts, 36 36 ///resp.) … … 130 130 ///Runs the preflow algorithm. 131 131 132 ///Runs the preflow algorithm. 132 ///Runs the preflow algorithm. 133 /// 133 134 void run() { 134 135 phase1(flow_prop); … … 158 159 ///is not yet obtained. So after calling this method \ref flowValue 159 160 ///and \ref minCut gives proper results. 160 ///\warning :\ref minMinCut and \ref maxMinCut do not161 ///\warning \ref minMinCut and \ref maxMinCut do not 161 162 ///give minimum value cuts unless calling \ref phase2. 162 163 ///\pre The starting flow must be … … 179 180 ///is not yet obtained. So after calling this method \ref flowValue 180 181 ///and \ref actMinCut gives proper results. 181 ///\warning :\ref minCut, \ref minMinCut and \ref maxMinCut do not182 ///\warning \ref minCut, \ref minMinCut and \ref maxMinCut do not 182 183 ///give minimum value cuts unless calling \ref phase2. 183 184 void phase1()
Note: See TracChangeset
for help on using the changeset viewer.