#
root/sandbox/orkney/shootingstar.h

Revision 84, 10.2 KB (checked in by anton, 3 years ago) |
---|

Line | |
---|---|

1 | /* |

2 | * Shooting* Shortest path algorithm for PostgreSQL |

3 | * |

4 | * Copyright (c) 2007 Anton A. Patrushev, Orkney, Inc. |

5 | * |

6 | * This program is free software; you can redistribute it and/or modify |

7 | * it under the terms of the GNU General Public License as published by |

8 | * the Free Software Foundation; either version 2 of the License, or |

9 | * (at your option) any later version. |

10 | * |

11 | * This program is distributed in the hope that it will be useful, |

12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |

13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |

14 | * GNU General Public License for more details. |

15 | * |

16 | * You should have received a copy of the GNU General Public License |

17 | * along with this program; if not, write to the Free Software |

18 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |

19 | * |

20 | */ |

21 | |

22 | #ifndef _SHOOTINGSTAR_H_INCLUDED |

23 | #define _SHOOTINGSTAR_H_INCLUDED |

24 | |

25 | #include "ogr_core.h" |

26 | #include "ogr_feature.h" |

27 | #include "ogr_geometry.h" |

28 | |

29 | #include <boost/config.hpp> |

30 | |

31 | #include <boost/graph/graph_traits.hpp> |

32 | #include <boost/graph/adjacency_list.hpp> |

33 | #include <boost/vector_property_map.hpp> |

34 | |

35 | #include <math.h> // for sqrt and fabs |

36 | |

37 | #include "algorithm.h" |

38 | #include "shooting_star_search.hpp" |

39 | |

40 | |

41 | #define MAX_RULE_LENGTH 5 |

42 | |

43 | #define MAX_NODES 1000000 |

44 | #define MAX_COST 100000 |

45 | |

46 | using namespace std; |

47 | using namespace boost; |

48 | |

49 | // visitor that terminates when we find the goal |

50 | template <class Edge> |

51 | class shooting_star_goal_visitor : public boost::default_shooting_star_visitor |

52 | { |

53 | public: |

54 | shooting_star_goal_visitor(Edge goal, int max_id) : m_goal(goal){} |

55 | shooting_star_goal_visitor(const shooting_star_goal_visitor &gv) : m_goal(gv.m_goal){} |

56 | ~shooting_star_goal_visitor(){} |

57 | |

58 | template <class Graph> |

59 | void examine_edge(Edge e, Graph& g) |

60 | { |

61 | if( g[e].id == g[m_goal].id) |

62 | { |

63 | throw found_goal(); |

64 | } |

65 | } |

66 | template <class Graph> |

67 | void finish_edge(Edge e, Graph& g) {} |

68 | private: |

69 | Edge m_goal; |

70 | }; |

71 | |

72 | template <class Graph, class CostType> |

73 | class edge_distance_heuristic |

74 | { |

75 | public: |

76 | typedef typename graph_traits<Graph>::edge_descriptor Edge; |

77 | edge_distance_heuristic(Graph& g, Edge goal):m_g(g), m_goal(goal){} |

78 | CostType operator()(Edge e) |

79 | { |

80 | CostType dx = m_g[source(m_goal, m_g)].x - m_g[source(e, m_g)].x; |

81 | CostType dxt = m_g[target(m_goal, m_g)].x - m_g[target(e, m_g)].x; |

82 | CostType dy = m_g[source(m_goal, m_g)].y - m_g[source(e, m_g)].y; |

83 | CostType dyt = m_g[target(m_goal, m_g)].y - m_g[target(e, m_g)].y; |

84 | //You can choose any heuristical function from below |

85 | //return ::max(dx, dy); |

86 | //return ::sqrt(dx * dx + dy * dy)/2; |

87 | //return 0; |

88 | return (min(::fabs(dx),::fabs(dxt))+min(::fabs(dy),::fabs(dyt)))/2; |

89 | } |

90 | private: |

91 | Graph& m_g; |

92 | Edge m_goal; |

93 | }; |

94 | |

95 | class ShootingStar : public Algorithm |

96 | { |

97 | public: |

98 | ShootingStar():offset(1), rule_num(0){} |

99 | ShootingStar( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn ) |

100 | : Algorithm( nameIn, directedIn, weightedIn, reverseCostIn ), offset(1), rule_num(0){} |

101 | virtual ~ShootingStar(); |

102 | |

103 | private: |

104 | std::map< int, vector< std::pair<float, vector<int> > >, std::less<int> > adjacent_edges; |

105 | std::map< int, int, std::less<int> > vertices; |

106 | vector<int> rule; |

107 | int offset; |

108 | int rule_num; |

109 | |

110 | bool addEdge(edge_descriptor *e, OGRFeature *edge, graph_t &graph) |

111 | { |

112 | bool inserted; |

113 | |

114 | if (edge->GetFieldAsDouble(COST_FIELD) < 0) // edges are inserted as unpassable if cost is negative |

115 | edge->SetField(COST_FIELD, MAX_COST); |

116 | |

117 | tie(*e, inserted) = add_edge(edge->GetFieldAsInteger(SOURCE_FIELD), |

118 | edge->GetFieldAsInteger(TARGET_FIELD), graph); |

119 | |

120 | graph[*e].cost = edge->GetFieldAsDouble(COST_FIELD); |

121 | graph[*e].id = edge->GetFieldAsInteger(ID_FIELD); |

122 | |

123 | graph[*e].source = edge->GetFieldAsInteger(SOURCE_FIELD); |

124 | graph[*e].target = edge->GetFieldAsInteger(TARGET_FIELD); |

125 | |

126 | graph[*e].adjacent_edges = adjacent_edges; |

127 | |

128 | graph[*e].rank = 0; |

129 | graph[*e].distance = 0; |

130 | |

131 | OGRLineString *geom = static_cast<OGRLineString*>(edge->GetGeometryRef()); |

132 | |

133 | vertex_descriptor s = vertex(edge->GetFieldAsInteger(SOURCE_FIELD), graph); |

134 | vertex_descriptor t = vertex(edge->GetFieldAsInteger(TARGET_FIELD), graph); |

135 | |

136 | graph[s].id = edge->GetFieldAsInteger(SOURCE_FIELD); |

137 | graph[t].id = edge->GetFieldAsInteger(TARGET_FIELD); |

138 | |

139 | graph[s].x=geom->getX(0); |

140 | graph[s].y=geom->getY(0); |

141 | graph[t].x=geom->getX(geom->getNumPoints()-1); |

142 | graph[t].y=geom->getY(geom->getNumPoints()-1); |

143 | |

144 | return inserted; |

145 | } |

146 | |

147 | virtual void fillFeatures(OGRFeature **edges, unsigned int count, edge_descriptor *e, graph_t &graph, int j) |

148 | { |

149 | int src, trg; |

150 | |

151 | //Vertex ids renumbering moved here |

152 | src = edges[j]->GetFieldAsInteger(SOURCE_FIELD); |

153 | trg = edges[j]->GetFieldAsInteger(TARGET_FIELD); |

154 | |

155 | if(vertices[src]==0) |

156 | { |

157 | vertices[src]=j+offset; |

158 | } |

159 | edges[j]->SetField(SOURCE_FIELD, vertices[src]); |

160 | |

161 | if(vertices[trg]==0) |

162 | { |

163 | offset++; |

164 | vertices[trg]=j+offset; |

165 | } |

166 | edges[j]->SetField(TARGET_FIELD, vertices[trg]); |

167 | |

168 | int *rule_cnt; |

169 | const int *rule_list; |

170 | |

171 | rule_list = edges[j]->GetFieldAsIntegerList(RULE_FIELD, rule_cnt); |

172 | |

173 | for(int z=0; z< *rule_cnt;++z) |

174 | { |

175 | if(rule_list[z] > 0) |

176 | { |

177 | rule.push_back(rule_list[z]); |

178 | } |

179 | } |

180 | |

181 | if(edges[j]->GetFieldAsDouble(TO_COST_FIELD) > 0) |

182 | { |

183 | adjacent_edges[edges[j]->GetFieldAsInteger(ID_FIELD)].push_back( |

184 | std::pair<double, vector<int> > (edges[j]->GetFieldAsDouble(TO_COST_FIELD), rule) ); |

185 | rule.clear(); |

186 | } |

187 | |

188 | if((j < count-1 && edges[j]->GetFieldAsInteger(ID_FIELD) != edges[j+1]->GetFieldAsInteger(ID_FIELD))||(j==count-1)) |

189 | { |

190 | |

191 | bool inserted = addEdge(e, edges[j], graph); |

192 | |

193 | graph[*e].cost = edges[j]->GetFieldAsDouble(COST_FIELD);//set cost |

194 | graph[*e].id = j;//set id |

195 | |

196 | |

197 | if (!IsDirected() || (IsDirected() && HasReverseCost())) |

198 | { |

199 | |

200 | if(adjacent_edges[edges[j]->GetFieldAsInteger(ID_FIELD)].size() > 0) |

201 | { |

202 | adjacent_edges[edges[j]->GetFieldAsInteger(ID_FIELD)+e_max_id].assign( |

203 | adjacent_edges[edges[j]->GetFieldAsInteger(ID_FIELD)].begin(), |

204 | adjacent_edges[edges[j]->GetFieldAsInteger(ID_FIELD)].end() ); |

205 | adjacent_edges.erase(edges[j]->GetFieldAsInteger(ID_FIELD)); |

206 | } |

207 | |

208 | edge_descriptor *er; |

209 | //adding an edge for opposite direction |

210 | bool inserted = addEdge(er, edges[j], graph); |

211 | |

212 | graph[*er].id = j;//set id |

213 | |

214 | if (HasReverseCost()) |

215 | { |

216 | graph[*er].cost = edges[j]->GetFieldAsDouble(RC_FIELD);//set reverse cost |

217 | } |

218 | else |

219 | { |

220 | graph[*er].cost = edges[j]->GetFieldAsDouble(COST_FIELD);//set cost |

221 | } |

222 | |

223 | } |

224 | |

225 | adjacent_edges.clear(); |

226 | rule_num = 0; |

227 | |

228 | } |

229 | else |

230 | { |

231 | rule_num++; |

232 | } |

233 | } |

234 | |

235 | int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) |

236 | { |

237 | edge_descriptor source_edge; |

238 | edge_descriptor target_edge; |

239 | |

240 | bool source_found = false, target_found = false; |

241 | |

242 | graph_traits<graph_t>::edge_iterator ei, ei_end; |

243 | |

244 | for(tie(ei, ei_end) = boost::edges(graph); ei != ei_end; ++ei) |

245 | { |

246 | if(graph[*ei].id == start) |

247 | { |

248 | source_edge = *ei; |

249 | source_found = true; |

250 | break; |

251 | } |

252 | } |

253 | |

254 | if (!source_found) |

255 | { |

256 | return NO_SOURCE_FOUND; |

257 | } |

258 | |

259 | |

260 | for(tie(ei, ei_end) = boost::edges(graph); ei != ei_end; ++ei) |

261 | { |

262 | if(graph[*ei].id == end) |

263 | { |

264 | target_edge = *ei; |

265 | target_found = true; |

266 | break; |

267 | } |

268 | } |

269 | |

270 | if (!target_found) |

271 | { |

272 | return NO_TARGET_FOUND; |

273 | } |

274 | |

275 | property_map<graph_t, int Edge::*>::type edge_index = get(&Edge::id, graph); |

276 | |

277 | std::map< int, edge_descriptor, std::less<int> > predecessors; |

278 | |

279 | property_map<graph_t, double Edge::*>::type rank = get(&Edge::rank, graph); |

280 | property_map<graph_t, double Edge::*>::type distance = get(&Edge::distance, graph); |

281 | |

282 | try |

283 | { |

284 | shooting_star_search |

285 | (graph, source_edge, |

286 | edge_distance_heuristic<graph_t, float>(graph, target_edge), |

287 | weight_map(get(&Edge::cost, graph)). |

288 | weight_map2(get(&Edge::adjacent_edges, graph)). |

289 | edge_color_map(get(&Edge::color, graph)). |

290 | visitor(shooting_star_goal_visitor<edge_descriptor>(target_edge, e_max_id)), |

291 | edge_index, |

292 | distance, rank, |

293 | predecessors, e_max_id |

294 | ); |

295 | } |

296 | catch(found_goal &fg) |

297 | { |

298 | return makeResult(target_edge, source_edge, edges, predecessors, result, resultCount, graph); |

299 | } |

300 | } |

301 | |

302 | int makeResult(edge_descriptor target_edge, edge_descriptor source_edge, |

303 | OGRFeature **edges, |

304 | std::map< int, edge_descriptor, std::less<int> > &predecessors, |

305 | OGRFeature **result, int *resultCount, graph_t &graph) |

306 | { |

307 | vector<edge_descriptor> path_vect; |

308 | int max = MAX_NODES; |

309 | |

310 | path_vect.push_back(target_edge); |

311 | |

312 | while (target_edge != source_edge) |

313 | { |

314 | |

315 | if ((target_edge == predecessors[graph[target_edge].id]) && (predecessors[graph[target_edge].id] != source_edge)) |

316 | { |

317 | return NO_PATH_FOUND; |

318 | } |

319 | |

320 | target_edge = predecessors[graph[target_edge].id]; |

321 | |

322 | path_vect.push_back(target_edge); |

323 | |

324 | if (!max--) |

325 | { |

326 | return RESULT_OVERFLOW; |

327 | } |

328 | } |

329 | |

330 | //*result = (OGRFeature *) malloc(sizeof(OGRFeature) * (path_vect.size() + 1)); |

331 | //Let's try to do it in C++ style |

332 | result = new OGRFeature * [path_vect.size() + 1]; |

333 | *resultCount = path_vect.size(); |

334 | |

335 | for(int i = path_vect.size() - 1, j = 0; i >= 0; i--, j++) |

336 | { |

337 | graph_traits < graph_t >::edge_descriptor e; |

338 | |

339 | e = path_vect.at(i); |

340 | |

341 | if(graph[e].id > e_max_id) |

342 | { |

343 | graph[e].id -= e_max_id; |

344 | } |

345 | |

346 | result[j] = edges[graph[e].id]; |

347 | } |

348 | |

349 | return EXIT_SUCCESS; |

350 | } |

351 | |

352 | }; |

353 | |

354 | #endif |

**Note:**See TracBrowser for help on using the browser.