AW: [pgrouting-users] PostGIS - Problem with driving_distancesegfault when calculating distance for many nodes

[Kurt Weninger]

Thanks for the advice Daniel.

Well - today I downloaded the gsoc-tdsp and apsp-johnson branches from git.
I started with the first one as it also supports reverse_costs which I need.

For better understanding my situation I will explain my topology. I am using
a road network from OSM as basis for the core routing network. Using the
tool osm2po  (http://osm2po.de/) I created my base topology consisting of ~
690.000 edges and ~ 500.000 nodes.

For my purpose I insert ~ 1000 special locations into the graph by
connecting them to the routing topology (new edges and nodes). The original
topology is only extended, not altered in any way.

I am working with PostGis 1.5 based on Postgres 8.4 under Linux (Ubuntu 32
Bit)

Now my goal is to get the shortest path matrix of all my special locations
(each to each) -> should result in a 1000 x 1000  matrix.

Following https://github.com/pgRouting/pgrouting/wiki/APSP I compiled the
library and tried 

SELECT * from all_pairs_shortest_path
	('SELECT gid as id, source::integer, target::integer, cost::double
precision, reverse_cost::double precision
	FROM rout_test WHERE source IN (SELECT source FROM rout_test WHERE
source > 690000) '::TEXT
,false,true) WHERE src_vertex_id > 690000 AND dest_vertex_id >= 690000 ORDER
BY src_vertex_id, dest_vertex_id;

I was assuming that the subquery (SELECT source FROM rout_test WHERE source
> 690000) would set a focus to the nodes I am interested in.
(Additionally I sorted out costs  to other targets and added some ordering.)

Probably my assumption is wrong as the result doesn't look correct at all.

All source = target pairs do have the expected cost 0, but all other rows
have the value 1.79769313486232e+308

So I would like to ask whether my assumption is correct:

Is the function really supposed to work with a subset of nodes ?
What does the value value 1.79769313486232e+308 mean ?

Trying to solve the complete matrix for all nodes leads to an out of memory
error.

Basically I would also like to know how many nodes would be possible and of
course what the memory requirements are.

BTW: Time is not an issue, as the matrix needs only to be computed once - so
the memory question is still an issue here.
The memory allocated using malloc in the shared library is not freed when a
query is finished. Only exiting the session (e.g. quiting psql)
does the clean up. 

Best Regards,

Kurt Weninger

________________________________

Von: pgrouting-users-bounces at lists.osgeo.org
[mailto:pgrouting-users-bounces at lists.osgeo.org] Im Auftrag von Daniel Kastl
Gesendet: Mittwoch, 31. August 2011 04:41
An: pgRouting users mailing list
Betreff: Re: [pgrouting-users] PostGIS - Problem with
driving_distancesegfault when calculating distance for many nodes


Hi Kurt, 

Thank you for reporting this issue! 


Without being able to answer your questions about the memory allocation, I
would like to point you to some new algorithms developed during the Google
Summer of Code program this year.

Jay as well as Kishore (our sutedents) have added an
"All-Pair-Shortest-Path" (APSP) function, that can calculate a distance
matrix. Doing many shortest path queries is inefficient, because for every
query it selects the network into the memory again and again. APSP should do
this only once, which should also solve the memory issue.

Currently Jay's and Kishore's code resides in different branches of the
Github repository. And you would have to take the role as a "beta-tester"
;-) 
Though if you often need to calculate a distance matrix then it might be
worth to try. Of course your feedback would be very welcome!

Here a few links if you want to take a look.

*	https://github.com/pgRouting/pgrouting/network 
	look for branch "gsoc-tdsp" and "apsp-johnson"  
*	https://github.com/pgRouting/pgrouting/wiki/APSP
	This document should be for APSP in the "gsoc-tdsp" branch. Jay, can
you confirm this? Is the document still valid? 

Best regards,
Daniel 


On Wed, Aug 31, 2011 at 4:04 AM, Weninger Kurt <kurt.weninger at utanet.at>
wrote:


	Hi !
	
	I am calculating the shortest paths for some nodes of a large
network with
	about 600.000 nodes and edges. Building network topology works fine,
also
	computing the distance for one node.
	The problem I am encountering occurs when I am trying to calculate
the
	shortest path matrix for several selected nodes (about 1000) at
once. I am
	calling the function for each node and as I also have reverse costs
are
	getting the resulting matrix.
	Problem is that I get a segfault in librouting_dd.so after ~ 170
nodes in
	Windows and ~ 300 nodes in Linux. The backtrace leads me to line 162
of
	boost_drivedist.cpp.
	When I am doing the calculation in pieces of 100 nodes and logging
out
	between calculations everything works fine.
	
	I think the problem is using malloc to reserve memory, as I observed
	increasing memory usage of process postgres.
	
	 *path = (path_element_t *) malloc( sizeof(path_element_t) *
	                                    (path_vector.size() + 1) );
	
	It seems to me the memory is never freed.
	Can this be solved using palloc ?  And how ?  Because I tried
changing
	malloc to palloc, but getting strange errors in other libraries
	afterwards.
	
	Thanks for your help,
	
	Kurt
	
	
	
	_______________________________________________
	Pgrouting-users mailing list
	Pgrouting-users at lists.osgeo.org
	http://lists.osgeo.org/mailman/listinfo/pgrouting-users
	




-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de <http://georepublic.de/>