others (#15) - Research on pgRouting (#275) - Message List
Hi everyone!
My name is Paul, a I have been working on my application for a while. I use three algorithms for finding the shortest path:
- Dijkstra
- A*
- Shooting Star
Everything is working great! But now I have some question? I am writing MASTER THESIS and I have to test all this three algorithms in some way. Test just two of them would be great. I have no clue how to do it, what parameters can I change? I am working on Windows XP with pgRouting-1.02_pg-8.3.3. This is a library saved in *.dll file so I actually have no access. Can anyone please help me ? How to test them. I my application I check how many edges was include in path, and I count the length of path. You may see this on the screen below
http://img132.imageshack.us/img132/194/applicationc.jpg
I don't know what to do. I may write a lot of theory about Dijkstra and A* algorithms, but that isn't the point.
CAN ANYONE PLEASE HELP ME !!!!
Regards, Paul
-
Message #968
CAN ANY ONE PLEASE HELP ME....
paweluz05/24/09 15:25:47 (18 months ago)-
Message #969
Hi Paul,
did you still get my last reply to this post on Monday?
It's probably the only content that got lost ;-)As I wrote in the mailing list, this server died and I just restored the TRAC site now. Still a few things to do, but I hope it basically works again.
daniel05/27/09 18:58:33 (18 months ago)-
Message #970
Hi Daniel!
I actually didn't get any response. I thought that server went down. Can you please write to me again. I would really appreciate. I thought I was left alone, but there is a hope :) I am waiting for you replay.
Regards, Paul
paweluz05/29/09 03:58:33 (18 months ago)-
Message #971
Hi Paul,
At first there was only the Dijkstra algorithm and we thought with A* we could speed up routing queries. From my experience this is not the case. All algorithms have almost the same performance if you don't count milliseconds.
The biggest factor for performance is how fast you can load your data from your database. So a performance tests depends on the density of your data, on the additional BBOX you add to clip out your area, and I believe tuning PostgreSQL settings might influence your tests as well.
There are a lot of paramaters you can alter, changing algorithms might not have that large effect. Indices are important for PostgreSQL and you also should consider the query planner, so if you run the same query a couple of times it will become faster, if you then run a completely different one, it might take longer as usual.
If you're looking for a tool to test, I'm using JMeter usually, selecting start and end point randomly within a predefined BBOX.
daniel05/29/09 09:20:36 (18 months ago)
-
-
-
-
Message #972
see the graph example in this file
http://pgrouting.postlbs.org/browser/sandbox/sigis/christian.gonzalez/trunk/README.shortest_path
and then use the comman "time" in linux, i don't know if windows has it.
time psql -d mydb -c "myquery"
example:
time psql -d pgrouting -c "SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8 FROM graph1_edges', (SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'H'),false, false)";
result: real 0m0.419s user 0m0.000s sys 0m0.001s
christian.gonzalez06/04/09 23:07:41 (18 months ago)
