5 ///\ingroup flowalgs |
5 ///\ingroup flowalgs |
6 ///\file |
6 ///\file |
7 ///\brief An algorithm for finding k paths of minimal total length. |
7 ///\brief An algorithm for finding k paths of minimal total length. |
8 |
8 |
9 |
9 |
10 //#include <hugo/dijkstra.h> |
|
11 //#include <hugo/graph_wrapper.h> |
|
12 #include <hugo/maps.h> |
10 #include <hugo/maps.h> |
13 #include <vector> |
11 #include <vector> |
14 #include <hugo/mincostflows.h> |
12 #include <hugo/mincostflows.h> |
15 |
13 |
16 namespace hugo { |
14 namespace hugo { |
17 |
15 |
18 /// \addtogroup flowalgs |
16 /// \addtogroup flowalgs |
19 /// @{ |
17 /// @{ |
20 |
18 |
21 ///\brief Implementation of an algorithm for finding k paths between 2 nodes |
19 ///\brief Implementation of an algorithm for finding k edge-disjoint paths between 2 nodes |
22 /// of minimal total length |
20 /// of minimal total length |
23 /// |
21 /// |
24 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements |
22 /// The class \ref hugo::MinLengthPaths implements |
25 /// an algorithm for finding k edge-disjoint paths |
23 /// an algorithm for finding k edge-disjoint paths |
26 /// from a given source node to a given target node in an |
24 /// from a given source node to a given target node in an |
27 /// edge-weighted directed graph having minimal total weigth (length). |
25 /// edge-weighted directed graph having minimal total weight (length). |
28 /// |
26 /// |
29 ///\warning It is assumed that the lengths are positive, since the |
27 ///\warning Length values should be nonnegative. |
30 /// general flow-decomposition is not implemented yet. |
28 /// |
|
29 ///\param Graph The directed graph type the algorithm runs on. |
|
30 ///\param LengthMap The type of the length map (values should be nonnegative). |
31 /// |
31 /// |
32 ///\author Attila Bernath |
32 ///\author Attila Bernath |
33 template <typename Graph, typename LengthMap> |
33 template <typename Graph, typename LengthMap> |
34 class MinLengthPaths{ |
34 class MinLengthPaths{ |
35 |
35 |
57 std::vector< std::vector<Edge> > paths; |
57 std::vector< std::vector<Edge> > paths; |
58 |
58 |
59 public : |
59 public : |
60 |
60 |
61 |
61 |
|
62 /// The constructor of the class. |
|
63 |
|
64 ///\param _G The directed graph the algorithm runs on. |
|
65 ///\param _length The length (weight or cost) of the edges. |
62 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
66 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), |
63 const1map(1), mincost_flow(_G, _length, const1map){} |
67 const1map(1), mincost_flow(_G, _length, const1map){} |
64 |
68 |
65 ///Runs the algorithm. |
69 ///Runs the algorithm. |
66 |
70 |
67 ///Runs the algorithm. |
71 ///Runs the algorithm. |
68 ///Returns k if there are at least k edge-disjoint paths from s to t. |
72 ///Returns k if there are at least k edge-disjoint paths from s to t. |
69 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
73 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
|
74 /// |
|
75 ///\param s The source node. |
|
76 ///\param t The target node. |
|
77 ///\param k How many paths are we looking for? |
|
78 /// |
70 int run(Node s, Node t, int k) { |
79 int run(Node s, Node t, int k) { |
71 |
80 |
72 int i = mincost_flow.run(s,t,k); |
81 int i = mincost_flow.run(s,t,k); |
73 |
82 |
74 |
|
75 |
83 |
76 //Let's find the paths |
84 //Let's find the paths |
77 //We put the paths into stl vectors (as an inner representation). |
85 //We put the paths into stl vectors (as an inner representation). |
78 //In the meantime we lose the information stored in 'reversed'. |
86 //In the meantime we lose the information stored in 'reversed'. |
79 //We suppose the lengths to be positive now. |
87 //We suppose the lengths to be positive now. |
109 } |
117 } |
110 return i; |
118 return i; |
111 } |
119 } |
112 |
120 |
113 |
121 |
114 ///Total length of the paths |
122 ///Returns the total length of the paths |
115 |
123 |
116 ///This function gives back the total length of the found paths. |
124 ///This function gives back the total length of the found paths. |
117 ///\pre \ref run() must |
125 ///\pre \ref run() must |
118 ///be called before using this function. |
126 ///be called before using this function. |
119 Length totalLength(){ |
127 Length totalLength(){ |
120 return mincost_flow.totalLength(); |
128 return mincost_flow.totalLength(); |
121 } |
129 } |
122 |
130 |
123 ///Return the found flow. |
131 ///Returns the found flow. |
124 |
132 |
125 ///This function returns a const reference to the EdgeMap \c flow. |
133 ///This function returns a const reference to the EdgeMap \c flow. |
126 ///\pre \ref run() must |
134 ///\pre \ref run() must |
127 ///be called before using this function. |
135 ///be called before using this function. |
128 const EdgeIntMap &getFlow() const { return mincost_flow.flow;} |
136 const EdgeIntMap &getFlow() const { return mincost_flow.flow;} |
129 |
137 |
130 /// Return the optimal dual solution |
138 /// Returns the optimal dual solution |
131 |
139 |
132 ///This function returns a const reference to the NodeMap |
140 ///This function returns a const reference to the NodeMap |
133 ///\c potential (the dual solution). |
141 ///\c potential (the dual solution). |
134 /// \pre \ref run() must be called before using this function. |
142 /// \pre \ref run() must be called before using this function. |
135 const EdgeIntMap &getPotential() const { return mincost_flow.potential;} |
143 const EdgeIntMap &getPotential() const { return mincost_flow.potential;} |
136 |
144 |
137 ///Checks whether the complementary slackness holds. |
145 ///Checks whether the complementary slackness holds. |
138 |
146 |
139 ///This function checks, whether the given solution is optimal |
147 ///This function checks, whether the given solution is optimal. |
140 ///Running after a \c run() should return with true |
148 ///It should return true after calling \ref run() |
141 ///Currently this function only checks optimality, |
149 ///Currently this function only checks optimality, |
142 ///doesn't bother with feasibility |
150 ///doesn't bother with feasibility |
|
151 ///It is meant for testing purposes. |
143 /// |
152 /// |
144 ///\todo Is this OK here? |
|
145 bool checkComplementarySlackness(){ |
153 bool checkComplementarySlackness(){ |
146 return mincost_flow.checkComplementarySlackness(); |
154 return mincost_flow.checkComplementarySlackness(); |
147 } |
155 } |
148 |
156 |
149 ///Read the found paths. |
157 ///Read the found paths. |
152 ///Assumes that \c run() has been run and nothing changed since then. |
160 ///Assumes that \c run() has been run and nothing changed since then. |
153 /// \warning It is assumed that \c p is constructed to |
161 /// \warning It is assumed that \c p is constructed to |
154 ///be a path of graph \c G. |
162 ///be a path of graph \c G. |
155 ///If \c j is not less than the result of previous \c run, |
163 ///If \c j is not less than the result of previous \c run, |
156 ///then the result here will be an empty path (\c j can be 0 as well). |
164 ///then the result here will be an empty path (\c j can be 0 as well). |
|
165 /// |
|
166 ///\param Path The type of the path structure to put the result to (must meet hugo path concept). |
|
167 ///\param p The path to put the result to |
|
168 ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively) |
157 template<typename Path> |
169 template<typename Path> |
158 void getPath(Path& p, size_t j){ |
170 void getPath(Path& p, size_t j){ |
159 |
171 |
160 p.clear(); |
172 p.clear(); |
161 if (j>paths.size()-1){ |
173 if (j>paths.size()-1){ |
162 return; |
174 return; |
163 } |
175 } |
164 typename Path::Builder B(p); |
176 typename Path::Builder B(p); |