# [pgrouting-users] Wierd results using pgr_kdijkstraPath

AUS - Eyad b00038807 at aus.edu
Fri Dec 19 13:28:44 PST 2014

Hi All,

Today I progressed on calculating the costs of routing from sources to targets, and started to get weird results which does not only indicate network fault!

I calculated the cost of routing “to the different points” from the little-pinkish point in the middle/bottom side of the layout as above

I used the below code to create the cost table:

create table l0_cost_gate1 as

SELECT seq, id1 as source, id2 as target, cost FROM pgr_kdijkstraCost(

'SELECT id, source, target, (st_length(geom) * 0.001) as cost FROM schema.network_noded',

(SELECT id FROM schema.l0_pv2 WHERE id=286, (SELECT array_agg(id) FROM dcc_schema.l0_pv1), false, false

)

Afterward I inner_joint the original points feature with the resulted cost table (from the above code)

Then I selected all target points accessible (from the source point) within routing cost <= 300

As you see in the above map (the resulted points in yellow!)

What is weird is that:

1)      The point on the extreme left side has a cost=39 only, although, it’s not connected to the vector network (this point is planned to be connected via stairs coming from another floor)

2)      The points in blue shall be accessible before a majority of points on the left/right sides of layout

Such results (especially point#1 above) may significantly indicate that the issue is not only a network problem

Just to confirm, I repeated the same exercise (using the same network and points) to route from another source point.. below are similar results (only one point in cyan color is not accessible):

Also, the yellow point on the extreme left side has cost of only “37” to access from the source point

Sorry to interrupt you repeatedly with my emails, but I think that this exercise my help in further development/education of pgRouting

From: pgrouting-users-bounces at lists.osgeo.org [mailto:pgrouting-users-bounces at lists.osgeo.org] On Behalf Of Daniel Kastl
Sent: Friday, December 19, 2014 11:43 AM
To: pgRouting users mailing list
Subject: Re: [pgrouting-users] Wierd results using pgr_kdijkstraPath

Looking at just a few of your network images, the network is definitely broken afterwards. So it's not the fault of the shortest path algorithm.

Without access to the data I can only guess, but often CAD data may contain geomtries, that don't work well for GIS.

When I look at some screenshots and which parts have been removed, could it be, that your data contains circles or self-intersecting linestrings for example?

Daniel

On Fri, Dec 19, 2014 at 4:16 PM, AUS - Eyad <b00038807 at aus.edu> wrote:

Thanks Steve..

It seems that I may need to re-install the pgRouting to update the
"ST_DumpPoints()"?

correctly? Or I may get to same situation if the bug is in the nodding, not
in splitting lines?

I have done a cross-check for the pgr_kdijkstraCost and pgr_kdijkstraPath
results. The cost results are exactly the same. But I'm still not sure if
the calculated cost is done based on the real shortest_path because I can't
see the outcome on the map

If you think that the bug of nodding is only impacting the reflective Path
outcome? but the Cost outcome is fine? I would rather to complete my
exercise for now as I'm running out of time.. I can fix this later

beginner

Thanks again

-----Original Message-----
From: pgrouting-users-bounces at lists.osgeo.org
[mailto:pgrouting-users-bounces at lists.osgeo.org] On Behalf Of Stephen
Woodbridge

Sent: Friday, December 19, 2014 2:36 AM
To: pgrouting-users at lists.osgeo.org
Subject: Re: [pgrouting-users] Wierd results using pgr_kdijkstraPath

On 12/18/2014 1:51 PM, AUS - Eyad wrote:
> Also pgr_analyzeGraph function returned in the Messages Tab:
>
> NOTICE:              ANALYSIS RESULTS FOR SELECTED EDGES:
> NOTICE:                    Isolated segments: 7
> NOTICE:  Potential gaps found near dead ends: 1
> NOTICE:               Intersections detected: 62
> NOTICE:                      Ring geometries: 0
>
> I don't know if this is positive or negative, but would like to know your
> feedback
>
> Maybe the isolated segments are lines which are not connected to the
> network? Is there a way to visualize each group of the above lines?

So this command adds columns "cnt" amd "chk" to the vertices_tmp table.

Isolated segments are identified by the fact that both the start and end

select *
from edges a, vertices_tmp b, vertices_tmp c
where a.source=b.id and a.target=c.id and b.cnt=1 and c.cnt=1;

or maybe:

select *
from vertices_tmp a, edges b
where a.chk>0 and st_dwithin(a.geom, b.geom, <distance>);

Intersections detected indicates you have lines that cross but are not
noded where they cross. You have to split all lines if they cross and
make sure there is node at the intersection.

There is a tool pgr_nodeNetwork() that can help, but there has recently
been a big found in it and a patch posted with the ticket for the bug.
https://github.com/pgRouting/pgrouting/issues/280

-Steve

>
>
> -----Original Message-----
> From: AUS - Eyad [mailto:b00038807 at aus.edu]
> Sent: Thursday, December 18, 2014 9:54 PM
> To: 'pgRouting users mailing list'
> Subject: RE: [pgrouting-users] Wierd results using pgr_kdijkstraPath
>
> The function
>
> SELECT pgr_analyzeGraph('schema.network_noded',50,'geom');
>
> Returned "OK"
>
> Feel free to ask for any other details. I know it's not easy to get things
> done remotely.
>
>
>
> -----Original Message-----
> From: pgrouting-users-bounces at lists.osgeo.org
> [mailto:pgrouting-users-bounces at lists.osgeo.org] On Behalf Of Stephen
> Woodbridge
> Sent: Thursday, December 18, 2014 8:25 PM
> To: pgrouting-users at lists.osgeo.org
> Subject: Re: [pgrouting-users] Wierd results using pgr_kdijkstraPath
>
> Ok this sounds reasonable.
>
> Give this a try:
> http://docs.pgrouting.org/dev/src/common/doc/functions/analyze_graph.html
>
> It is hard to diagnose problems remotely via the list.
>
> -Steve
>
> On 12/18/2014 10:48 AM, AUS - Eyad wrote:
>> Here is st_astext(geom) function result (below table).
>>
>> For both createTopology and nodeNetwork functions, I used "50" as
>> tolerance because my data unit is in millimeter. However, the network is
>> done on CAD and fairly not poor in resolution.
>>
>> Is this what you wanted, or you need another layout/map? I attached many
>> layouts/maps already in the previous 3 emails.. let me know if you were
>> not able to visualize
>>
>>
>> -----Original Message-----
>> From: pgrouting-users-bounces at lists.osgeo.org
>> [mailto:pgrouting-users-bounces at lists.osgeo.org] On Behalf Of Stephen
>> Woodbridge
>> Sent: Thursday, December 18, 2014 7:26 PM
>> To: pgrouting-users at lists.osgeo.org
>> Subject: Re: [pgrouting-users] Wierd results using pgr_kdijkstraPath
>>
>>
>> What does you geomerty look like?
>>
>> Select st_astext(geom) from edges limit 10;
>>
>> What value did you use for tolerance when creating your topology?
>>
>> What value did you use for tolerance when you noded your network?
>>
>> -Steve
>>
>> On 12/18/2014 10:17 AM, AUS - Eyad wrote:
>>
>>   > And here I enclose below the resulted travel_costs' table of
>>
>>   > pgr_dijkstra function:
>>
>>   >
>>
>>   > Note that Shortest path cost on original network (between the 2 lines
> of
>>
>>   > the resulted vector feature) is around 250m (below - by converting
from
>>
>>   > millimeter to meter) whereas the sum of costs in the above table is
>>
>>   > around 45m only
>>
>>   >
>>
>>   > Thanks..
>>
>>   >
>>
>>
>>   >
>>
>>   > *From:*AUS - Eyad [mailto:b00038807 at aus.edu]
>>
>>   > *Sent:* Thursday, December 18, 2014 7:02 PM
>>
>>   > *To:* 'pgRouting users mailing list'
>>
>>   > *Subject:* RE: [pgrouting-users] Wierd results using
pgr_kdijkstraPath
>>
>>   >
>>
>>   > Here is a prt_sc after trying pgr_dijkstra as follows:
>>
>>   >
>>
>>   > SELECT seq, id1 as path, (b.geom) as geom, cost FROM pgr_dijkstra(
>>
>>   >
>>
>>   >      'SELECT id, source, target, (st_length(geom) * 0.001) as cost
FROM
>>
>>   > schema.network_noded',
>>
>>   >
>>
>>   >      336, (SELECT MAX(id) FROM schema.l1_pv1), false, false
>>
>>   >
>>
>>   >    ) a, schema.network_noded b
>>
>>   >
>>
>>   > WHERE a.id1=b.id
>>
>>   >
>>
>>   > As you may see, there is only too little parts of the network's lines
>>
>>   > left (on the sides of the layout)! No route is visible
>>
>>   >
>>
>>   > Hope this clarifies..
>>
>>   >
>>
>>
>>   >
>>
>>   > *From:*AUS - Eyad [mailto:b00038807 at aus.edu]
>>
>>   > *Sent:* Thursday, December 18, 2014 6:29 PM
>>
>>   > *To:* 'pgRouting users mailing list'
>>
>>   > *Subject:* RE: [pgrouting-users] Wierd results using
pgr_kdijkstraPath
>>
>>   >
>>
>>   > Hi Daniel,
>>
>>   >
>>
>>   > Enclosed are 3 maps (1^st prt_sc with the original network, 2^nd &
3^rd
>>
>>   > prt_sc with the resulted network)
>>
>>   >
>>
>>   > Clearly, the majority of the network has faded away
>>
>>   >
>>
>>   > Awaiting your feedback, I would work on 2^nd suggestion
>>
>>   >
>>
>>   > Regards,
>>
>>   >
>>
>>
>>   >
>>
>>   > *From:*pgrouting-users-bounces at lists.osgeo.org
>>
>>   > [mailto:pgrouting-users-bounces at lists.osgeo.org] *On Behalf Of
>> *Daniel Kastl
>>
>>   > *Sent:* Thursday, December 18, 2014 6:28 AM
>>
>>   > *To:* pgRouting users mailing list
>>
>>   > *Subject:* Re: [pgrouting-users] Wierd results using
pgr_kdijkstraPath
>>
>>   >
>>
>>
>>   >
>>
>>   > It's difficult to give an answer based on your query and problem
>>
>>   > description only. I guess, that (still) your network topology is not
>>
>>   > correct. It looks like a data problem.
>>
>>   >
>>
>>   > There are 2 things you could do for now:
>>
>>   >
>>
>>   > (1) Show us some image of your "weird de-attached "little" pieces"
>>
>>   >
>>
>>   > (2) Try a simple shortest path query with one start and one end point
>>
>>   > and see if it works with pgr_dijkstra function for example.
>>
>>   >
>>
>>   > Daniel
>>
>>   >
>>
>>   > On Thu, Dec 18, 2014 at 7:37 AM, AUS - Eyad <b00038807 at aus.edu
>>
>>   > <mailto:b00038807 at aus.edu>> wrote:
>>
>>   >
>>
>>   > Hello pgr_Experts,
>>
>>   >
>>
>>   > I'm trying to get all the routes from a source point (i.e. 336) to a
>>
>>   > group of target/destination points (located at different edges/ends
of
>>
>>   > linestrings' network) using the below code:
>>
>>   >
>>
>>   > SELECT seq, id1 as path, id2 as node, id3 as edge, (b.geom) as geom,
>>
>>   > cost FROM pgr_kdijkstraPath(
>>
>>   >
>>
>>   > 'SELECT id, source, target, (st_length(geom) * 0.001) as cost FROM
>>
>>   > schema.network_noded',
>>
>>   >
>>
>>   > 336, (SELECT array_agg(id) FROM schema.l1_pv1), false, false
>>
>>   >
>>
>>   > ) a, schema.network_noded b
>>
>>   >
>>
>>   > WHERE a.id1=b.id <http://b.id>
>>
>>   >
>>
>>   > It's resulting a weird de-attached "little" pieces of my original
>>
>>   > nodded_network! However, the number of resulted paths is equal to the
>>
>>
>>   >
>>
>>   > 1)What potential mistake I may have committed?
>>
>>   >
>>
>>   > 2)Does it mean that all the calculated travel_cost(s) are wrong (as
> they
>>
>>   > are reflected/represented by wrong linestrings)?
>>
>>   >
>>
>>   > I'm using QGIS 2.4.0 and pgRouting pg93-binaries-2.4.0
>>
>>   >
>>
>>   > I found similar question on this list of pgRouting users, asked by
>>
>>   > Antonio last October
>>
>>   >
>>
(http://lists.osgeo.org/pipermail/pgrouting-users/2014-October/001992.html
>>
>>   > ), but obviously the question is not answered yet?
>>
>>   >
>>
>>   > Regards..
>>
>>   >
>>
>>
>>   >
>>
>>   >
>>
>>   > _______________________________________________
>>
>>   > Pgrouting-users mailing list
>>
>>   > Pgrouting-users at lists.osgeo.org
> <mailto:Pgrouting-users at lists.osgeo.org>
>>
>>   > http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>>   >
>>
>>   >
>>
>>   > --
>>
>>   >
>>
>>   > Georepublic UG & Georepublic Japan
>>
>>   > eMail: daniel.kastl at georepublic.de
<mailto:daniel.kastl at georepublic.de>
>>
>>   > Web: http://georepublic.info
>>
>>   >
>>
>>   >
> ------------------------------------------------------------------------
>>
>>   >
>>
>>   > No virus found in this message.
>>
>>   > Checked by AVG - www.avg.com <http://www.avg.com>
>>
>>   > Version: 2015.0.5577 / Virus Database: 4253/8755 - Release Date:
> 12/17/14
>>
>>   >
>>
>>   >
>>
>>   >
>>
>>   > _______________________________________________
>>
>>   > Pgrouting-users mailing list
>>
>>   > Pgrouting-users at lists.osgeo.org
>>
>>   > http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>>   >
>>
>> _______________________________________________
>>
>> Pgrouting-users mailing list
>>
>> Pgrouting-users at lists.osgeo.org
>>
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>> -----
>>
>> No virus found in this message.
>>
>> Checked by AVG - www.avg.com
>>
>> Version: 2015.0.5577 / Virus Database: 4253/8755 - Release Date: 12/17/14
>>
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2015.0.5577 / Virus Database: 4253/8755 - Release Date: 12/17/14
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
-----
No virus found in this message.
Checked by AVG - www.avg.com

Version: 2015.0.5577 / Virus Database: 4253/8761 - Release Date: 12/18/14

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--

Georepublic UG & Georepublic Japan
eMail:  <mailto:daniel.kastl at georepublic.de> daniel.kastl at georepublic.de
Web:  <http://georepublic.info> http://georepublic.info

_____

No virus found in this message.
Checked by AVG - www.avg.com
Version: 2015.0.5577 / Virus Database: 4253/8761 - Release Date: 12/18/14

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 464 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image004.png
Type: image/png
Size: 503 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0005.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image006.png
Type: image/png
Size: 459 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0006.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image007.png
Type: image/png
Size: 444 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0007.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 43323 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0002.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image010.jpg
Type: image/jpeg
Size: 47944 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20141220/4fc98104/attachment-0003.jpg>