Changeset 2276:1a8a66b6c6ce in lemon0.x for lemon/suurballe.h
 Timestamp:
 10/30/06 18:22:14 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3039
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/suurballe.h
r1956 r2276 27 27 #include <lemon/maps.h> 28 28 #include <vector> 29 #include <lemon/ min_cost_flow.h>29 #include <lemon/ssp_min_cost_flow.h> 30 30 31 31 namespace lemon { … … 34 34 /// @{ 35 35 36 ///\brief Implementation of an algorithm for finding k edgedisjoint paths between 2 nodes37 /// of minimal total length36 ///\brief Implementation of an algorithm for finding k edgedisjoint 37 /// paths between 2 nodes of minimal total length 38 38 /// 39 39 /// The class \ref lemon::Suurballe implements … … 50 50 ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm 51 51 ///for finding minimum cost flows. In fact, this implementation just 52 ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and52 ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and 53 53 ///EdmondsKarp published in 1972, therefore it is possibly right to 54 54 ///state that they are … … 80 80 ConstMap const1map; 81 81 //This MinCostFlow instance will actually solve the problem 82 MinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;82 SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow; 83 83 84 84 //Container to store found paths … … 88 88 89 89 90 /*! \brief The constructor of the class. 91 92 \param _G The directed graph the algorithm runs on. 93 \param _length The length (weight or cost) of the edges. 94 \param _s Source node. 95 \param _t Target node. 96 */ 90 /// \brief The constructor of the class. 91 /// 92 /// \param _G The directed graph the algorithm runs on. 93 /// \param _length The length (weight or cost) of the edges. 94 /// \param _s Source node. 95 /// \param _t Target node. 97 96 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) : 98 97 G(_G), s(_s), t(_t), const1map(1), 99 98 min_cost_flow(_G, _length, const1map, _s, _t) { } 100 99 101 /// Runs the algorithm.102 103 /// Runs the algorithm.104 /// Returns k if there are at least k edgedisjoint paths from s to t.105 /// Otherwise it returns the number of edgedisjoint paths found106 /// from s to t.107 /// 108 /// \param k How many paths are we looking for?100 /// \brief Runs the algorithm. 101 /// 102 /// Runs the algorithm. 103 /// Returns k if there are at least k edgedisjoint paths from s to t. 104 /// Otherwise it returns the number of edgedisjoint paths found 105 /// from s to t. 106 /// 107 /// \param k How many paths are we looking for? 109 108 /// 110 109 int run(int k) { … … 145 144 146 145 147 /// Returns the total length of the paths.148 149 /// This function gives back the total length of the found paths.146 /// \brief Returns the total length of the paths. 147 /// 148 /// This function gives back the total length of the found paths. 150 149 Length totalLength(){ 151 150 return min_cost_flow.totalLength(); 152 151 } 153 152 154 /// Returns the found flow.155 156 /// This function returns a const reference to the EdgeMap \c flow.153 /// \brief Returns the found flow. 154 /// 155 /// This function returns a const reference to the EdgeMap \c flow. 157 156 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;} 158 157 159 /// Returns the optimal dual solution160 161 /// This function returns a const reference to the NodeMap162 /// \cpotential (the dual solution).158 /// \brief Returns the optimal dual solution 159 /// 160 /// This function returns a const reference to the NodeMap \c 161 /// potential (the dual solution). 163 162 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;} 164 163 165 ///Checks whether the complementary slackness holds. 166 167 ///This function checks, whether the given solution is optimal. 168 ///Currently this function only checks optimality, 169 ///doesn't bother with feasibility. 170 ///It is meant for testing purposes. 164 /// \brief Checks whether the complementary slackness holds. 165 /// 166 /// This function checks, whether the given solution is optimal. 167 /// Currently this function only checks optimality, doesn't bother 168 /// with feasibility. It is meant for testing purposes. 171 169 bool checkComplementarySlackness(){ 172 170 return min_cost_flow.checkComplementarySlackness(); 173 171 } 174 172 175 ///Read the found paths. 176 177 ///This function gives back the \c jth path in argument p. 178 ///Assumes that \c run() has been run and nothing has changed since then. 179 /// \warning It is assumed that \c p is constructed to 180 ///be a path of graph \c G. 181 ///If \c j is not less than the result of previous \c run, 182 ///then the result here will be an empty path (\c j can be 0 as well). 183 /// 184 ///\param Path The type of the path structure to put the result to (must meet lemon path concept). 185 ///\param p The path to put the result to. 186 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively). 173 /// \brief Read the found paths. 174 /// 175 /// This function gives back the \c jth path in argument p. 176 /// Assumes that \c run() has been run and nothing has changed 177 /// since then. 178 /// 179 /// \warning It is assumed that \c p is constructed to be a path 180 /// of graph \c G. If \c j is not less than the result of 181 /// previous \c run, then the result here will be an empty path 182 /// (\c j can be 0 as well). 183 /// 184 /// \param Path The type of the path structure to put the result 185 /// to (must meet lemon path concept). 186 /// \param p The path to put the result to. 187 /// \param j Which path you want to get from the found paths (in a 188 /// real application you would get the found paths iteratively). 187 189 template<typename Path> 188 190 void getPath(Path& p, size_t j){
Note: See TracChangeset
for help on using the changeset viewer.