navit-project.org

forum for navit navigation tool
It is currently 18 Aug 2017, 16:12
View unanswered posts | View active topics


All times are UTC


Forum rules


Feel free to ask anything here related to the development process - coding, creating new features, fixing bugs and custom changes of Navit.

Note: For reporting bugs, use the bug tracker.



Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Help : Approach for multiple route using multpepath dijkstra
PostPosted: 18 Nov 2015, 12:06 
Offline

Joined: 16 Nov 2015, 12:17
Posts: 9
Hallo all i have posted a question about routing engine.
Now i want to share my approach for multiple route in navit.

i am going to use Multiple-Path-Dijkstra Algorithm for producing more then one shortest route as given below.


1 function Multi-path Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity; // Mark distances from source to v as not yet computed
4 visited[v] := false; // Mark all nodes as unvisited
5 previous[v] := undefined; // Previous node in optimal path from source
6 end for
7
8 dist[source] := 0; // Distance from source to itself is zero
9 insert source into Q; // Start off with the source node
10
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] and has not been visited;
13 // Source node in first case
14 remove u from Q;
15 visited[u] := true // mark this node as visited
16
17 for each neighbor v of u:
18 alt := dist[u] + dist_between(u, v); // accumulate shortest dist from source
19 if alt < dist[v]: // find a shortest path
20 dist[v] := alt; // keep the shortest dist from src to v
21 reset the previous[v] // clear up the content of previous[v]
22 add u into previous[v] // add the previous vertex u into previous[v]
23 else if alt == dist[v]: // find another path that cost = dist[v]
24 add u into previous[v]
25 endif
26 if !visited[v]:
27 insert v into Q; // Add unvisited v into the Q to be processed
28 end if
29 end if
30 end for
31 end while
32 return dist;
33 endfunction


i compared method route_graph_flood() Dijkstra part with the algorithm.
some variable and statments i compared below

*S =NuLL ---> Source.
Heap = fh_makekeyheap(); ----> Q.
p_min -----> u.
new ------->alt.
val -------> dist_between[u,V].
s->end->value --------> dist[V].
s->-end->value = new ---------> dist[V]=alt;
s->end->seg= s; ----> previous[V]=u; .
s->end->el = fh_insertkey(heap,new,s->end) --------> insert v into Q


after this i have made some editing in the code below

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;
// editing here
s->end->seg=NULL; // reset the pervious[v]
s->end->seg=p_min; //add u into previous[v]
}
else {
if(new == s->end->value) // find another path thta = dist[v]
p_min = s->end->seg;
// edit done till here

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);
}


I am really stucked. i need your suggestions for the approach.
please guide me further.


Thanks in advance.


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 20 Nov 2015, 12:19 
Offline

Joined: 23 Jun 2013, 20:15
Posts: 65
Location: Essen, Germany
Hello, and welcome to Navit development!

It's great that you want to contribute. However, it seems you have taken on a fairly ambitious project. Routing is a complex subject, both in general an in Navit's code, and I don't think we have many developers who know it well (I don't).

Maybe someone else will be able to help with your problem, but maybe there simply is no other developer who knows the problem well enough to be able to help with the free time they have (we are all volunteers).

If no one else steps up, my advice to you would be to perhaps try a simpler problem first. Some ideas:

  • There are some routing bugs in our bug tracker ( http://trac.navit-project.org/ ), you could try investigating these.
  • Try simple modifications to the code like you describe, then get the result to compile and post it to GitHub or similar. Then you can ask specific questions about the code here, linking to GitHub, which are more likely to get a response.
  • Finally, the routing code was overhauled recently ("project HighFive"). This was integrated in commit 98406407a. Try reading the commit and understanding what was changed, and why. Maybe you even find a bug ;-).

Good luck and happy hacking!


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 25 Nov 2015, 09:37 
Offline

Joined: 16 Nov 2015, 12:17
Posts: 9
Hallo sleske,

Thanks for your reply
I will surely look in to the bugs and try to solve it as well.
But can you just tell me who wrote the code for routing engine.
I have some ideas and some techniques to implement on the routing engine but i am failing at some point, if i could contact the person who wrote it would be great for me and great for the navit route engine as well.


Best of luck..

Best Regards
Fahad Ahmed


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 25 Nov 2015, 19:09 
Offline

Joined: 10 Aug 2014, 16:04
Posts: 14
Hi,
Feel free to review the changes I made to routing :
https://github.com/jandegr/navit/tree/ext_graph_prep

But I am still working to get 1 good route, so not 2 yet as you propose :)

Don't forget to run any change in routing code through the QA :

https://github.com/navit-gps/routing-qa
https://circleci.com/gh/navit-gps/routing-qa

and the output of my changed code is there :
https://circleci.com/gh/jandegr/routing-qa


regards,
Jan


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 27 Nov 2015, 09:04 
Offline

Joined: 16 Nov 2015, 12:17
Posts: 9
Hey Jan,


Thanks for the reply
I need some more help can you check out your inbox.

Thanks again
best regards
Fahad Ahmed


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 27 Nov 2015, 15:48 
Offline

Joined: 10 Aug 2014, 16:04
Posts: 14
Hi,

You will seldom get to 2 different routes with equal cost, but 2 good but different routes is possible by calculating them slightly different as both samples below :

https://circle-artifacts.com/gh/jandegr/routing-qa/253/artifacts/0/tmp/circle-artifacts.yn50P6e/RTE_Hopkins_street.yamlmetric.png
[url]to follow[/url]

But once you have 2 routes, you will have to build a path for both and offer a choice between the two to the user , as below.
https://www.google.com/maps/dir/37.88504,-122.27571/37.88442,-122.2756/@37.8832989,-122.2781105,17z/data=!4m2!4m1!3e0

That will probably be a bigger challenge than actually calculating 2 good routes, so before spending a lot of time in calculating 2 routes, you may think about what you're going to do with them afterwards.

Forget A* in the beginning and just work with dijkstra at first, I am probably not going to use A* myself, but I could not resist to code it even if it was just for fun.


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 30 Nov 2015, 11:18 
Offline

Joined: 16 Nov 2015, 12:17
Posts: 9
Hi jan

I am also just working on Djkstra Algorithm.

Thanks for your advice :)
i am trying to edit the existing code if i got some output i will update here ;)
Or i will got some error then i will need your assitance aswell.

i have shown above the peusodo code of multipath dijkstra i am trying to implement that approach in the existing code


Best Regards
Fahad


 Profile  
 
 Post subject: Re: Help : Approach for multiple route using multpepath dijk
PostPosted: 03 Dec 2015, 11:20 
Offline

Joined: 16 Nov 2015, 12:17
Posts: 9
Hey Jan,

i think right now calculating two different route will be the good option i really dont want to go for two route with the same cost.

But still i am feeling some really hard time to figure out the solution. i tried to implement the Multipath dijkstra algorithm but its having some memory leak and alot of things are going messy.

If you could just guide me with some steps to follow for calculating for two different routes from current pos to destination. Will be good Idea.
First i really just want to plot the two route on the map and then furthur we can add some attr to ask user to select any one route to follow.

please i am really lost somewhere between route_graph_flood() , Route_path_new() and route_find_nearest_street().

i know its not that easy and i am asking alot.

but if you can just give me some good tips regarding this i think i can do it because the reason is you have very good understanding of the code specially routing engine.

Please help me :(

Thanks
Regards
Fahad


 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Silver Orange 2.0.6 for IPB Designed by Skins and Hosting
Converted for phpBB3, based on Royal Blue template by BigB © 2007 2008 AEON KINGS