Hi Anton,<div><br></div><div>Just yesterday this question was also asked in the Github ticket tracker:</div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="https://github.com/pgRouting/pgrouting/issues/34">https://github.com/pgRouting/pgrouting/issues/34</a></div>
<div><br></div><div>And there is another pretty simple way to solve this if you "ORDER BY cost".</div><div>Then it takes always the cheapest, because it takes the first entry.</div><div><br></div><div>Possible to add this "ORDER BY" by default?</div>
<div><br></div><div>Daniel</div><div><br><br><div class="gmail_quote">2011/6/3 Anton Patrushev <span dir="ltr"><<a href="mailto:anton.patrushev@georepublic.de">anton.patrushev@georepublic.de</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi Steve,<br>
<br>
About parallel edges.<br>
It is well known issue of Dijkstra/A*. As it creates a graph as<br>
vertices list with one c cost between them (edge), it takes only one<br>
edge from set of parallel edges (one we add least no matter how high<br>
the cost is).<br>
There are three possible solutions. One with predecessors. Another one<br>
is to modify add_edge() to check previously added edges for given pair<br>
of vertices and add one with lowest cost. And one more solution is to<br>
break parallel edges to two with additional vertices.<br>
<br>
Anton.<br>
<div><div></div><div class="h5"><br>
On 5/24/11, Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>> wrote:<br>
> Anton, Daniel,<br>
><br>
> Have either of you had a chance to look at this problem?<br>
> I wrote a test program outside of the postgresql environment that<br>
> effectively runs the same query using the libpq-fe.h interface from C to<br>
> retrieve results. I returned path elements like:<br>
><br>
> typedef struct path_element<br>
> {<br>
> int vertex_id;<br>
> int parent_id;<br>
> int edge_id;<br>
> float8 cost;<br>
> } path_element_t;<br>
><br>
> where the parent_id is gotten from the predecessors map in C++ like:<br>
><br>
> p = vertex(predecessors[*vi], graph);<br>
> pe.parent_id = graph[p].id;<br>
><br>
> And in this case I can assemble a full tree using the vertex_id and the<br>
> parent_id with the records returned from C++. My leading theory is that<br>
> something is broken when we return records to postgresql and somehow<br>
> some of the records get lost.<br>
><br>
> That said, I have stared at the pgRouting code and I can not see what is<br>
> wrong or missing.<br>
><br>
> Any thoughts?<br>
><br>
> -Steve<br>
><br>
> On 5/19/2011 2:53 PM, Stephen Woodbridge wrote:<br>
>> Hi Anton, Daniel<br>
>><br>
>> I have taken an additional look at this and it appears to be two strange<br>
>> things happening in the results.<br>
>><br>
>> 1. there are definitely edges missing from the out. The missing edges<br>
>> would in fact connect the disconnected trees and obviously dijkstra<br>
>> traversed those edges because it is the only way to get to the<br>
>> disconnected trees.<br>
>><br>
>> 2. I have noticed at least one case where I had two parallel edges and<br>
>> one had a significantly larger cost, and it shows in the results but not<br>
>> the short edge. For example:<br>
>><br>
>><br>
>> s-----A------o-------B-------m--------C------o<br>
>> | |<br>
>> | |<br>
>> \-------D------/<br>
>><br>
>> edge D parallels B, but is 4x as long as B. In the output A, D, and C<br>
>> are exist but not B, the driving distance starts at s and the cost at m<br>
>> is A + D, not A + B and C is missing.<br>
>><br>
>> I'm not sure what if anything more I can do at this point. There is<br>
>> nothing special about my data that I can think of. I have been running<br>
>> my tests and analysis in pgAdmin3 to get lists of input edges and output<br>
>> nodes and then generating trees of it by hand. I/m also plotting the<br>
>> segments and gids using mapserver from the table in postgis. The are no<br>
>> costs <= 0 so it should be well behaved.<br>
>><br>
>> Thoughts?<br>
>><br>
>> -Steve<br>
>><br>
>> On 5/17/2011 9:54 AM, Stephen Woodbridge wrote:<br>
>>> Hi Anton,<br>
>>><br>
>>> I need some help with this. I think I have run into a bug. What I am<br>
>>> trying to do is reconstruct the Dijkstra tree from the driving<br>
>>> 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<br>
>>> 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),<br>
>>> 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<br>
>>> that I actually have multiple disconnected trees :(<br>
>>><br>
>>> Leaving off the 143 prefix to all the nodes above, I get the following 9<br>
>>> trees. Any ideas why I am not getting a single connected tree? Am I not<br>
>>> interpreting the results correctly? Would it be possible to patch the C<br>
>>> 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<br>
>>> varying, x double precision, y double precision, maxcost double<br>
>>> precision, bufdist double precision, "cost" character varying,<br>
>>> reverse_cost character varying, directed boolean, has_reverse_cost<br>
>>> 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 =<br>
>>> '''||table_name||'''' LOOP<br>
>>> END LOOP;<br>
>>><br>
>>> srid := r.srid;<br>
>>><br>
>>> RAISE NOTICE 'SRID: %', srid;<br>
>>> RAISE NOTICE 'SELECT id FROM<br>
>>> find_node_by_nearest_link_within_distance(''POINT(% %)'', %, ''%'');',<br>
>>> x, y, bufdist, table_name;<br>
>>><br>
>>> SELECT id INTO source_id<br>
>>> FROM find_node_by_nearest_link_within_distance('POINT('||x||' '||y||')',<br>
>>> bufdist, table_name);<br>
>>><br>
>>> RAISE NOTICE 'SOURCE_ID: %', source_id;<br>
>>><br>
>>> q := 'SELECT gid AS id, source::integer, target::integer, '||cost||' AS<br>
>>> cost'<br>
>>> || CASE WHEN has_reverse_cost THEN ', '||reverse_cost||' AS reverse_cost<br>
>>> ' ELSE '' END<br>
>>> ||' FROM '||table_name||' WHERE setsrid(''BOX3D('||x-bufdist||'<br>
>>> '||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,<br>
>>> 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">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>
>><br>
>> _______________________________________________<br>
>> pgrouting-dev mailing list<br>
>> <a href="mailto:pgrouting-dev@lists.osgeo.org">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>
><br>
> _______________________________________________<br>
> pgrouting-dev mailing list<br>
> <a href="mailto:pgrouting-dev@lists.osgeo.org">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>
><br>
<br>
<br>
</div></div>--<br>
Georepublic UG (haftungsbeschränkt)<br>
Salzmannstraße 44,<br>
81739 München, Germany<br>
<br>
Anton Patrushev<br>
CTO<br>
<br>
eMail: <a href="mailto:anton.patrushev@georepublic.de">anton.patrushev@georepublic.de</a><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a><br>
<br>
Tel: +49 (089) 420 959 519<br>
Sip: <a href="mailto:1959519@sipgate.de">1959519@sipgate.de</a><br>
<br>
Commercial register: Amtsgericht München, HRB 181428<br>
CEO: Daniel Kastl<br>
<div><div></div><div class="h5">_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">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>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66, 99, 171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66, 99, 171)" target="_blank">http://georepublic.de</a></span><br>
</div>