Logo Search packages:      
Sourcecode: navit version File versions

static void route_graph_flood ( struct route_graph this,
struct route_info dst,
struct vehicleprofile profile,
struct callback cb 
) [static]

Calculates the routing costs for each point.

This function is the heart of routing. It assigns each point in the route graph a cost at which one can reach the destination from this point on. Additionally it assigns each point a segment one should follow from this point on to reach the destination at the stated costs.

This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look at this algorithm.

Definition at line 1691 of file route.c.

References route_graph_point::c, route_graph_point::el, route_graph_point::end, route_graph_segment::end, route_graph_segment::end_next, route_info::percent, route_value_seg(), route_graph_point::seg, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, route_info::street, route_graph_point::value, coord::x, and coord::y.

{
      struct route_graph_point *p_min;
      struct route_graph_segment *s;
      int min,new,old,val;
      struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */

      heap = fh_makekeyheap();   

      s=route_graph_get_segment(this, dst->street);
      if (!s) {
            dbg(0,"no segment for destination found\n");
            return;
      }
      val=route_value_seg(profile, NULL, s, -1);
      if (val != INT_MAX) {
            val=val*(100-dst->percent)/100;
            s->end->seg=s;
            s->end->value=val;
            s->end->el=fh_insertkey(heap, s->end->value, s->end);
      }
      val=route_value_seg(profile, NULL, s, 1);
      if (val != INT_MAX) {
            val=val*dst->percent/100;
            s->start->seg=s;
            s->start->value=val;
            s->start->el=fh_insertkey(heap, s->start->value, s->start);
      }
      for (;;) {
            p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
            if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
                  break;
            min=p_min->value;
            if (debug_route)
                  printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y);
            p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
            s=p_min->start;
            while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
                  val=route_value_seg(profile, p_min, s, -1);
                  if (val != INT_MAX) {
                        new=min+val;
                        if (debug_route)
                              printf("begin %d len %d vs %d (0x%x,0x%x)\n",new,val,s->end->value, s->end->c.x, s->end->c.y);
                        if (new < s->end->value) { /* We've found a less costly way to reach the end of s, update it */
                              s->end->value=new;
                              s->end->seg=s;
                              if (! s->end->el) {
                                    if (debug_route)
                                          printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
                                    s->end->el=fh_insertkey(heap, new, s->end);
                                    if (debug_route)
                                          printf("el new=%p\n", s->end->el);
                              }
                              else {
                                    if (debug_route)
                                          printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
                                    fh_replacekey(heap, s->end->el, new);
                              }
                        }
                        if (debug_route)
                              printf("\n");
                  }
                  s=s->start_next;
            }
            s=p_min->end;
            while (s) { /* Doing the same as above with the segments leading towards our point */
                  val=route_value_seg(profile, p_min, s, 1);
                  if (val != INT_MAX) {
                        new=min+val;
                        if (debug_route)
                              printf("end %d len %d vs %d (0x%x,0x%x)\n",new,val,s->start->value,s->start->c.x, s->start->c.y);
                        if (new < s->start->value) {
                              old=s->start->value;
                              s->start->value=new;
                              s->start->seg=s;
                              if (! s->start->el) {
                                    if (debug_route)
                                          printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
                                    s->start->el=fh_insertkey(heap, new, s->start);
                                    if (debug_route)
                                          printf("el new=%p\n", s->start->el);
                              }
                              else {
                                    if (debug_route)
                                          printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
                                    fh_replacekey(heap, s->start->el, new);
                              }
                        }
                        if (debug_route)
                              printf("\n");
                  }
                  s=s->end_next;
            }
      }
      fh_deleteheap(heap);
      callback_call_0(cb);
      dbg(1,"return\n");
}


Generated by  Doxygen 1.6.0   Back to index