Changeset 322:a42dacfd0e3e in lemon0.x for src/work/athos/minlengthpaths.h
 Timestamp:
 04/14/04 15:30:05 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@440
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/athos/minlengthpaths.h
r314 r322 10 10 #include <graph_wrapper.h> 11 11 #include <maps.h> 12 #include <vector> 13 12 14 13 15 namespace hugo { 16 14 17 15 18 … … 49 52 50 53 ValueType operator[](typename ResGraphType::Edge e) const { 51 if ( (12*rev[e])*ol[e](pot[G.head(e)]pot[G.tail(e)] ) <0 ){ 52 ///\TODO This has to be removed 53 std::cout<<"Negative length!!"<<std::endl; 54 } 54 //if ( (12*rev[e])*ol[e](pot[G.head(e)]pot[G.tail(e)] ) <0 ){ 55 // std::cout<<"Negative length!!"<<std::endl; 56 //} 55 57 return (12*rev[e])*ol[e](pot[G.head(e)]pot[G.tail(e)]); 56 58 } … … 65 67 const LengthMap& length; 66 68 67 //auxiliry variable 69 //auxiliry variables 70 68 71 //The value is 1 iff the edge is reversed. 69 72 //If the algorithm has finished, the edges of the seeked paths are … … 71 74 EdgeIntMap reversed; 72 75 76 //Container to store found paths 77 std::vector< std::vector<Edge> > paths; 78 73 79 public : 74 80 … … 77 83 length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ } 78 84 79 ///Runs the algorithm80 85 81 86 ///Runs the algorithm … … 93 98 94 99 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length); 95 96 for (int i=0; i<k; ++i){ 100 101 int i; 102 for (i=0; i<k; ++i){ 97 103 dijkstra.run(s); 98 104 if (!dijkstra.reached(t)){ 99 105 //There are no k paths from s to t 100 return i;106 break; 101 107 }; 102 108 … … 121 127 122 128 } 123 return k; 124 } 129 130 //Let's find the paths 131 //We put the paths into vectors (just for now). In the meantime we lose 132 //the information stored in 'reversed' 133 //We suppose the lengths to be positive now. 134 paths.clear(); 135 paths.resize(k); 136 for (int j=0; j<i; ++j){ 137 Node n=s; 138 OutEdgeIt e; 139 140 while (n!=t){ 125 141 126 142 143 G.first(e,n); 144 145 while (!reversed[e]){ 146 G.next(e); 147 } 148 n = G.head(e); 149 paths[j].push_back(e); 150 reversed[e] = 1reversed[e]; 151 } 152 153 } 127 154 155 return i; 156 } 128 157 129 158
Note: See TracChangeset
for help on using the changeset viewer.