[pgrouting-dev] Driving Directions Revisited
Jay Mahadeokar
jai.mahadeokar at gmail.com
Tue May 17 16:37:26 EDT 2011
On Tue, May 17, 2011 at 7:24 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> 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?
I will just guess here, since I am not exactly sure about the internals of
driving distance. But, in theory, if the graph is not connected, the
breadth-first-dijkstra-search algorithm would return multiple trees.
If the dijkstra implementation stops when no more vertices can be reached
from source, then only single tree should be returned, excluding the
vertices in other components of graph. But, if b-f-s is continued, then
multiple search trees would be output.
Is the input graph that is being constructed, connected?
Would this have something to do with the result? Or if the driving_distance
implementation search stops when no vertices are reachable, then I guess
there would be some other issue..
> 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
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110518/f6bd2d0e/attachment.html
More information about the pgrouting-dev
mailing list