Skip to content

Instantly share code, notes, and snippets.

@cvvergara
Last active September 7, 2016 13:49
Show Gist options
  • Save cvvergara/f46e298154ae5160153603ba5045dde0 to your computer and use it in GitHub Desktop.
Save cvvergara/f46e298154ae5160153603ba5045dde0 to your computer and use it in GitHub Desktop.
GSoC student applicant: Task improve this code
/*
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