|
1 // -*- c++ -*- |
|
2 #ifndef HUGO_SUURBALLE_H |
|
3 #define HUGO_SUURBALLE_H |
|
4 |
|
5 #include <iostream> |
|
6 #include <dijkstra.h> |
|
7 #include <graph_wrapper.h> |
|
8 namespace hugo { |
|
9 |
|
10 |
|
11 ///\brief Implementation of Suurballe's algorithm |
|
12 /// |
|
13 /// The class \ref hugo::Suurballe "Suurballe" implements |
|
14 /// Suurballe's algorithm which seeks for k edge-disjoint paths |
|
15 /// from a given source node to a given target node in an |
|
16 /// edge-weighted directed graph having minimal total cost. |
|
17 /// |
|
18 /// |
|
19 |
|
20 |
|
21 template <typename Graph, typename T, |
|
22 typename LengthMap=typename Graph::EdgeMap<T> > |
|
23 class Suurballe { |
|
24 |
|
25 |
|
26 //Writing maps |
|
27 class ConstMap { |
|
28 public : |
|
29 typedef int ValueType; |
|
30 int operator[](typename Graph::Edge e) const { |
|
31 return 1; |
|
32 } |
|
33 }; |
|
34 /* |
|
35 // template <typename Graph, typename T> |
|
36 class ModLengthMap { |
|
37 typedef typename Graph::EdgeMap<T> EdgeMap; |
|
38 typedef typename Graph::NodeMap<T> NodeMap; |
|
39 |
|
40 const EdgeMap &ol; |
|
41 const NodeMap &pot; |
|
42 public : |
|
43 typedef typename EdgeMap::KeyType KeyType; |
|
44 typedef typename EdgeMap::ValueType ValueType; |
|
45 |
|
46 double operator[](typename Graph::EdgeIt e) const { |
|
47 return 10;//ol.get(e)-pot.get(v)-pot.get(u); |
|
48 } |
|
49 |
|
50 ModLengthMap(const EdgeMap &o, |
|
51 const NodeMap &p) : |
|
52 ol(o), pot(p){}; |
|
53 }; |
|
54 */ |
|
55 |
|
56 |
|
57 typedef typename Graph::Node Node; |
|
58 typedef typename Graph::NodeIt NodeIt; |
|
59 typedef typename Graph::Edge Edge; |
|
60 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
61 typedef ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap > ResGraphType; |
|
62 |
|
63 const Graph& G; |
|
64 const LengthMap& length; |
|
65 |
|
66 |
|
67 //auxiliary variables |
|
68 |
|
69 typename Graph::EdgeMap<int> reversed; |
|
70 typename Graph::NodeMap<T> dijkstra_dist; |
|
71 |
|
72 public : |
|
73 |
|
74 |
|
75 Suurballe(Graph& _G, LengthMap& _length) : G(_G), |
|
76 length(_length), reversed(_G), dijkstra_dist(_G){ } |
|
77 |
|
78 ///Runs Suurballe's algorithm |
|
79 ///Returns true iff there are k edge-disjoint paths from s to t |
|
80 bool run(Node s, Node t, int k) { |
|
81 |
|
82 LengthMap mod_length_c = length; |
|
83 ConstMap const1map; |
|
84 //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> |
|
85 ResGraphType res_graph(G, reversed, const1map); |
|
86 //ModLengthMap modified_length(length, dijkstra_dist); |
|
87 //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length); |
|
88 //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> |
|
89 Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c); |
|
90 |
|
91 for (int i=0; i<k; ++i){ |
|
92 dijkstra.run(s); |
|
93 if (!dijkstra.reached(t)){ |
|
94 //There is no k path from s to t |
|
95 return false; |
|
96 }; |
|
97 { |
|
98 //We have to copy the potential |
|
99 typename ResGraphType::EdgeIt e; |
|
100 for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) { |
|
101 //dijkstra_dist[e] = dijkstra.distMap()[e]; |
|
102 mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - |
|
103 dijkstra.distMap()[res_graph.head(e)] + |
|
104 dijkstra.distMap()[res_graph.tail(e)]; |
|
105 } |
|
106 } |
|
107 |
|
108 //Reversing the sortest path |
|
109 Node n=t; |
|
110 Edge e; |
|
111 while (n!=s){ |
|
112 e=dijkstra.pred(n); |
|
113 n=dijkstra.predNode(n); |
|
114 reversed[e] = 1-reversed[e]; |
|
115 } |
|
116 |
|
117 |
|
118 } |
|
119 return true; |
|
120 } |
|
121 |
|
122 |
|
123 |
|
124 |
|
125 |
|
126 };//class Suurballe |
|
127 |
|
128 |
|
129 |
|
130 |
|
131 } //namespace hugo |
|
132 |
|
133 #endif //HUGO_SUURBALLE_H |