16 namespace hugo { |
16 namespace hugo { |
17 |
17 |
18 /// \addtogroup galgs |
18 /// \addtogroup galgs |
19 /// @{ |
19 /// @{ |
20 |
20 |
21 ///\brief Implementation of an algorithm for finding k paths between 2 nodes |
21 ///\brief Implementation of an algorithm for finding a flow of value \c k |
22 /// of minimal total length |
22 ///(for small values of \c k) having minimal total cost between 2 nodes |
|
23 /// |
23 /// |
24 /// |
24 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements |
25 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements |
25 /// an algorithm for finding k edge-disjoint paths |
26 /// an algorithm for finding a flow of value \c k |
|
27 ///(for small values of \c k) having minimal total cost |
26 /// from a given source node to a given target node in an |
28 /// from a given source node to a given target node in an |
27 /// edge-weighted directed graph having minimal total weigth (length). |
29 /// edge-weighted directed graph having nonnegative integer capacities. |
|
30 /// The range of the length (weight) function is nonnegative reals but |
|
31 /// the range of capacity function is the set of nonnegative integers. |
|
32 /// It is not a polinomial time algorithm for counting the minimum cost |
|
33 /// maximal flow, since it counts the minimum cost flow for every value 0..M |
|
34 /// where \c M is the value of the maximal flow. |
28 /// |
35 /// |
29 ///\author Attila Bernath |
36 ///\author Attila Bernath |
30 template <typename Graph, typename LengthMap> |
37 template <typename Graph, typename LengthMap> |
31 class MinLengthPaths { |
38 class MinCostFlows { |
32 |
39 |
33 typedef typename LengthMap::ValueType Length; |
40 typedef typename LengthMap::ValueType Length; |
34 |
41 |
35 typedef typename Graph::Node Node; |
42 typedef typename Graph::Node Node; |
36 typedef typename Graph::NodeIt NodeIt; |
43 typedef typename Graph::NodeIt NodeIt; |