Context Navigation

dijkstra (#16) - Postgresql crash on dijkstra (#109) - Message List

Postgresql crash on dijkstra

Hi,

we have been using pgrouting for the street network of a city totaling 50k edges and it seems to work fine. However, a strange thing has been occurring to another, much smaller topology of only 95 edges, that makes the postmaster process consume a lot of memory ( > 2GB) and simply never returns the result. I have to kill the postmaster each time with a SIGKILL in order to get the system back to normal.

We have noticed that the cause of this problem are certain edges, but when looking at the attributes and coordinates, it all seems fine. Including just one of the particular edges in the set used for routing will halt the complete server. This occurs with Dijkstra, but it could be that this also occurs with A*.

There are no parallel edges, no isolated edges, we're not using directed/reverse_cost and the data has been projected for use with google maps. We are really at a loss here. Are there any restrictions or problems that are not mentioned in the documentation?

UPDATE: The sql file can be found here: http://pgrouting.postlbs.org/attachment/wiki/crashdata/test.sql

The edges causing the problem have the value "stop" in the field "name"

it's the standard output of shp2pgsql

Thanks for any help in advance!

John

Tree View Flat View (newer first) Flat View (older first)

Message #403

Hi John,

Thanks for the report. I will try your data. Can you please tell me which pgRouting and PostGIS version are you using?

anton

01/29/08 09:47:38 (3 years ago)
- Message #404
  
  Hi Anton,
  
  thank you for the quick reply. We're using pgRouting 1.01 and postgis 1.3.1 (from the foss4gtk package) and postgresql 8.2.5.
  
  johno
  
  01/29/08 10:44:29 (3 years ago)
  - Message #406
    
    Hi John,
    
    I tried the data and I found out that the problem is in the vertices renumbering. This is a long story, but I can explain it in few words. Boost library creates a graph and the number of entities in that graph equals to the max vertex id. So, in A* and Shooting* C wrappers I made the vertex id renumbering function (which works strange, 'cause it crashes with A* also).
    
    What you can do (as a fast temporary solution and only if you don't cate about vertex ids) is to run topology function which will renumber all vertices. I tried it and it's working well.
    
    It will take few days to find out what's wrong with renumbering. So, please wait if you don't like the first solution.
    
    Anton.
    
    anton
    
    01/29/08 17:52:42 (3 years ago)
    - Message #407
      
      Many thanks!
      
      Glad to hear that you managed to find what is causing the problem. I really had no idea that there is a restriction on the vertex numbering and I guess I would have never figured that out by myself. It'll become a bit complicated for us to renumber the vertices, because this small topology is actually a part of a much bigger one and stuff is being added daily from external sources based on those numbers. However, I guess that temporarily we can renumber the vertices and save the original source and target into other fields so we can finally test the whole thing :)
      
      Which function are you talking about specifically? We have, geographically speaking, lines on top of others, but are separated in the graph. Rebuilding the topology would mess up the graph. Is there a way to just renumber the vertices?
      
      Talking about that, having two or more lines with the same start and end coordenates in one graph is allowed as long as they separated in the topology ,right? Both having their own edges and vertices and interconnected using an intermediary vertex.
      
      Thanks again!
      
      John
      
      johno
      
      01/29/08 18:25:59 (3 years ago)
      - Message #416
        
        Hi John,
        
        Yeah, indeed, Shooting* does the better job!
        
        Try this:
        
        alter table test add column rule text;
        
        alter table test add column to_cost double precision;
        
        and then
        
        SELECT edge_id, cost FROM shortest_path_shooting_star('SELECT gid AS id, source::int4 as source, target::int4 as target, length::double precision AS cost, x(startpoint(the_geom)) as x1, y(startpoint(the_geom)) as y1, x(endpoint(the_geom)) as x2, y(endpoint(the_geom)) as y2, to_cost, rule FROM test',1, 45, false, false);
        
        anton
        
        01/31/08 16:47:39 (3 years ago)
      - Message #408
        
        Hi John,
        
        If you really need to have several edges with the same start and end coordinates, you can merge topologies and use Shooting* algorithm which cares about parallel edges.
        
        anton
        
        01/29/08 18:35:42 (3 years ago)

Tree View Flat View (newer first) Flat View (older first)