#
root/sandbox/orkney/algorithm.h

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

Line | |
---|---|

1 | /* |

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

3 | * |

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

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

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

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

8 | * |

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

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

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

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

13 | * |

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

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

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

17 | * |

18 | */ |

19 | |

20 | #ifndef _ALGORITHM_H_INCLUDED |

21 | #define _ALGORITHM_H_INCLUDED |

22 | |

23 | #include "ogr_core.h" |

24 | #include "ogr_feature.h" |

25 | #include "ogr_geometry.h" |

26 | |

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

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

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

30 | |

31 | |

32 | #define MAX_NODES 1000000 |

33 | |

34 | #define ID_FIELD "id" |

35 | #define COST_FIELD "cost" |

36 | #define WEIGHT_FIELD "weight" |

37 | #define RC_FIELD "reverse_cost" |

38 | |

39 | #define SOURCE_FIELD "source" |

40 | #define TARGET_FIELD "target" |

41 | |

42 | #define TO_COST_FIELD "to_cost" |

43 | #define RULE_FIELD "rule" |

44 | |

45 | #define EXIT_SUCCESS 0 |

46 | #define NO_SOURCE_FOUND 1 |

47 | #define NO_TARGET_FOUND 2 |

48 | #define NO_PATH_FOUND 3 |

49 | #define RESULT_OVERFLOW 4 |

50 | |

51 | |

52 | using namespace std; |

53 | using namespace boost; |

54 | |

55 | struct Edge |

56 | { |

57 | int id; |

58 | int source; |

59 | int target; |

60 | double cost; |

61 | double distance; |

62 | double rank; |

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

64 | default_color_type color; |

65 | }; |

66 | |

67 | struct Vertex |

68 | { |

69 | int id; |

70 | double x; |

71 | double y; |

72 | }; |

73 | |

74 | struct found_goal {}; // exception for termination |

75 | |

76 | typedef adjacency_list < listS, vecS, directedS, Vertex, Edge > graph_t; |

77 | |

78 | typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; |

79 | typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; |

80 | |

81 | class Algorithm |

82 | { |

83 | protected: |

84 | bool directed; |

85 | bool weighted; |

86 | bool reverseCost; |

87 | |

88 | char *name; |

89 | int e_max_id; |

90 | |

91 | public: |

92 | // Algorithm(); |

93 | // Algorithm(char*, bool, bool, bool); |

94 | // virtual ~Algorithm(); |

95 | |

96 | Algorithm(){} |

97 | Algorithm( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn ) |

98 | { |

99 | name = nameIn; |

100 | directed = directedIn; |

101 | weighted = weightedIn; |

102 | reverseCost = reverseCostIn; |

103 | } |

104 | virtual ~Algorithm(){} |

105 | |

106 | virtual bool addEdge(edge_descriptor *e, OGRFeature *edge, graph_t &graph) = 0; |

107 | virtual void fillFeature(OGRFeature **edges, unsigned int count, edge_descriptor *e, graph_t &graph, int j) = 0; |

108 | virtual int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) = 0; |

109 | virtual int makeResult(vertex_descriptor target, vertex_descriptor source, |

110 | OGRFeature **edges, |

111 | std::vector<vertex_descriptor> &predecessors, |

112 | OGRFeature **result, int *resultCount, graph_t &graph) = 0; |

113 | |

114 | //Template method for shortest path calculation |

115 | int shortestPath(OGRFeature **edges, unsigned int count, int start, |

116 | int end, OGREnvelope *bbox, OGRFeature **result, int *resultCount) |

117 | { |

118 | |

119 | // FIXME: compute this value |

120 | const unsigned int num_nodes = ((IsDirected() && HasReverseCost() ? 2 : 1) * count) + 100; |

121 | |

122 | graph_t graph(num_nodes); |

123 | |

124 | for (unsigned int z = 0; z < count; ++z) |

125 | { |

126 | if(edges[z]->GetFieldAsInteger(ID_FIELD) > e_max_id) |

127 | e_max_id=edges[z]->GetFieldAsInteger(ID_FIELD); |

128 | } |

129 | |

130 | for (std::size_t j = 0; j < count; ++j) |

131 | { |

132 | edge_descriptor *e; |

133 | |

134 | fillFeature(edges, count, e, graph, j); |

135 | } |

136 | |

137 | return getRoute(start, end, edges, result, resultCount, graph); |

138 | } |

139 | |

140 | void SetName( char* nameIn ) { name = nameIn; } |

141 | virtual char *GetName() { return name; } |

142 | |

143 | void SetDirected( bool directedIn ) { directed = directedIn; } |

144 | bool IsDirected() const { return directed; } |

145 | void SetWeighted( bool weightedIn ) { weighted = weightedIn; } |

146 | bool IsWeighted() const { return weighted; } |

147 | void SetReverseCost( bool reverseCostIn ) { reverseCost = reverseCostIn; } |

148 | bool HasReverseCost() const { return reverseCost; } |

149 | }; |

150 | |

151 | #endif |

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