[pgrouting-dev] Driving Directions Revisited
Stephen Woodbridge
woodbri at swoodbridge.com
Mon May 23 17:06:18 EDT 2011
Anton, Daniel,
Have either of you had a chance to look at this problem?
I wrote a test program outside of the postgresql environment that
effectively runs the same query using the libpq-fe.h interface from C to
retrieve results. I returned path elements like:
typedef struct path_element
{
int vertex_id;
int parent_id;
int edge_id;
float8 cost;
} path_element_t;
where the parent_id is gotten from the predecessors map in C++ like:
p = vertex(predecessors[*vi], graph);
pe.parent_id = graph[p].id;
And in this case I can assemble a full tree using the vertex_id and the
parent_id with the records returned from C++. My leading theory is that
something is broken when we return records to postgresql and somehow
some of the records get lost.
That said, I have stared at the pgRouting code and I can not see what is
wrong or missing.
Any thoughts?
-Steve
On 5/19/2011 2:53 PM, Stephen Woodbridge wrote:
> 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
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list