1.1 --- a/src/work/athos/minlengthpaths.h Mon Apr 05 17:56:31 2004 +0000
1.2 +++ b/src/work/athos/minlengthpaths.h Mon Apr 05 18:24:37 2004 +0000
1.3 @@ -13,31 +13,18 @@
1.4 namespace hugo {
1.5
1.6
1.7 -///\brief Implementation of an algorithm for finding k paths between 2 nodes
1.8 + ///\brief Implementation of an algorithm for finding k paths between 2 nodes
1.9 /// of minimal total length
1.10 -///
1.11 -/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
1.12 -/// an algorithm which finds k edge-disjoint paths
1.13 -/// from a given source node to a given target node in an
1.14 -/// edge-weighted directed graph having minimal total weigth (length).
1.15 -///
1.16 -///
1.17 + ///
1.18 + /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
1.19 + /// an algorithm which finds k edge-disjoint paths
1.20 + /// from a given source node to a given target node in an
1.21 + /// edge-weighted directed graph having minimal total weigth (length).
1.22
1.23 - template <typename Graph, typename T,
1.24 - typename LengthMap=typename Graph::EdgeMap<T> >
1.25 + template <typename Graph, typename LengthMap>
1.26 class MinLengthPaths {
1.27
1.28 -
1.29 -// class ConstMap {
1.30 -// public :
1.31 -// typedef int ValueType;
1.32 -// typedef typename Graph::Edge KeyType;
1.33 -
1.34 -// int operator[](typename Graph::Edge e) const {
1.35 -// return 1;
1.36 -// }
1.37 -// };
1.38 -
1.39 + typedef typename LengthMap::ValueType Length;
1.40
1.41 typedef typename Graph::Node Node;
1.42 typedef typename Graph::NodeIt NodeIt;
1.43 @@ -47,18 +34,15 @@
1.44
1.45 typedef ConstMap<Edge,int> ConstMap;
1.46
1.47 - typedef TrivGraphWrapper<const Graph> TrivGraphType;
1.48 - typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
1.49 - ConstMap> ResGraphType;
1.50 + typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
1.51
1.52
1.53 - //template <typename Graph, typename T>
1.54 class ModLengthMap {
1.55 - typedef typename ResGraphType::NodeMap<T> NodeMap;
1.56 + typedef typename ResGraphType::NodeMap<Length> NodeMap;
1.57 const ResGraphType& G;
1.58 - const EdgeIntMap& rev;
1.59 - const LengthMap &ol;
1.60 - const NodeMap &pot;
1.61 + const EdgeIntMap& rev;
1.62 + const LengthMap &ol;
1.63 + const NodeMap &pot;
1.64 public :
1.65 typedef typename LengthMap::KeyType KeyType;
1.66 typedef typename LengthMap::ValueType ValueType;
1.67 @@ -71,8 +55,8 @@
1.68 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
1.69 }
1.70
1.71 - ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev,
1.72 - const LengthMap &o, const NodeMap &p) :
1.73 + ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
1.74 + const LengthMap &o, const NodeMap &p) :
1.75 G(_G), rev(_rev), ol(o), pot(p){};
1.76 };
1.77
1.78 @@ -86,7 +70,7 @@
1.79
1.80
1.81 public :
1.82 -
1.83 +
1.84
1.85 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
1.86 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
1.87 @@ -102,8 +86,8 @@
1.88 ResGraphType res_graph(G, reversed, const1map);
1.89
1.90 //Initialize the copy of the Dijkstra potential to zero
1.91 - typename ResGraphType::NodeMap<T> dijkstra_dist(G);
1.92 - ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
1.93 + typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
1.94 + ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
1.95
1.96 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
1.97
1.98 @@ -111,7 +95,8 @@
1.99 dijkstra.run(s);
1.100 if (!dijkstra.reached(t)){
1.101 //There is no k path from s to t
1.102 - return ++i;
1.103 + /// \TODO mit keresett itt ez a ++?
1.104 + return i;
1.105 };
1.106
1.107 {
1.108 @@ -123,19 +108,6 @@
1.109 }
1.110
1.111
1.112 - /*
1.113 - {
1.114 - //We have to copy the potential
1.115 - typename ResGraphType::EdgeIt e;
1.116 - for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
1.117 - //dijkstra_dist[e] = dijkstra.distMap()[e];
1.118 - mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
1.119 - dijkstra.distMap()[res_graph.head(e)] +
1.120 - dijkstra.distMap()[res_graph.tail(e)];
1.121 - }
1.122 - }
1.123 - */
1.124 -
1.125 //Reversing the sortest path
1.126 Node n=t;
1.127 Edge e;
1.128 @@ -149,14 +121,12 @@
1.129 }
1.130 return k;
1.131 }
1.132 -
1.133 -
1.134
1.135
1.136
1.137 - };//class MinLengthPaths
1.138
1.139
1.140 + }; //class MinLengthPaths
1.141
1.142
1.143 } //namespace hugo