80 ConstMap const1map; |
81 ConstMap const1map; |
81 //This MinCostFlow instance will actually solve the problem |
82 //This MinCostFlow instance will actually solve the problem |
82 SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow; |
83 SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow; |
83 |
84 |
84 //Container to store found paths |
85 //Container to store found paths |
85 std::vector< std::vector<Edge> > paths; |
86 std::vector<SimplePath<Graph> > paths; |
86 |
87 |
87 public : |
88 public : |
88 |
89 |
89 |
90 |
90 /// \brief The constructor of the class. |
91 /// \brief The constructor of the class. |
168 /// with feasibility. It is meant for testing purposes. |
169 /// with feasibility. It is meant for testing purposes. |
169 bool checkComplementarySlackness(){ |
170 bool checkComplementarySlackness(){ |
170 return min_cost_flow.checkComplementarySlackness(); |
171 return min_cost_flow.checkComplementarySlackness(); |
171 } |
172 } |
172 |
173 |
|
174 typedef SimplePath<Graph> Path; |
|
175 |
173 /// \brief Read the found paths. |
176 /// \brief Read the found paths. |
174 /// |
177 /// |
175 /// This function gives back the \c j-th path in argument p. |
178 /// This function gives back the \c j-th path in argument p. |
176 /// Assumes that \c run() has been run and nothing has changed |
179 /// Assumes that \c run() has been run and nothing has changed |
177 /// since then. |
180 /// since then. |
179 /// \warning It is assumed that \c p is constructed to be a path |
182 /// \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 |
183 /// 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 |
184 /// previous \c run, then the result here will be an empty path |
182 /// (\c j can be 0 as well). |
185 /// (\c j can be 0 as well). |
183 /// |
186 /// |
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 |
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). |
188 /// real application you would get the found paths iteratively). |
189 template<typename Path> |
189 Path path(int j) const { |
190 void getPath(Path& p, size_t j){ |
190 return paths[j]; |
191 |
191 } |
192 p.clear(); |
192 |
193 if (j>paths.size()-1){ |
193 /// \brief Gives back the number of the paths. |
194 return; |
194 /// |
195 } |
195 /// Gives back the number of the constructed paths. |
196 typename Path::Builder B(p); |
196 int pathNum() const { |
197 for(typename std::vector<Edge>::iterator i=paths[j].begin(); |
197 return paths.size(); |
198 i!=paths[j].end(); ++i ){ |
|
199 B.pushBack(*i); |
|
200 } |
|
201 |
|
202 B.commit(); |
|
203 } |
198 } |
204 |
199 |
205 }; //class Suurballe |
200 }; //class Suurballe |
206 |
201 |
207 ///@} |
202 ///@} |