From 610f91d7b1d5c7c989304584bb77c5d3d01995ef Mon Sep 17 00:00:00 2001 From: mvglasow Date: Sun, 12 Aug 2018 15:24:47 +0200 Subject: Refactor:traffic:route_graph_is_path_computed as common exit criterion Signed-off-by: mvglasow --- navit/route.c | 53 ++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 40 insertions(+), 13 deletions(-) diff --git a/navit/route.c b/navit/route.c index f357d64f8..12a73a3c7 100644 --- a/navit/route.c +++ b/navit/route.c @@ -212,6 +212,7 @@ static int route_time_seg(struct vehicleprofile *profile, struct route_segment_d struct route_traffic_distortion *dist); static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb); +static int route_graph_is_path_computed(struct route_graph *this_); static void route_graph_reset(struct route_graph *this); @@ -2060,22 +2061,22 @@ static void route_graph_point_update(struct vehicleprofile *profile, struct rout } /** - * @brief Expands (i.e. calculates the costs for) the points on the heap. + * @brief Expands (i.e. calculates the costs for) the points on the route graph’s heap. * - * This calculates the cost for every point on the heap, as well as any neighbors affected by the cost change, and sets - * the next segment. + * This calculates the cost for every point on the route graph’s heap, as well as any neighbors affected by the cost + * change, and sets the next segment. * * This is part of a modified LPA* implementation. * * @param profile The vehicle profile to use for routing. This determines which ways are passable and how their costs * are calculated. - * @param heap The Fibonacci heap which stores the locally inconsistent points + * @param graph The route graph */ -static void route_graph_compute_shortest_path(struct vehicleprofile * profile, struct fibheap * heap) { +static void route_graph_compute_shortest_path(struct vehicleprofile * profile, struct route_graph * graph) { struct route_graph_point *p_min; struct route_graph_segment *s = NULL; - while ((p_min = fh_extractmin(heap))) { + while (!route_graph_is_path_computed(graph) && (p_min = fh_extractmin(graph->heap))) { p_min->el = NULL; if (p_min->value > p_min->rhs) /* cost has decreased, update point value */ @@ -2083,7 +2084,7 @@ static void route_graph_compute_shortest_path(struct vehicleprofile * profile, s else { /* cost has increased, re-evaluate */ p_min->value = INT_MAX; - route_graph_point_update(profile, p_min, heap); + route_graph_point_update(profile, p_min, graph->heap); } /* in any case, update rhs of predecessors (nodes from which we can reach p_min via a single segment) */ @@ -2091,12 +2092,12 @@ static void route_graph_compute_shortest_path(struct vehicleprofile * profile, s if ((s->start == s->end) || (s->data.item.type < route_item_first) || (s->data.item.type > route_item_last)) continue; else if (route_value_seg(profile, NULL, s, -2) != INT_MAX) - route_graph_point_update(profile, s->end, heap); + route_graph_point_update(profile, s->end, graph->heap); for (s = p_min->end; s; s = s->end_next) if ((s->start == s->end) || (s->data.item.type < route_item_first) || (s->data.item.type > route_item_last)) continue; else if (route_value_seg(profile, NULL, s, 2) != INT_MAX) - route_graph_point_update(profile, s->start, heap); + route_graph_point_update(profile, s->start, graph->heap); } } @@ -2634,6 +2635,33 @@ static void route_graph_flood(struct route_graph *this, struct route_info *dst, dbg(lvl_debug,"return"); } +/** + * @brief Whether cost (re)calculation of route graph points has reached the start point + * + * This method serves as the exit criterion for cost calculation in our LPA* implementation. When it returns true, it + * means that calculation of node cost has proceeded far enough to determine the cost of, and cheapest path from, the + * start point. + * + * The current implementation returns true only when the heap is empty, i.e. all points have been calculated. This is + * not optimal in terms of efficiency, as the cost of the start point and the cheapest path from there no longer + * change during the last few cycles. Future versions may report true before the heap is completely empty, as soon as + * the cost of the start point and the cheapest path are final. However, this needs to be considered for recalculations + * which happen when the vehicle leaves the cheapest path: right now, any point in the route graph has its final cost + * and cheapest path, thus no recalculation is needed if the vehicle leaves the cheapest path. In the future, however, + * a (partial) recalculation may be needed if the vehicle deviates from the cheapest path. + * + * @param this_ The route graph + * + * @return true if calculation is complete, false if not + */ +static int route_graph_is_path_computed(struct route_graph *this_) { + /* TODO refine exit criterion */ + if (!fh_min(this_->heap)) + return 1; + else + return 0; +} + /** * @brief Triggers partial recalculation of the route, based on the existing route graph. * @@ -2671,9 +2699,8 @@ void route_recalculate_partial(struct route *this_) { if (this_->graph->busy) return; - /* do nothing if the heap is empty */ - /* TODO add exit criterion shared with route_graph_compute_shortest_path() */ - if (!fh_min(this_->graph->heap)) + /* exit if there is no need to recalculate */ + if (route_graph_is_path_computed(this_->graph)) return; route_status.type = attr_route_status; @@ -2683,7 +2710,7 @@ void route_recalculate_partial(struct route *this_) { printf("Expanding points which have changed\n"); - route_graph_compute_shortest_path(this_->vehicleprofile, this_->graph->heap); + route_graph_compute_shortest_path(this_->vehicleprofile, this_->graph); printf("Point expansion complete, recalculating route path\n"); -- cgit v1.2.1