24 ///\brief An algorithm for finding k paths of minimal total length. |
24 ///\brief An algorithm for finding k paths of minimal total length. |
25 |
25 |
26 |
26 |
27 #include <lemon/maps.h> |
27 #include <lemon/maps.h> |
28 #include <vector> |
28 #include <vector> |
29 #include <lemon/min_cost_flow.h> |
29 #include <lemon/ssp_min_cost_flow.h> |
30 |
30 |
31 namespace lemon { |
31 namespace lemon { |
32 |
32 |
33 /// \addtogroup flowalgs |
33 /// \addtogroup flowalgs |
34 /// @{ |
34 /// @{ |
35 |
35 |
36 ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes |
36 ///\brief Implementation of an algorithm for finding k edge-disjoint |
37 /// of minimal total length |
37 /// paths between 2 nodes of minimal total length |
38 /// |
38 /// |
39 /// The class \ref lemon::Suurballe implements |
39 /// The class \ref lemon::Suurballe implements |
40 /// an algorithm for finding k edge-disjoint paths |
40 /// an algorithm for finding k edge-disjoint paths |
41 /// from a given source node to a given target node in an |
41 /// from a given source node to a given target node in an |
42 /// edge-weighted directed graph having minimal total weight (length). |
42 /// edge-weighted directed graph having minimal total weight (length). |
47 ///\param LengthMap The type of the length map (values should be nonnegative). |
47 ///\param LengthMap The type of the length map (values should be nonnegative). |
48 /// |
48 /// |
49 ///\note It it questionable whether it is correct to call this method after |
49 ///\note It it questionable whether it is correct to call this method after |
50 ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm |
50 ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm |
51 ///for finding minimum cost flows. In fact, this implementation just |
51 ///for finding minimum cost flows. In fact, this implementation just |
52 ///wraps the MinCostFlow algorithms. The paper of both %Suurballe and |
52 ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and |
53 ///Edmonds-Karp published in 1972, therefore it is possibly right to |
53 ///Edmonds-Karp published in 1972, therefore it is possibly right to |
54 ///state that they are |
54 ///state that they are |
55 ///independent results. Most frequently this special case is referred as |
55 ///independent results. Most frequently this special case is referred as |
56 ///%Suurballe method in the literature, especially in communication |
56 ///%Suurballe method in the literature, especially in communication |
57 ///network context. |
57 ///network context. |
77 |
77 |
78 //Auxiliary variables |
78 //Auxiliary variables |
79 //This is the capacity map for the mincostflow problem |
79 //This is the capacity map for the mincostflow problem |
80 ConstMap const1map; |
80 ConstMap const1map; |
81 //This MinCostFlow instance will actually solve the problem |
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 //Container to store found paths |
84 //Container to store found paths |
85 std::vector< std::vector<Edge> > paths; |
85 std::vector< std::vector<Edge> > paths; |
86 |
86 |
87 public : |
87 public : |
88 |
88 |
89 |
89 |
90 /*! \brief The constructor of the class. |
90 /// \brief The constructor of the class. |
91 |
91 /// |
92 \param _G The directed graph the algorithm runs on. |
92 /// \param _G The directed graph the algorithm runs on. |
93 \param _length The length (weight or cost) of the edges. |
93 /// \param _length The length (weight or cost) of the edges. |
94 \param _s Source node. |
94 /// \param _s Source node. |
95 \param _t Target node. |
95 /// \param _t Target node. |
96 */ |
|
97 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) : |
96 Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) : |
98 G(_G), s(_s), t(_t), const1map(1), |
97 G(_G), s(_s), t(_t), const1map(1), |
99 min_cost_flow(_G, _length, const1map, _s, _t) { } |
98 min_cost_flow(_G, _length, const1map, _s, _t) { } |
100 |
99 |
101 ///Runs the algorithm. |
100 /// \brief Runs the algorithm. |
102 |
101 /// |
103 ///Runs the algorithm. |
102 /// Runs the algorithm. |
104 ///Returns k if there are at least k edge-disjoint paths from s to t. |
103 /// Returns k if there are at least k edge-disjoint paths from s to t. |
105 ///Otherwise it returns the number of edge-disjoint paths found |
104 /// Otherwise it returns the number of edge-disjoint paths found |
106 ///from s to t. |
105 /// from s to t. |
107 /// |
106 /// |
108 ///\param k How many paths are we looking for? |
107 /// \param k How many paths are we looking for? |
109 /// |
108 /// |
110 int run(int k) { |
109 int run(int k) { |
111 int i = min_cost_flow.run(k); |
110 int i = min_cost_flow.run(k); |
112 |
111 |
113 //Let's find the paths |
112 //Let's find the paths |
142 } |
141 } |
143 return i; |
142 return i; |
144 } |
143 } |
145 |
144 |
146 |
145 |
147 ///Returns the total length of the paths. |
146 /// \brief Returns the total length of the paths. |
148 |
147 /// |
149 ///This function gives back the total length of the found paths. |
148 /// This function gives back the total length of the found paths. |
150 Length totalLength(){ |
149 Length totalLength(){ |
151 return min_cost_flow.totalLength(); |
150 return min_cost_flow.totalLength(); |
152 } |
151 } |
153 |
152 |
154 ///Returns the found flow. |
153 /// \brief Returns the found flow. |
155 |
154 /// |
156 ///This function returns a const reference to the EdgeMap \c flow. |
155 /// This function returns a const reference to the EdgeMap \c flow. |
157 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;} |
156 const EdgeIntMap &getFlow() const { return min_cost_flow.flow;} |
158 |
157 |
159 /// Returns the optimal dual solution |
158 /// \brief Returns the optimal dual solution |
160 |
159 /// |
161 ///This function returns a const reference to the NodeMap |
160 /// This function returns a const reference to the NodeMap \c |
162 ///\c potential (the dual solution). |
161 /// potential (the dual solution). |
163 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;} |
162 const EdgeIntMap &getPotential() const { return min_cost_flow.potential;} |
164 |
163 |
165 ///Checks whether the complementary slackness holds. |
164 /// \brief Checks whether the complementary slackness holds. |
166 |
165 /// |
167 ///This function checks, whether the given solution is optimal. |
166 /// This function checks, whether the given solution is optimal. |
168 ///Currently this function only checks optimality, |
167 /// Currently this function only checks optimality, doesn't bother |
169 ///doesn't bother with feasibility. |
168 /// with feasibility. It is meant for testing purposes. |
170 ///It is meant for testing purposes. |
|
171 bool checkComplementarySlackness(){ |
169 bool checkComplementarySlackness(){ |
172 return min_cost_flow.checkComplementarySlackness(); |
170 return min_cost_flow.checkComplementarySlackness(); |
173 } |
171 } |
174 |
172 |
175 ///Read the found paths. |
173 /// \brief Read the found paths. |
176 |
174 /// |
177 ///This function gives back the \c j-th path in argument p. |
175 /// This function gives back the \c j-th path in argument p. |
178 ///Assumes that \c run() has been run and nothing has changed since then. |
176 /// Assumes that \c run() has been run and nothing has changed |
179 /// \warning It is assumed that \c p is constructed to |
177 /// since then. |
180 ///be a path of graph \c G. |
178 /// |
181 ///If \c j is not less than the result of previous \c run, |
179 /// \warning It is assumed that \c p is constructed to be a path |
182 ///then the result here will be an empty path (\c j can be 0 as well). |
180 /// of graph \c G. If \c j is not less than the result of |
183 /// |
181 /// previous \c run, then the result here will be an empty path |
184 ///\param Path The type of the path structure to put the result to (must meet lemon path concept). |
182 /// (\c j can be 0 as well). |
185 ///\param p The path to put the result to. |
183 /// |
186 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively). |
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 template<typename Path> |
189 template<typename Path> |
188 void getPath(Path& p, size_t j){ |
190 void getPath(Path& p, size_t j){ |
189 |
191 |
190 p.clear(); |
192 p.clear(); |
191 if (j>paths.size()-1){ |
193 if (j>paths.size()-1){ |