1 /* -*- C++ -*- |
1 /* -*- C++ -*- |
2 * src/hugo/suurballe.h - Part of HUGOlib, a generic C++ optimization library |
2 * src/lemon/suurballe.h - Part of LEMON, a generic C++ optimization library |
3 * |
3 * |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
5 * (Egervary Combinatorial Optimization Research Group, EGRES). |
6 * |
6 * |
7 * Permission to use, modify and distribute this software is granted |
7 * Permission to use, modify and distribute this software is granted |
12 * express or implied, and with no claim as to its suitability for any |
12 * express or implied, and with no claim as to its suitability for any |
13 * purpose. |
13 * purpose. |
14 * |
14 * |
15 */ |
15 */ |
16 |
16 |
17 #ifndef HUGO_SUURBALLE_H |
17 #ifndef LEMON_SUURBALLE_H |
18 #define HUGO_SUURBALLE_H |
18 #define LEMON_SUURBALLE_H |
19 |
19 |
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 ///\file |
21 ///\file |
22 ///\brief An algorithm for finding k paths of minimal total length. |
22 ///\brief An algorithm for finding k paths of minimal total length. |
23 |
23 |
24 |
24 |
25 #include <hugo/maps.h> |
25 #include <lemon/maps.h> |
26 #include <vector> |
26 #include <vector> |
27 #include <hugo/min_cost_flow.h> |
27 #include <lemon/min_cost_flow.h> |
28 |
28 |
29 namespace hugo { |
29 namespace lemon { |
30 |
30 |
31 /// \addtogroup flowalgs |
31 /// \addtogroup flowalgs |
32 /// @{ |
32 /// @{ |
33 |
33 |
34 ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes |
34 ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes |
35 /// of minimal total length |
35 /// of minimal total length |
36 /// |
36 /// |
37 /// The class \ref hugo::Suurballe implements |
37 /// The class \ref lemon::Suurballe implements |
38 /// an algorithm for finding k edge-disjoint paths |
38 /// an algorithm for finding k edge-disjoint paths |
39 /// from a given source node to a given target node in an |
39 /// from a given source node to a given target node in an |
40 /// edge-weighted directed graph having minimal total weight (length). |
40 /// edge-weighted directed graph having minimal total weight (length). |
41 /// |
41 /// |
42 ///\warning Length values should be nonnegative. |
42 ///\warning Length values should be nonnegative. |
185 /// \warning It is assumed that \c p is constructed to |
185 /// \warning It is assumed that \c p is constructed to |
186 ///be a path of graph \c G. |
186 ///be a path of graph \c G. |
187 ///If \c j is not less than the result of previous \c run, |
187 ///If \c j is not less than the result of previous \c run, |
188 ///then the result here will be an empty path (\c j can be 0 as well). |
188 ///then the result here will be an empty path (\c j can be 0 as well). |
189 /// |
189 /// |
190 ///\param Path The type of the path structure to put the result to (must meet hugo path concept). |
190 ///\param Path The type of the path structure to put the result to (must meet lemon path concept). |
191 ///\param p The path to put the result to |
191 ///\param p The path to put the result to |
192 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively) |
192 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively) |
193 template<typename Path> |
193 template<typename Path> |
194 void getPath(Path& p, size_t j){ |
194 void getPath(Path& p, size_t j){ |
195 |
195 |