[pgrouting-dev] Driving Directions Revisited

pgRouting pgrouting-dev
1

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

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;

2

On Tue, May 17, 2011 at 7:24 PM, Stephen Woodbridge <woodbri@swoodbridge.com> 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 :frowning:

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?

I will just guess here, since I am not exactly sure about the internals of driving distance. But, in theory, if the graph is not connected, the breadth-first-dijkstra-search algorithm would return multiple trees.

If the dijkstra implementation stops when no more vertices can be reached from source, then only single tree should be returned, excluding the vertices in other components of graph. But, if b-f-s is continued, then multiple search trees would be output.

Is the input graph that is being constructed, connected?
Would this have something to do with the result? Or if the driving_distance implementation search stops when no vertices are reachable, then I guess there would be some other issue…

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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

3

On 5/17/2011 4:37 PM, Jay Mahadeokar wrote:

[snip]

I will just guess here, since I am not exactly sure about the internals
of driving distance. But, in theory, if the graph is not connected, the
breadth-first-dijkstra-search algorithm would return multiple trees.

If the dijkstra implementation stops when no more vertices can be
reached from source, then only single tree should be returned, excluding
the vertices in other components of graph. But, if b-f-s is continued,
then multiple search trees would be output.

Is the input graph that is being constructed, connected?
Would this have something to do with the result? Or if the
driving_distance implementation search stops when no vertices are
reachable, then I guess there would be some other issue..

Jay,

Thanks for your thoughts. I had to go back and reread the description here:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/dijkstra_shortest_paths.html

So this does not do a breadth-first search but using dijkstra algorithm.

It should return a single tree with the source node cost=0.0

We also pass a predecessor map which I would like to output also as this would aid in reconstructing the tree. In theory I should be able to reconstruct the tree from the vertex_id and edge_id because the predecessor of vertex_d should be:

    case when b.source=vertex_id then b.target else b.source end as tid

in my query.

What I am concerned about and wondering about if there is a bug that is preventing some edges from being return the would link the various trees that I was able to reconstruct.

I will do some additional data analysis to try and validate that hypothesis.

-Steve

4

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

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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

5

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

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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

6

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@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 :frowning:

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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@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@georepublic.de
Web: http://georepublic.de

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

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

7

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@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@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 :frowning:

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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@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@georepublic.de
Web: http://georepublic.de

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

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

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

8

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@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@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@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 :frowning:
>>>
>>> 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@lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev@lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev@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@georepublic.de
Web: http://georepublic.de

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

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

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

Anton Patrushev
CTO

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

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

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