Opened 3 years ago

Last modified 3 years ago

#1258 new enhancement/feature request

Bidirectional Dijkstra Routing

Reported by: marcus püschel Owned by: KaZeR
Priority: major Milestone: want patch / contribution
Component: core Version: 0.2.0
Severity: normal Keywords: bidirectional search


Hello everybody,

as recommended in the Navit-IRC channel, i provide a diff for the route.c that implements the bidirectional version of the Dijkstra to reduce the time needed for calculate a route request. In a next step the pthreads have to be exchanged by the Glib Threads to ensure the portability to other platforms that do not support pthreads.

Greetings, hoschi

Attachments (4)

route.c_bidirDijkstra.diff (48.5 KB) - added by marcus püschel 3 years ago.
gui_internal_command.c.diff (964 bytes) - added by marcus püschel 3 years ago.
navit_shipped.xml.diff (544 bytes) - added by marcus püschel 3 years ago.
route.c_bidirDijkstra.2.diff (48.5 KB) - added by marcus püschel 3 years ago.

Download all attachments as: .zip

Change History (10)

Changed 3 years ago by marcus püschel

comment:1 Changed 3 years ago by kazer

That's quite a lot of work here!

Unfortunately it's really hard to merge this patch as is : can you please update your code to make it configurable?

Ultimately, we should start by having it disabled until we can gather some user feedback, before enabling it by default.

Thanks a lot for your contribution!

comment:2 Changed 3 years ago by tryagain


Can you please share your results regarding actual performance benefit, memory usage analysis before and after applying the patch?

Thank you for your work.

comment:3 Changed 3 years ago by jandegr

Hi, I got it to compile and run after I glued the following in :

double now_ms()
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec*1000. + tv.tv_usec/1000.;

or did I miss out on something ?

The patch says

/**@brief varaibles used for enabling and disabling functions
 * These variables are influenced by the menue and control if the bidirectional routing
 * and also the parallel graph buildup are used or not.
int useBidirectionalRouting = 0;
int useBidirectionalMultiThread = 0;

I could test it by recompiling it with both 0's changed to 1's, but do you have some code to change it from the menu as the comment suggests ?

I did no get in to real comparison or statisticsyet, but I get the following output after compiling it for Multithread :

navit:route_graph_build:route_calc_selection() took: 0.01 ms
navit:route_graph_build:mapset_open() took: 0.00 ms
navit:route_graph_build_done:build took: 789.02 ms
navit:route_graph_flood_bidirectional2Threads: took: 1.510 ms
navit:route_graph_build_done:build took: 7323.51 ms

so I suppose it runs ok ?

The route is drawn correct, but the demovehicle runs 50 meter forth and back on the start of the route forever.


Changed 3 years ago by marcus püschel

Changed 3 years ago by marcus püschel

Changed 3 years ago by marcus püschel

comment:4 Changed 3 years ago by marcus püschel

Hello Jan, i've attached three files for you. There is an menu Extension and a new diff for the route.c-file. it compiles just fine. Navigation functions properly but i can not exclude bugs.

I wish you a happy christmas, Marcus

comment:5 Changed 3 years ago by jandegr

Hi Marcus, Thanks for the update, control from the menu works fine, and route calculation goes fine as well, but the demovehicle keeps acting funny on a 1T or 2T calculated route. I am convinced it works fine for normal driving, I just happen to do a lot of testing with the demovehicle

EDIT 20/12 : Now I had many tests go well at the start of the route, but had the demovehicle jump forth and back at the end of the route EDIT : first debugging leads to : in navigation_update (navigation.c) the updates of a traditional route result in a 'turn_around= -2' of that specific debugging line, routes 1T or 2T output other numbers for turnaround, causing the route to be reprocessed completely at each update.

Tested on Navit r5976 in Ubuntu

Happy christmas to you too Marcus, Jan

Last edited 3 years ago by jandegr (previous) (diff)

comment:6 Changed 3 years ago by jandegr

Hi Marcus If you calculate a route the classic Navit way and switch on the route graph map, it shows a serie of descending values along the path representing the remaining cost to the destination. Demovehicle drives the cheapest and follows these values to destination. In case of a bidir calculated route, it shows a serie of ascending values up to the common point and there a sequence of descending values towards destination starts. Demovehicle gets completely confused by this. I could partially solve it by assigning the correct values to the routepoints in calculate_costs_and_set_ref() but for a complete solution, on the points next to the route those values should simply be removed, otherwise demovehicle will still wander off from the route on some crossing where it still finds a seamingly cheaper way. I suppose using something like value_back instead of value in the backwards part of the bidir loop could solve this.

reagards, Jan

Last edited 3 years ago by jandegr (previous) (diff)
Note: See TracTickets for help on using tickets.