<br><br><div class="gmail_quote">On Tue, May 17, 2011 at 7:24 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi Anton,<br>
<br>
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.<br>
<br>
So I run this query (my driving_distance() is listed below:<br>
<br>
SELECT vertex_id, case when b.source=vertex_id then b.target else b.source end as tid, edge_id, cost<br>
FROM driving_distance(<br>
'SELECT gid AS id, source, target, cost_len::double precision AS cost<br>
FROM streets<br>
WHERE expand(setsrid(makepoint(-71.38776, 42.62),4326), 800./111120.+0.05) && the_geom', 14350697, 800, false, false) as a,<br>
streets b<br>
WHERE a.edge_id=b.gid<br>
order by cost;<br>
<br>
And get back this list of nodes:<br>
<br>
vertex_id;tid;edge_id;cost<br>
14350697;14324143;17585631;0<br>
14324152;14350697;17559046;65.7600693996609<br>
14324153;14324155;17525943;151.931780105486<br>
14324154;14333339;17535960;170.771041457689<br>
14324142;14350697;17559045;270.404042264354<br>
14324145;14324142;17525935;312.38892285178<br>
14352132;14357502;17568711;327.943430630889<br>
14324150;14357469;17568653;372.73455007583<br>
14324146;14324145;17525934;385.363174877394<br>
14324140;14324145;17525933;388.831846843193<br>
14357469;14324150;17568653;409.460621733005<br>
14324205;14352132;17561074;438.800178615358<br>
14324143;14350697;17585631;440.463055899486<br>
14324149;14324151;17525953;463.817008548616<br>
14324155;14335807;17539031;505.011855607214<br>
14324141;14350696;17559044;522.697129188522<br>
14324144;14324140;17525932;529.29745870764<br>
14333339;14324154;17535960;538.752343241644<br>
14335807;14335809;17539033;545.433040614225<br>
14350695;14333339;17559042;549.17256774511<br>
14324164;14324155;17525998;608.754587443993<br>
14324151;14324149;17525953;611.133336570719<br>
14335809;14335807;17539033;617.050097622648<br>
14350696;14324141;17559044;624.884390435334<br>
14350693;14350696;17559043;630.386775977662<br>
14350692;14350693;17559040;635.388795958097<br>
14335808;14350705;17559060;676.985348880917<br>
14324206;14324205;17525992;690.86142794178<br>
14324207;14354647;17564505;698.702994306955<br>
14350705;14357566;17568800;725.054574549748<br>
14357566;14361210;17574058;744.377671982209<br>
14324156;14324164;17525954;775.199428174955<br>
14361210;14362309;17575712;785.251952246793<br>
14324165;14324164;17525955;788.303395916384<br>
<br>
This looks reason about until I try to reconstruct the tree and find that I actually have multiple disconnected trees :(<br>
</blockquote><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
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? </blockquote><div><br>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. <br>
<br>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.<br>
<br>Is the input graph that is being constructed, connected? <br>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..<br>
<br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">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?<br>
<br>
Other thoughts? I really need to be able to get to this data.<br>
<br>
Thanks,<br>
-Steve<br>
<br>
In these trees, in-dent means child of the the previous out-dent.<br>
<br>
50697<br>
+24143<br>
+24152<br>
+24142<br>
+24145<br>
+24146<br>
+24140<br>
+24144<br>
<br>
24153<br>
+24155<br>
+35807<br>
+35809<br>
+24164<br>
+24156<br>
+24165<br>
<br>
24154<br>
+33339<br>
+50695<br>
<br>
52132<br>
+57502<br>
+24205<br>
+24206<br>
<br>
24150<br>
+57469<br>
<br>
24149<br>
+24151<br>
<br>
24207<br>
+54647<br>
<br>
24141<br>
+50696<br>
+50693<br>
+50692<br>
<br>
35808<br>
+50705<br>
+57566<br>
+61210<br>
+62309<br>
<br>
<br>
-- this function sets up a call the the pg_routing driving_distance()<br>
-- function and returns the rows without creating polygons<br>
<br>
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)<br>
RETURNS SETOF path_result AS<br>
$BODY$<br>
DECLARE<br>
q text;<br>
srid integer;<br>
r record;<br>
source_id integer;<br>
<br>
BEGIN<br>
<br>
FOR r IN EXECUTE 'SELECT srid FROM geometry_columns WHERE f_table_name = '''||table_name||'''' LOOP<br>
END LOOP;<br>
<br>
srid := r.srid;<br>
<br>
RAISE NOTICE 'SRID: %', srid;<br>
RAISE NOTICE 'SELECT id FROM find_node_by_nearest_link_within_distance(''POINT(% %)'', %, ''%'');', x, y, bufdist, table_name;<br>
<br>
SELECT id INTO source_id<br>
FROM find_node_by_nearest_link_within_distance('POINT('||x||' '||y||')', bufdist, table_name);<br>
<br>
RAISE NOTICE 'SOURCE_ID: %', source_id;<br>
<br>
q := 'SELECT gid AS id, source::integer, target::integer, '||cost||' AS cost'<br>
|| CASE WHEN has_reverse_cost THEN ', '||reverse_cost||' AS reverse_cost ' ELSE '' END<br>
||' FROM '||table_name||' WHERE setsrid(''BOX3D('||x-bufdist||' '||y-bufdist||','<br>
||x+bufdist||' '||y+bufdist||')''::BOX3D, '||srid||') && the_geom';<br>
<br>
RAISE NOTICE 'Query: %', q;<br>
<br>
FOR r IN SELECT * FROM driving_distance(q, source_id, maxcost, directed, has_reverse_cost)<br>
LOOP<br>
RETURN NEXT r;<br>
END LOOP;<br>
<br>
RETURN;<br>
<br>
END;<br>
$BODY$<br>
LANGUAGE plpgsql VOLATILE STRICT<br>
COST 100<br>
ROWS 1000;<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>