Changeset 310:76c005b15354 in lemon0.x for src/work/athos/minlengthpaths.h
 Timestamp:
 04/05/04 20:24:37 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@428
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/minlengthpaths.h
r306 r310 14 14 15 15 16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes 17 17 /// of minimal total length 18 /// 19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements 20 /// an algorithm which finds k edgedisjoint paths 21 /// from a given source node to a given target node in an 22 /// edgeweighted directed graph having minimal total weigth (length). 23 /// 24 /// 18 /// 19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements 20 /// an algorithm which finds k edgedisjoint paths 21 /// from a given source node to a given target node in an 22 /// edgeweighted directed graph having minimal total weigth (length). 25 23 26 template <typename Graph, typename T, 27 typename LengthMap=typename Graph::EdgeMap<T> > 24 template <typename Graph, typename LengthMap> 28 25 class MinLengthPaths { 29 26 30 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 27 typedef typename LengthMap::ValueType Length; 41 28 42 29 typedef typename Graph::Node Node; … … 48 35 typedef ConstMap<Edge,int> ConstMap; 49 36 50 typedef TrivGraphWrapper<const Graph> TrivGraphType; 51 typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap, 52 ConstMap> ResGraphType; 37 typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType; 53 38 54 39 55 //template <typename Graph, typename T>56 40 class ModLengthMap { 57 typedef typename ResGraphType::NodeMap< T> NodeMap;41 typedef typename ResGraphType::NodeMap<Length> NodeMap; 58 42 const ResGraphType& G; 59 const EdgeIntMap& rev; 60 const LengthMap &ol; 61 const NodeMap &pot; 43 const EdgeIntMap& rev; 44 const LengthMap &ol; 45 const NodeMap &pot; 62 46 public : 63 47 typedef typename LengthMap::KeyType KeyType; … … 72 56 } 73 57 74 ModLengthMap( 75 58 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 59 const LengthMap &o, const NodeMap &p) : 76 60 G(_G), rev(_rev), ol(o), pot(p){}; 77 61 }; … … 87 71 88 72 public : 89 73 90 74 91 75 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), … … 103 87 104 88 //Initialize the copy of the Dijkstra potential to zero 105 typename ResGraphType::NodeMap< T> dijkstra_dist(G);106 ModLengthMap mod_length( 89 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph); 90 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist); 107 91 108 92 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); … … 112 96 if (!dijkstra.reached(t)){ 113 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 … … 123 108 } 124 109 125 126 /*127 {128 //We have to copy the potential129 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 111 //Reversing the sortest path … … 150 122 return k; 151 123 } 152 153 154 124 155 125 156 126 157 };//class MinLengthPaths158 127 159 128 129 }; //class MinLengthPaths 160 130 161 131
Note: See TracChangeset
for help on using the changeset viewer.