[pgrouting-dev] Driving Directions Revisited

Thu Jun 2 21:23:06 EDT 2011

Hi Steve,

About parallel edges.
It is well known issue of Dijkstra/A*. As it creates a graph as
vertices list with one c cost between them (edge), it takes only one
edge from set of parallel edges (one we add least no matter how high
the cost is).
There are three possible solutions. One with predecessors. Another one
is to modify add_edge() to check previously added edges for given pair
of vertices and add one with lowest cost. And one more solution is to
break parallel edges to two with additional vertices.

Anton.

On 5/24/11, Stephen Woodbridge <woodbri at swoodbridge.com> wrote:
> 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
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>

-- 
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Anton Patrushev
CTO

eMail: anton.patrushev at georepublic.de
Web: http://georepublic.de

Tel: +49 (089) 420 959 519
Sip: 1959519 at sipgate.de

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl