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