Changeset 306:4d15193e3a5d in lemon0.x for src/work/athos/minlengthpaths.h
 Timestamp:
 04/05/04 19:33:04 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@424
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/minlengthpaths.h
r299 r306 1 1 // * c++ * 2 #ifndef HUGO_ SUURBALLE_H3 #define HUGO_ SUURBALLE_H2 #ifndef HUGO_MINLENGTHPATHS_H 3 #define HUGO_MINLENGTHPATHS_H 4 4 5 5 ///\file 6 ///\brief Suurballe algorithm.6 ///\brief An algorithm for finding k paths of minimal total length. 7 7 8 8 #include <iostream> 9 9 #include <dijkstra.h> 10 10 #include <graph_wrapper.h> 11 #include <maps.h> 12 11 13 namespace hugo { 12 14 13 15 14 ///\brief Implementation of Suurballe's algorithm 16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes 17 /// of minimal total length 15 18 /// 16 /// The class \ref hugo:: Suurballe "Suurballe" implements17 /// Suurballe's algorithm which seeks fork edgedisjoint paths19 /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements 20 /// an algorithm which finds k edgedisjoint paths 18 21 /// from a given source node to a given target node in an 19 /// edgeweighted directed graph having minimal total cost.22 /// edgeweighted directed graph having minimal total weigth (length). 20 23 /// 21 24 /// … … 23 26 template <typename Graph, typename T, 24 27 typename LengthMap=typename Graph::EdgeMap<T> > 25 class Suurballe{28 class MinLengthPaths { 26 29 27 30 28 //Writing maps 29 class ConstMap { 30 public : 31 typedef int ValueType; 32 typedef typename Graph::Edge KeyType; 31 // class ConstMap { 32 // public : 33 // typedef int ValueType; 34 // typedef typename Graph::Edge KeyType; 33 35 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 */ 36 // int operator[](typename Graph::Edge e) const { 37 // return 1; 38 // } 39 // }; 59 40 60 41 … … 63 44 typedef typename Graph::Edge Edge; 64 45 typedef typename Graph::OutEdgeIt OutEdgeIt; 46 typedef typename Graph::EdgeMap<int> EdgeIntMap; 47 48 typedef ConstMap<Edge,int> ConstMap; 49 65 50 typedef TrivGraphWrapper<const Graph> TrivGraphType; 66 typedef ResGraphWrapper<TrivGraphType,int, typename Graph::EdgeMap<int>,51 typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap, 67 52 ConstMap> ResGraphType; 53 54 55 //template <typename Graph, typename T> 56 class ModLengthMap { 57 typedef typename ResGraphType::NodeMap<T> NodeMap; 58 const ResGraphType& G; 59 const EdgeIntMap& rev; 60 const LengthMap &ol; 61 const NodeMap &pot; 62 public : 63 typedef typename LengthMap::KeyType KeyType; 64 typedef typename LengthMap::ValueType ValueType; 65 66 ValueType operator[](typename ResGraphType::Edge e) const { 67 if ( (12*rev[e])*ol[e](pot[G.head(e)]pot[G.tail(e)] ) <0 ){ 68 ///\TODO This has to be removed 69 std::cout<<"Negative length!!"<<std::endl; 70 } 71 return (12*rev[e])*ol[e](pot[G.head(e)]pot[G.tail(e)]); 72 } 73 74 ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev, 75 const LengthMap &o, const NodeMap &p) : 76 G(_G), rev(_rev), ol(o), pot(p){}; 77 }; 78 68 79 69 80 const Graph& G; 70 81 const LengthMap& length; 71 82 83 //auxiliary variable 84 //The value is 1 iff the edge is reversed 85 EdgeIntMap reversed; 72 86 73 //auxiliary variables74 75 typename Graph::EdgeMap<int> reversed;76 typename Graph::NodeMap<T> dijkstra_dist;77 87 78 88 public : 79 89 80 90 81 Suurballe(Graph& _G, LengthMap& _length) : G(_G),82 length(_length), reversed(_G) , dijkstra_dist(_G){ }91 MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 92 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ } 83 93 84 ///Runs Suurballe'salgorithm94 ///Runs the algorithm 85 95 86 ///Runs Suurballe's algorithm 87 ///Returns true iff there are k edgedisjoint paths from s to t 88 bool run(Node s, Node t, int k) { 96 ///Runs the algorithm 97 ///Returns k if there are at least k edgedisjoint paths from s to t. 98 ///Otherwise it returns the number of edgedisjoint paths from s to t. 99 int run(Node s, Node t, int k) { 100 ConstMap const1map(1); 89 101 90 LengthMap mod_length_c = length; 91 ConstMap const1map; 92 //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 93 TrivGraphType ize(G); 94 ResGraphType res_graph(ize, reversed, const1map); 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); 102 ResGraphType res_graph(G, reversed, const1map); 103 104 //Initialize the copy of the Dijkstra potential to zero 105 typename ResGraphType::NodeMap<T> dijkstra_dist(G); 106 ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist); 107 108 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); 99 109 100 110 for (int i=0; i<k; ++i){ … … 102 112 if (!dijkstra.reached(t)){ 103 113 //There is no k path from s to t 104 return false;114 return ++i; 105 115 }; 116 117 { 118 //We have to copy the potential 119 typename ResGraphType::NodeIt n; 120 for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) { 121 dijkstra_dist[n] += dijkstra.distMap()[n]; 122 } 123 } 124 125 126 /* 106 127 { 107 128 //We have to copy the potential … … 114 135 } 115 136 } 116 137 */ 138 117 139 //Reversing the sortest path 118 140 Node n=t; … … 126 148 127 149 } 128 return true;150 return k; 129 151 } 130 152 … … 133 155 134 156 135 };//class Suurballe157 };//class MinLengthPaths 136 158 137 159 … … 140 162 } //namespace hugo 141 163 142 #endif //HUGO_ SUURBALLE_H164 #endif //HUGO_MINLENGTHPATHS_H
Note: See TracChangeset
for help on using the changeset viewer.