[pgrouting-dev] Driving Directions Revisited

[Stephen Woodbridge]

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;