29 ///\author Attila Bernath |
29 ///\author Attila Bernath |
30 template <typename Graph, typename LengthMap> |
30 template <typename Graph, typename LengthMap> |
31 class MinLengthPaths { |
31 class MinLengthPaths { |
32 |
32 |
33 typedef typename LengthMap::ValueType Length; |
33 typedef typename LengthMap::ValueType Length; |
34 |
34 |
35 typedef typename Graph::Node Node; |
35 typedef typename Graph::Node Node; |
36 typedef typename Graph::NodeIt NodeIt; |
36 typedef typename Graph::NodeIt NodeIt; |
37 typedef typename Graph::Edge Edge; |
37 typedef typename Graph::Edge Edge; |
38 typedef typename Graph::OutEdgeIt OutEdgeIt; |
38 typedef typename Graph::OutEdgeIt OutEdgeIt; |
39 typedef typename Graph::EdgeMap<int> EdgeIntMap; |
39 typedef typename Graph::template EdgeMap<int> EdgeIntMap; |
40 |
40 |
41 typedef ConstMap<Edge,int> ConstMap; |
41 typedef ConstMap<Edge,int> ConstMap; |
42 |
42 |
43 typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType; |
43 typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType; |
44 |
44 |
45 |
|
46 class ModLengthMap { |
45 class ModLengthMap { |
47 typedef typename ResGraphType::NodeMap<Length> NodeMap; |
46 typedef typename ResGraphType::template NodeMap<Length> NodeMap; |
48 const ResGraphType& G; |
47 const ResGraphType& G; |
49 const EdgeIntMap& rev; |
48 const EdgeIntMap& rev; |
50 const LengthMap &ol; |
49 const LengthMap &ol; |
51 const NodeMap &pot; |
50 const NodeMap &pot; |
52 public : |
51 public : |
53 typedef typename LengthMap::KeyType KeyType; |
52 typedef typename LengthMap::KeyType KeyType; |
54 typedef typename LengthMap::ValueType ValueType; |
53 typedef typename LengthMap::ValueType ValueType; |
55 |
54 |
56 ValueType operator[](typename ResGraphType::Edge e) const { |
55 ValueType operator[](typename ResGraphType::Edge e) const { |
57 //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ |
56 //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){ |
58 // std::cout<<"Negative length!!"<<std::endl; |
57 // std::cout<<"Negative length!!"<<std::endl; |
59 //} |
58 //} |
60 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
59 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
61 } |
60 } |
62 |
61 |
63 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
62 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
64 const LengthMap &o, const NodeMap &p) : |
63 const LengthMap &o, const NodeMap &p) : |
65 G(_G), rev(_rev), ol(o), pot(p){}; |
64 G(_G), rev(_rev), ol(o), pot(p){}; |
66 }; |
65 };//ModLengthMap |
|
66 |
|
67 |
67 |
68 |
68 |
69 |
69 const Graph& G; |
70 const Graph& G; |
70 const LengthMap& length; |
71 const LengthMap& length; |
71 |
72 |
92 ///Returns k if there are at least k edge-disjoint paths from s to t. |
98 ///Returns k if there are at least k edge-disjoint paths from s to t. |
93 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
99 ///Otherwise it returns the number of found edge-disjoint paths from s to t. |
94 int run(Node s, Node t, int k) { |
100 int run(Node s, Node t, int k) { |
95 ConstMap const1map(1); |
101 ConstMap const1map(1); |
96 |
102 |
|
103 |
97 //We need a residual graph, in which some of the edges are reversed |
104 //We need a residual graph, in which some of the edges are reversed |
98 ResGraphType res_graph(G, const1map, reversed); |
105 ResGraphType res_graph(G, const1map, reversed); |
99 |
106 |
100 //Initialize the copy of the Dijkstra potential to zero |
107 //Initialize the copy of the Dijkstra potential to zero |
101 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); |
108 typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph); |
102 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
109 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
103 |
110 |
104 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
111 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
105 |
112 |
106 int i; |
113 int i; |
150 while (!reversed[e]){ |
161 while (!reversed[e]){ |
151 G.next(e); |
162 G.next(e); |
152 } |
163 } |
153 n = G.head(e); |
164 n = G.head(e); |
154 paths[j].push_back(e); |
165 paths[j].push_back(e); |
|
166 total_length += length[e]; |
155 reversed[e] = 1-reversed[e]; |
167 reversed[e] = 1-reversed[e]; |
156 } |
168 } |
157 |
169 |
158 } |
170 } |
159 |
171 |
160 return i; |
172 return i; |
161 } |
173 } |
162 |
174 |
|
175 ///This function gives back the total length of the found paths. |
|
176 ///Assumes that \c run() has been run and nothing changed since then. |
|
177 Length totalLength(){ |
|
178 return total_length; |
|
179 } |
|
180 |
|
181 ///This function gives back the \c j-th path in argument p. |
|
182 ///Assumes that \c run() has been run and nothing changed since then. |
|
183 /// \warning It is assumed that \c p is constructed to be a path of graph \c G. |
|
184 template<typename DirPath> |
|
185 void getPath(DirPath& p, int j){ |
|
186 p.clear(); |
|
187 typename DirPath::Builder B(p); |
|
188 for(typename std::vector<Edge>::iterator i=paths[j].begin(); |
|
189 i!=paths[j].end(); ++i ){ |
|
190 B.pushBack(*j); |
|
191 } |
|
192 |
|
193 B.commit(); |
|
194 } |
163 |
195 |
164 }; //class MinLengthPaths |
196 }; //class MinLengthPaths |
165 |
197 |
166 ///@} |
198 ///@} |
167 |
199 |