Changeset 310:76c005b15354 in lemon-0.x for src/work
- Timestamp:
- 04/05/04 20:24:37 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@428
- Location:
- src/work
- Files:
-
- 1 deleted
- 5 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 edge-disjoint paths 21 /// from a given source node to a given target node in an 22 /// edge-weighted directed graph having minimal total weigth (length). 23 /// 24 /// 18 /// 19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements 20 /// an algorithm which finds k edge-disjoint paths 21 /// from a given source node to a given target node in an 22 /// edge-weighted 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 -
src/work/athos/suurballe.cc
r306 r310 120 120 121 121 int k=3; 122 MinLengthPaths<ListGraph, int> surb_test(graph, length); 123 std::cout << surb_test.run(s,t,k)<<std::endl; 122 MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> > 123 surb_test(graph, length); 124 std::cout << surb_test.run(s,t,k) << std::endl; 124 125 125 126 return 0; -
src/work/klao/Makefile
r283 r310 1 BINARIES = path_test map_test 1 BINARIES = path_test map_test minlengthpaths 2 2 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos} 3 3 include ../makefile -
src/work/klao/minlengthpaths.cc
r308 r310 120 120 121 121 int k=3; 122 MinLengthPaths<ListGraph, int> surb_test(graph, length); 123 std::cout << surb_test.run(s,t,k)<<std::endl; 122 MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> > 123 surb_test(graph, length); 124 std::cout << surb_test.run(s,t,k) << std::endl; 124 125 125 126 return 0; -
src/work/klao/minlengthpaths.h
r308 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 edge-disjoint paths 21 /// from a given source node to a given target node in an 22 /// edge-weighted directed graph having minimal total weigth (length). 23 /// 24 /// 18 /// 19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements 20 /// an algorithm which finds k edge-disjoint paths 21 /// from a given source node to a given target node in an 22 /// edge-weighted 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.