[pgrouting-dev] Driving Directions Revisited

Thu Jun 2 21:40:03 EDT 2011

Oh, right! Much more simple and elegant solution.
Yes, we need to add it to all Dijkstra/A* wrappers. People using core
function can use this trick  right away.

Anton.

On 6/3/11, Daniel Kastl <daniel at georepublic.de> wrote:
> Hi Anton,
>
> Just yesterday this question was also asked in the Github ticket tracker:
> https://github.com/pgRouting/pgrouting/issues/34
>
> And there is another pretty simple way to solve this if you "ORDER BY cost".
> Then it takes always the cheapest, because it takes the first entry.
>
> Possible to add this "ORDER BY" by default?
>
> Daniel
>
>
> 2011/6/3 Anton Patrushev <anton.patrushev at georepublic.de>
>
>> 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
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: http://georepublic.de
>

-- 
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