11 #include <maps.h> |
11 #include <maps.h> |
12 |
12 |
13 namespace hugo { |
13 namespace hugo { |
14 |
14 |
15 |
15 |
16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes |
16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes |
17 /// of minimal total length |
17 /// of minimal total length |
18 /// |
18 /// |
19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements |
19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements |
20 /// an algorithm which finds k edge-disjoint paths |
20 /// an algorithm which finds k edge-disjoint paths |
21 /// from a given source node to a given target node in an |
21 /// from a given source node to a given target node in an |
22 /// edge-weighted directed graph having minimal total weigth (length). |
22 /// edge-weighted directed graph having minimal total weigth (length). |
23 /// |
|
24 /// |
|
25 |
23 |
26 template <typename Graph, typename T, |
24 template <typename Graph, typename LengthMap> |
27 typename LengthMap=typename Graph::EdgeMap<T> > |
|
28 class MinLengthPaths { |
25 class MinLengthPaths { |
29 |
26 |
30 |
27 typedef typename LengthMap::ValueType Length; |
31 // class ConstMap { |
|
32 // public : |
|
33 // typedef int ValueType; |
|
34 // typedef typename Graph::Edge KeyType; |
|
35 |
|
36 // int operator[](typename Graph::Edge e) const { |
|
37 // return 1; |
|
38 // } |
|
39 // }; |
|
40 |
|
41 |
28 |
42 typedef typename Graph::Node Node; |
29 typedef typename Graph::Node Node; |
43 typedef typename Graph::NodeIt NodeIt; |
30 typedef typename Graph::NodeIt NodeIt; |
44 typedef typename Graph::Edge Edge; |
31 typedef typename Graph::Edge Edge; |
45 typedef typename Graph::OutEdgeIt OutEdgeIt; |
32 typedef typename Graph::OutEdgeIt OutEdgeIt; |
46 typedef typename Graph::EdgeMap<int> EdgeIntMap; |
33 typedef typename Graph::EdgeMap<int> EdgeIntMap; |
47 |
34 |
48 typedef ConstMap<Edge,int> ConstMap; |
35 typedef ConstMap<Edge,int> ConstMap; |
49 |
36 |
50 typedef TrivGraphWrapper<const Graph> TrivGraphType; |
37 typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType; |
51 typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap, |
|
52 ConstMap> ResGraphType; |
|
53 |
38 |
54 |
39 |
55 //template <typename Graph, typename T> |
|
56 class ModLengthMap { |
40 class ModLengthMap { |
57 typedef typename ResGraphType::NodeMap<T> NodeMap; |
41 typedef typename ResGraphType::NodeMap<Length> NodeMap; |
58 const ResGraphType& G; |
42 const ResGraphType& G; |
59 const EdgeIntMap& rev; |
43 const EdgeIntMap& rev; |
60 const LengthMap &ol; |
44 const LengthMap &ol; |
61 const NodeMap &pot; |
45 const NodeMap &pot; |
62 public : |
46 public : |
63 typedef typename LengthMap::KeyType KeyType; |
47 typedef typename LengthMap::KeyType KeyType; |
64 typedef typename LengthMap::ValueType ValueType; |
48 typedef typename LengthMap::ValueType ValueType; |
65 |
49 |
66 ValueType operator[](typename ResGraphType::Edge e) const { |
50 ValueType operator[](typename ResGraphType::Edge e) const { |
69 std::cout<<"Negative length!!"<<std::endl; |
53 std::cout<<"Negative length!!"<<std::endl; |
70 } |
54 } |
71 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
55 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]); |
72 } |
56 } |
73 |
57 |
74 ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev, |
58 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, |
75 const LengthMap &o, const NodeMap &p) : |
59 const LengthMap &o, const NodeMap &p) : |
76 G(_G), rev(_rev), ol(o), pot(p){}; |
60 G(_G), rev(_rev), ol(o), pot(p){}; |
77 }; |
61 }; |
78 |
62 |
79 |
63 |
80 const Graph& G; |
64 const Graph& G; |
100 ConstMap const1map(1); |
84 ConstMap const1map(1); |
101 |
85 |
102 ResGraphType res_graph(G, reversed, const1map); |
86 ResGraphType res_graph(G, reversed, const1map); |
103 |
87 |
104 //Initialize the copy of the Dijkstra potential to zero |
88 //Initialize the copy of the Dijkstra potential to zero |
105 typename ResGraphType::NodeMap<T> dijkstra_dist(G); |
89 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); |
106 ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist); |
90 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); |
107 |
91 |
108 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
92 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); |
109 |
93 |
110 for (int i=0; i<k; ++i){ |
94 for (int i=0; i<k; ++i){ |
111 dijkstra.run(s); |
95 dijkstra.run(s); |
112 if (!dijkstra.reached(t)){ |
96 if (!dijkstra.reached(t)){ |
113 //There is no k path from s to t |
97 //There is no k path from s to t |
114 return ++i; |
98 /// \TODO mit keresett itt ez a ++? |
|
99 return i; |
115 }; |
100 }; |
116 |
101 |
117 { |
102 { |
118 //We have to copy the potential |
103 //We have to copy the potential |
119 typename ResGraphType::NodeIt n; |
104 typename ResGraphType::NodeIt n; |
120 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
105 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { |
121 dijkstra_dist[n] += dijkstra.distMap()[n]; |
106 dijkstra_dist[n] += dijkstra.distMap()[n]; |
122 } |
107 } |
123 } |
108 } |
124 |
109 |
125 |
|
126 /* |
|
127 { |
|
128 //We have to copy the potential |
|
129 typename ResGraphType::EdgeIt e; |
|
130 for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) { |
|
131 //dijkstra_dist[e] = dijkstra.distMap()[e]; |
|
132 mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - |
|
133 dijkstra.distMap()[res_graph.head(e)] + |
|
134 dijkstra.distMap()[res_graph.tail(e)]; |
|
135 } |
|
136 } |
|
137 */ |
|
138 |
110 |
139 //Reversing the sortest path |
111 //Reversing the sortest path |
140 Node n=t; |
112 Node n=t; |
141 Edge e; |
113 Edge e; |
142 while (n!=s){ |
114 while (n!=s){ |