dijkstra (#16) - Dijkstra problem (execution of algorithm not complete) (#27) - Message List

Dijkstra problem (execution of algorithm not complete)

First of all this is great work and great idea. Smooth install easy data prepare ... Works on postgres :)

I got one or two questions.

1) I have load table with 600000 lines in postgres. When I exec shortest_path function it works only if A an B point are within certain air distance else query returns empty resultset ?

2) Why is A* slower then a Djikstra algorithm. It should be faster if you consider heuristic (I supposse F=G+H where G is actual cost from start node to current node and H is air distance from current node to end node) ?

3) Is it possible to load graph dinamicly with parameter let we say radius. Sample: if I travel from A to B. On start create graph within radius start node, when succesors of current best node are out of radius , build another graph within radius of that node ... So you would build many small graphs until you reach end node.

Im no expert at all in route algorithms, so I maybe ask dummy question, but I am very interested in this project because idea is great.

--pixna--

  • Message #97

    Hi,

    Thank you, we are doing our best to make pgRouting better.

    1) It sounds strange to me, 'cause there are no distance limitations in pgRouting. Probably A and B are not connected at all, so algorithm couldn't find any route between them.

    2) Well, total execution time of any shortest path function consists of two parts - data loading time and shortest path calculation time. In case of Dijkstra data loading time is shorter, 'cause it doesn't need to load vertices' coordinates. A* shortes path calculation time COULD BE shorter (in a worst case it equals to calculation time for Dijkstra) and it depends on graph density, number of edges between A and B and other things, but in needs to load coordinates for each vertex in a graph which takes more time. That's why we have both algorithms in pgRouting - Dijkstra can be better in one case and A* in another. By the way, did you try wrapper functions from routing_postgis.sql file? There you can find functions which are clipping a boundary box out of entire graph to reduce a number of edges to load.

    3) Again, wrapper functions could be an answer. They don't load data dynamicaly, but they reduce a number of edges to load, and it can improve a performance.

    Thank you once again, stay tuned :)

    • Message #98

      U re right. Distances are not the reason why I get empty resultset. It seems that A an B are not connectet. But i build topology with arcinfo and there seems to be ok. I take a look again.

      Tx for all your ansvers. There will be new questions soon. :)

      • Message #99

        You are welcome!

        • Message #103

          Hmm. Topology is ok. I try it with my own algorithm a*. Maybe i dont understand how to use it.

          1) I build topology in arcinfo.

          build roads line; build roads node;

          --data otput-- "Fnode_","Tnode_","Length" 12,7,39 12,14,28.816 14,15,36.248 15,13,25.488 15,6,147.234

          Then i import data in postgres.

          fnode_ rename to source tnode_ rename to target

          i calculate x1 x2 y1 y2

          X(StartPoint?(the_geom)) = x1 Y(StartPoint?(the_geom)) = y1 X(EndPoint?(the_geom)) = x2 Y(EndPoint?(the_geom)) = y2

          then I exec

          SELECT * FROM shortest_path ('SELECT

          unique_id AS id, source::int4 AS source, target::int4 AS target, MINUTES AS cost,

          x1, y1, x2, y2

          FROM roads',428131, 258271, false, false

          ) ;

          428131 = value from source aka fnode_ 258271 = value from target aka tnode_

          works for while and returns empty result set no messages.

          Any clue ?

          Pix

          • Message #104

            Can you send me a dump of your table to 'anton <at> orkney <dot> co <dot> jp'?

            • Message #105

              Oh f.. my mistake. When I import shape to postgres some roads doesn't import. Because im from Slovenia we have some chars like ŠČŽ and roads witch contains that chars contains utf conv err. So graph was broken. My astar works directly on shape so it finds path :(. When i fix file with iconv things start work like charm. Im testing it on my laptop. I have 532142 roads in table and djikstra found A to B on max air distance within 15 sec. Im about to try it on 2 core server with 8 gb of ram. Score will be posted.

              • Message #106

                Hooray!!! :)

                But 15 sec is a little bit slow. Did you try wrapper functions I told you about?

                • Message #108

                  Yes. SELECT AsText?(roads.the_geom),name FROM

                  shortest_path_dijkstra1_as_geometry_internal_id ( 'roads',$from, $to,300000 ) AS T1 INNER JOIN roads on roads.gid=T1.gid;

                  But it would be helpful if i knew what is the meaning of fourth param. If it's too small path is not returned.

                  Do you have any idea (suggestion) how to get directions from optimisation (turn left right go straight).

                  Im thinkin to write php class witch will contains all sql func + wraped func in style

                  result will be xml with path.

                  Pix

                  • Message #109

                    Fourth parameter means the distance between start/end point and the border of a boundary box which clips out a piece of data to load. The value depends on your projection - it can be in meters or degrees (300 km in your case, I guess, and it is way too much).

                    What about directions, it is pretty tricky. Of course, you can check coordinates of each edge in the result and tell the direction of turn, but what if you will have a crossing of four or five edges? Which one goes where? There can be one street at the right side, two streets at the left side and one street can lead straight.

                    I think you need a list of landmarks to link directions to. In that case you can tell 'turn left to St. Paul street' or 'go strait across Blue Bridge'.

                    We want to implement this feature, so we will really appreciate if you would like to contribute something to pgRouting.

                    • Message #110

                      Im writin php class for routing with pgRouting now. Im going to solwe problem this way. When I get back sorted route, I check corners betwen depart line and arrival line. Something like this:

                      -- calculates angle between three points (arrival, cross and depart) in degrees -- angle is opened from arrival point to depart point counter clockwise -- angle values around 90 indicate perpendicular right turns on path from arrival via cross to depart point -- angle values around 270 indicate perpendicular left turns on path from arrival via cross to depart point SELECT

                      MOD((360

                      + (azimuth(GeomFromText? ('POINT (3 4) ',-1), GeomFromText? ('POINT (5 7) ',-1)))/pi()*180 -- cross point, arrival point

                      • (azimuth(GeomFromText? ('POINT (3 4) ',-1), GeomFromText? ('POINT (6 3) ',-1)))/pi()*180 -- cross point, depart point )::integer,

                      360) AS angle_deg

                      What are u thinkin about ?

                      • Message #111

                        Well, it could work for simple crossings. But I still thing it is better to incorporate at least street names to make a result look like "turn left to XXX street".

    • Message #100