[pgrouting-dev] Driving Directions Revisited

Thu May 19 14:53:48 EDT 2011

Hi Anton, Daniel

I have taken an additional look at this and it appears to be two strange 
things happening in the results.

1. there are definitely edges missing from the out. The missing edges 
would in fact connect the disconnected trees and obviously dijkstra 
traversed those edges because it is the only way to get to the 
disconnected trees.

2. I have noticed at least one case where I had two parallel edges and 
one had a significantly larger cost, and it shows in the results but not 
the short edge. For example:

s-----A------o-------B-------m--------C------o
              |               |
              |               |
              \-------D------/

edge D parallels B, but is 4x as long as B. In the output A, D, and C 
are exist but not B, the driving distance starts at s and the cost at m 
is A + D, not A + B and C is missing.

I'm not sure what if anything more I can do at this point. There is 
nothing special about my data that I can think of. I have been running 
my tests and analysis in pgAdmin3 to get lists of input edges and output 
nodes and then generating trees of it by hand. I/m also plotting the 
segments and gids using mapserver from the table in postgis. The are no 
costs <= 0 so it should be well behaved.

Thoughts?

   -Steve

On 5/17/2011 9:54 AM, Stephen Woodbridge wrote:
> Hi Anton,
>
> I need some help with this. I think I have run into a bug. What I am
> trying to do is reconstruct the Dijkstra tree from the driving
> directions node list.
>
> So I run this query (my driving_distance() is listed below:
>
> SELECT vertex_id, case when b.source=vertex_id then b.target else
> b.source end as tid, edge_id, cost
> FROM driving_distance(
> 'SELECT gid AS id, source, target, cost_len::double precision AS cost
> FROM streets
> WHERE expand(setsrid(makepoint(-71.38776, 42.62),4326),
> 800./111120.+0.05) && the_geom', 14350697, 800, false, false) as a,
> streets b
> WHERE a.edge_id=b.gid
> order by cost;
>
> And get back this list of nodes:
>
> vertex_id;tid;edge_id;cost
> 14350697;14324143;17585631;0
> 14324152;14350697;17559046;65.7600693996609
> 14324153;14324155;17525943;151.931780105486
> 14324154;14333339;17535960;170.771041457689
> 14324142;14350697;17559045;270.404042264354
> 14324145;14324142;17525935;312.38892285178
> 14352132;14357502;17568711;327.943430630889
> 14324150;14357469;17568653;372.73455007583
> 14324146;14324145;17525934;385.363174877394
> 14324140;14324145;17525933;388.831846843193
> 14357469;14324150;17568653;409.460621733005
> 14324205;14352132;17561074;438.800178615358
> 14324143;14350697;17585631;440.463055899486
> 14324149;14324151;17525953;463.817008548616
> 14324155;14335807;17539031;505.011855607214
> 14324141;14350696;17559044;522.697129188522
> 14324144;14324140;17525932;529.29745870764
> 14333339;14324154;17535960;538.752343241644
> 14335807;14335809;17539033;545.433040614225
> 14350695;14333339;17559042;549.17256774511
> 14324164;14324155;17525998;608.754587443993
> 14324151;14324149;17525953;611.133336570719
> 14335809;14335807;17539033;617.050097622648
> 14350696;14324141;17559044;624.884390435334
> 14350693;14350696;17559043;630.386775977662
> 14350692;14350693;17559040;635.388795958097
> 14335808;14350705;17559060;676.985348880917
> 14324206;14324205;17525992;690.86142794178
> 14324207;14354647;17564505;698.702994306955
> 14350705;14357566;17568800;725.054574549748
> 14357566;14361210;17574058;744.377671982209
> 14324156;14324164;17525954;775.199428174955
> 14361210;14362309;17575712;785.251952246793
> 14324165;14324164;17525955;788.303395916384
>
> This looks reason about until I try to reconstruct the tree and find
> that I actually have multiple disconnected trees :(
>
> Leaving off the 143 prefix to all the nodes above, I get the following 9
> trees. Any ideas why I am not getting a single connected tree? Am I not
> interpreting the results correctly? Would it be possible to patch the C
> code to just return all the nodes in the tree?
>
> Other thoughts? I really need to be able to get to this data.
>
> Thanks,
> -Steve
>
> In these trees, in-dent means child of the the previous out-dent.
>
> 50697
> +24143
> +24152
> +24142
> +24145
> +24146
> +24140
> +24144
>
> 24153
> +24155
> +35807
> +35809
> +24164
> +24156
> +24165
>
> 24154
> +33339
> +50695
>
> 52132
> +57502
> +24205
> +24206
>
> 24150
> +57469
>
> 24149
> +24151
>
> 24207
> +54647
>
> 24141
> +50696
> +50693
> +50692
>
> 35808
> +50705
> +57566
> +61210
> +62309
>
>
> -- this function sets up a call the the pg_routing driving_distance()
> -- function and returns the rows without creating polygons
>
> CREATE OR REPLACE FUNCTION driving_distance(table_name character
> varying, x double precision, y double precision, maxcost double
> precision, bufdist double precision, "cost" character varying,
> reverse_cost character varying, directed boolean, has_reverse_cost boolean)
> RETURNS SETOF path_result AS
> $BODY$
> DECLARE
> q text;
> srid integer;
> r record;
> source_id integer;
>
> BEGIN
>
> FOR r IN EXECUTE 'SELECT srid FROM geometry_columns WHERE f_table_name =
> '''||table_name||'''' LOOP
> END LOOP;
>
> srid := r.srid;
>
> RAISE NOTICE 'SRID: %', srid;
> RAISE NOTICE 'SELECT id FROM
> find_node_by_nearest_link_within_distance(''POINT(% %)'', %, ''%'');',
> x, y, bufdist, table_name;
>
> SELECT id INTO source_id
> FROM find_node_by_nearest_link_within_distance('POINT('||x||' '||y||')',
> bufdist, table_name);
>
> RAISE NOTICE 'SOURCE_ID: %', source_id;
>
> q := 'SELECT gid AS id, source::integer, target::integer, '||cost||' AS
> cost'
> || CASE WHEN has_reverse_cost THEN ', '||reverse_cost||' AS reverse_cost
> ' ELSE '' END
> ||' FROM '||table_name||' WHERE setsrid(''BOX3D('||x-bufdist||'
> '||y-bufdist||','
> ||x+bufdist||' '||y+bufdist||')''::BOX3D, '||srid||') && the_geom';
>
> RAISE NOTICE 'Query: %', q;
>
> FOR r IN SELECT * FROM driving_distance(q, source_id, maxcost, directed,
> has_reverse_cost)
> LOOP
> RETURN NEXT r;
> END LOOP;
>
> RETURN;
>
> END;
> $BODY$
> LANGUAGE plpgsql VOLATILE STRICT
> COST 100
> ROWS 1000;
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev