Page 1 of 1

Help me make sense of complexx POSTgis query

Posted: Tue Sep 01, 2015 3:44 pm
by gautamz07
Can somebody help me make sense of the below query:

Code: Select all

SELECT seq, id1 AS path, id2 AS edge, cost FROM pgr_kdijkstraPath('
                SELECT gid AS id,
                         source::integer,
                         target::integer,
                         length::double precision AS cost
                        FROM ways',
                10, array[60,70,80], false, false);
Found it Here http://workshop.pgrouting.org/chapters/ ... -kdijkstra.

If somebody can atleast help me make the slightest bit of sense of it. I would be really grateful.

Thank you.

Re: Help me make sense of complexx POSTgis query

Posted: Tue Sep 01, 2015 5:45 pm
by requinix
*PostgreSQL. Or Postgres for short.

pgr_kdijkstraPath returns an ordered resultset listing (a) which target node you will end up at, (b) which edge to travel to next, and (c) the cost of travelling. You tell it where to start and where to end, and give it SQL to tell it what kinds of paths are available.

Then the first false means the available paths are bidirectional (a path A->B implies there is also a path B->A) and the second false means the reverse path (B->A) has the same cost as the forward path.

It might be easier to understand with some sample data.

Code: Select all

ways

gid | source | target | length
----+--------+--------+-------
  1 |     10 |     20 |      1
  2 |     10 |     30 |      2
  3 |     20 |     30 |      2
  4 |     30 |     40 |      1
  5 |     40 |     50 |      2
  6 |     40 |     60 |      2
  7 |     40 |     70 |      5
  8 |     60 |     70 |      4
  9 |     70 |     80 |      3
You, as a human, can figure out routes between 10 and 60:
1. 10 -> edge 1 (+1) -> 20 -> edge 3 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 6 (+2) -> 60 = 7
2. 10 -> edge 2 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 6 (+2) -> 60 = 5

The function will return the shortest route according to which paths ("edges") to take:

Code: Select all

seq | id1 | id2 | cost
----+-----+-----+-----
  0 |  60 |   2 |    2
  1 |  60 |   4 |    1
  2 |  60 |   6 |    2
If you wanted the route to 70 as well,
3. 10 -> edge 1 (+1) -> 20 -> edge 3 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 6 (+2) -> 60 -> edge 8 (+4) -> 70 = 10
4. 10 -> edge 1 (+1) -> 20 -> edge 3 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 7 (+5) -> 70 = 9
5. 10 -> edge 2 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 6 (+2) -> 60 -> edge 8 (+4) -> 70 = 9
6. 10 -> edge 2 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 7 (+5) -> 70 = 8

then you would get

Code: Select all

seq | id1 | id2 | cost
----+-----+-----+-----
  0 |  60 |   2 |    2
  1 |  60 |   4 |    1
  2 |  60 |   6 |    2
  3 |  70 |   2 |    2
  4 |  70 |   4 |    1
  5 |  70 |   7 |    5
The Cost function would return a summary with just the two endpoints and the total cost:

Code: Select all

seq | id1 | id2 | cost
----+-----+-----+-----
  0 |  10 |  60 |    5
  1 |  10 |  70 |    8

Re: Help me make sense of complexx POSTgis query

Posted: Wed Sep 02, 2015 5:05 am
by gautamz07
requinix ! thanks alot :0 that was very helpful of you and i understand bit more now . one more question , is the below table:

Code: Select all

seq | id1 | id2 | cost
----+-----+-----+-----
  0 |  60 |   2 |    2
  1 |  60 |   4 |    1
  2 |  60 |   6 |    2
generated using the below data:

1. 10 -> edge 1 (+1) -> 20 -> edge 3 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 6 (+2) -> 60 = 7
2. 10 -> edge 2 (+2) -> 30 -> edge 4 (+1) -> 40 -> edge 6 (+2) -> 60 = 5

if it is where are the values for the cost coloum coming from ?

Re: Help me make sense of complexx POSTgis query

Posted: Wed Sep 02, 2015 1:02 pm
by requinix
I listed all the possible paths for reference, but the function only returns results for the shortest one (according to cost). So that table corresponds to route #2 (and because 5 < 7, not because 3 jumps < 4 jumps).

seq = a serial value
id1 = the ending point (so you know which route the row is used for; all 60 for that example)
id2 = the ID of the edges to travel along (edges 2, 4, and 6)
cost = the cost of the edge (2, 1, 2)

Re: Help me make sense of complexx POSTgis query

Posted: Sun Sep 06, 2015 10:38 pm
by gautamz07
Thanks alot !