1 | /* |
---|
2 | * Shortest path algorithm for PostgreSQL |
---|
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 | #include <boost/config.hpp> |
---|
21 | #include <boost/graph/graph_traits.hpp> |
---|
22 | #include <boost/graph/adjacency_list.hpp> |
---|
23 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
---|
24 | #include <boost/ptr_container/ptr_vector.hpp> |
---|
25 | |
---|
26 | #include <iostream> |
---|
27 | #include "dijkstra.h" |
---|
28 | |
---|
29 | using namespace std; //Everything in 'std' is accessed directly. |
---|
30 | using namespace boost; //Everything in 'boost' library is accessed directly. |
---|
31 | |
---|
32 | // Maximal number of nodes in the path (to avoid infinite loops) |
---|
33 | #define MAX_NODES 1000000000 |
---|
34 | |
---|
35 | struct Vertex |
---|
36 | { |
---|
37 | int id; |
---|
38 | float8 cost; |
---|
39 | }; |
---|
40 | |
---|
41 | int |
---|
42 | boost_dijkstra(edge_t *edges, unsigned int ntuplas, int start_vertex, int end_vertex, |
---|
43 | bool directed, path_element_t **path, int *path_count, char **err_msg) |
---|
44 | { |
---|
45 | |
---|
46 | typedef adjacency_list < listS, vecS, directedS, no_property, Vertex> graph_t; |
---|
47 | typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; |
---|
48 | typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; |
---|
49 | |
---|
50 | //const unsigned int num_nodes = ntuplas*2; |
---|
51 | const unsigned int num_nodes = 1; |
---|
52 | |
---|
53 | //Creating the Graph |
---|
54 | graph_t graph(num_nodes); |
---|
55 | |
---|
56 | for (unsigned int j = 0; j < ntuplas; ++j) |
---|
57 | { |
---|
58 | edge_descriptor e; |
---|
59 | bool inserted; |
---|
60 | |
---|
61 | tie(e, inserted) = add_edge(edges[j].source, edges[j].target, graph); |
---|
62 | graph[e].id = edges[j].id; |
---|
63 | graph[e].cost = edges[j].cost; |
---|
64 | |
---|
65 | if(directed) |
---|
66 | { |
---|
67 | |
---|
68 | if(edges[j].bidirectional != 0 && edges[j].bidirectional) |
---|
69 | { |
---|
70 | tie(e, inserted) = add_edge(edges[j].target, edges[j].source, graph); |
---|
71 | graph[e].id = edges[j].id; |
---|
72 | graph[e].cost = edges[j].cost; |
---|
73 | } |
---|
74 | |
---|
75 | if (edges[j].reverse_cost != 0) |
---|
76 | { |
---|
77 | tie(e, inserted) = add_edge(edges[j].target, edges[j].source, graph); |
---|
78 | graph[e].id = edges[j].id; |
---|
79 | graph[e].cost = edges[j].reverse_cost; |
---|
80 | } |
---|
81 | } |
---|
82 | else |
---|
83 | { |
---|
84 | //adding edges in reverse position, because the graph is undirected |
---|
85 | tie(e, inserted) = add_edge(edges[j].target, edges[j].source, graph); |
---|
86 | graph[e].id = edges[j].id; |
---|
87 | graph[e].cost = edges[j].cost; |
---|
88 | } |
---|
89 | } |
---|
90 | |
---|
91 | vector<vertex_descriptor> predecessors(num_vertices(graph)); |
---|
92 | |
---|
93 | vertex_descriptor _source = vertex(start_vertex, graph); |
---|
94 | |
---|
95 | if (_source < 0 /*|| _source >= num_nodes*/) |
---|
96 | { |
---|
97 | *err_msg = (char *) "Starting vertex not found"; |
---|
98 | return -1; |
---|
99 | } |
---|
100 | |
---|
101 | vertex_descriptor _target = vertex(end_vertex, graph); |
---|
102 | |
---|
103 | if (_target < 0 /*|| _target >= num_nodes*/) |
---|
104 | { |
---|
105 | *err_msg = (char *) "Ending vertex not found"; |
---|
106 | return -1; |
---|
107 | } |
---|
108 | |
---|
109 | vector<float8> distances(num_vertices(graph)); |
---|
110 | |
---|
111 | // Calling Boost function |
---|
112 | dijkstra_shortest_paths(graph, _source, |
---|
113 | predecessor_map(&predecessors[0]).weight_map(get(&Vertex::cost, graph)).distance_map(&distances[0])); |
---|
114 | |
---|
115 | vector<int> path_vect; |
---|
116 | |
---|
117 | int max = MAX_NODES; |
---|
118 | |
---|
119 | path_vect.push_back(_target); |
---|
120 | |
---|
121 | while (_target != _source) |
---|
122 | { |
---|
123 | if (_target == predecessors[_target]) |
---|
124 | { |
---|
125 | *err_msg = (char *) "No path found"; |
---|
126 | return 0; |
---|
127 | } |
---|
128 | _target = predecessors[_target]; |
---|
129 | |
---|
130 | path_vect.push_back(_target); |
---|
131 | if (!max--) |
---|
132 | { |
---|
133 | *err_msg = (char *) "Overflow"; |
---|
134 | return -1; |
---|
135 | } |
---|
136 | } |
---|
137 | |
---|
138 | *path = (path_element_t *) malloc(sizeof(path_element_t) * (path_vect.size() + 1)); |
---|
139 | *path_count = path_vect.size(); |
---|
140 | |
---|
141 | for(int i = path_vect.size() - 1, j = 0; i >= 0; i--, j++) |
---|
142 | { |
---|
143 | graph_traits < graph_t >::vertex_descriptor v_src; |
---|
144 | graph_traits < graph_t >::vertex_descriptor v_targ; |
---|
145 | graph_traits < graph_t >::edge_descriptor e; |
---|
146 | graph_traits < graph_t >::out_edge_iterator out_i, out_end; |
---|
147 | |
---|
148 | (*path)[j].vertex_id = path_vect.at(i); |
---|
149 | |
---|
150 | (*path)[j].edge_id = -1; |
---|
151 | (*path)[j].cost = distances[_target]; |
---|
152 | |
---|
153 | if (i == 0) |
---|
154 | { |
---|
155 | continue; |
---|
156 | } |
---|
157 | |
---|
158 | v_src = path_vect.at(i); |
---|
159 | v_targ = path_vect.at(i - 1); |
---|
160 | |
---|
161 | for (tie(out_i, out_end) = out_edges(v_src, graph); out_i != out_end; ++out_i) |
---|
162 | { |
---|
163 | graph_traits < graph_t >::vertex_descriptor v, targ; |
---|
164 | e = *out_i; |
---|
165 | v = source(e, graph); |
---|
166 | targ = target(e, graph); |
---|
167 | |
---|
168 | if (targ == v_targ) |
---|
169 | { |
---|
170 | (*path)[j].edge_id = graph[*out_i].id; |
---|
171 | (*path)[j].cost = graph[*out_i].cost; |
---|
172 | break; |
---|
173 | } |
---|
174 | } |
---|
175 | } |
---|
176 | |
---|
177 | return EXIT_SUCCESS; |
---|
178 | } |
---|