Last active
September 7, 2016 13:49
-
-
Save cvvergara/f46e298154ae5160153603ba5045dde0 to your computer and use it in GitHub Desktop.
GSoC student applicant: Task improve this code
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
GSoC student applicant: | |
Task improve this code. | |
Things to keep in mind: | |
- parameters: what changes? what does not change) (const) | |
- what is the return value? void or Path? | |
- how is it going to be easier to use: | |
... | |
Path my_path; | |
get_path(my_graph, my_source, my_target, my_pred, my_distances, my_path); | |
... | |
auto my_path = get_path(my_graph, my_source, my_target, my_pred, my_distances); | |
- local variables: | |
- are they used? | |
- they add any "value" to the result of the function? | |
- class Path has these constructors: | |
*/ | |
template < class G > | |
void | |
Pgr_dijkstra< G >::get_path( | |
const G &graph, | |
V source, | |
V target, | |
const std::vector<V> &predecessors, | |
const std::vector<double> &distances, | |
Path &r_path) { | |
// backup of the target | |
V target_back = target; | |
uint64_t from(graph.graph[source].id); | |
uint64_t to(graph.graph[target].id); | |
// no path was found | |
if (target == predecessors[target]) { | |
r_path.clear(); | |
return; | |
} | |
// find out how large is the path | |
int64_t result_size = 1; | |
while (target != source) { | |
if (target == predecessors[target]) break; | |
result_size++; | |
target = predecessors[target]; | |
} | |
// recover the target | |
target = target_back; | |
// variables that are going to be stored | |
int64_t vertex_id; | |
int64_t edge_id; | |
double cost; | |
// working from the last to the beginning | |
// initialize the sequence | |
auto seq = result_size; | |
// the last stop is the target | |
Path path(from, to); | |
path.push_front( | |
{graph.graph[target].id, -1, | |
0, distances[target]}); | |
while (target != source) { | |
// we are done when the predecesor of the target is the target | |
if (target == predecessors[target]) break; | |
// values to be inserted in the path | |
--seq; | |
cost = distances[target] - distances[predecessors[target]]; | |
vertex_id = graph.graph[predecessors[target]].id; | |
edge_id = graph.get_edge_id(predecessors[target], target, cost); | |
path.push_front({vertex_id, edge_id, | |
cost, (distances[target] - cost)}); | |
target = predecessors[target]; | |
} | |
r_path = path; | |
return; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment