kDijkstra(Path) should return path nodes as well as path edges.

[sanak]

kDijkstra(Path) return values definition/sample is as follows.

seq:    row sequence
id1:    path vertex target id (identifies the target path).
id2:    path edge id
cost:   cost to traverse this edge or -1.0 if there is no path to this target

 seq | path | edge | cost
-----+------+------+------
   0 |    4 |   12 |    1
   1 |    4 |   13 |    1
   2 |    4 |   15 |    1
   3 |    4 |   16 |    1
   4 |   12 |   12 |    1
   5 |   12 |   13 |    1
(6 rows)

But above case, I can't determine which edge side(start/end) result path start. So, I think that the following definition is better. (Sample node values are dummies.)

seq:    path vertex target id (identifies the target path).
id1:    node id
id2:    edge id
cost:   cost to traverse this edge or -1.0 if there is no path to this target

path | node | edge | cost
-----+------+------+------
   4 |    1 |   12 |    1
   4 |    3 |   13 |    1
   4 |    5 |   15 |    1
   4 |    7 |   16 |    1
  12 |    9 |   12 |    1
  12 |   11 |   13 |    1
(6 rows)

[woodbri]

I think we need to consider another column because seq needs to be there to order the results. In set theory the order is not insured without an order by clause.

You can flip the edges if needed by:

1. see if seq=0 edge target is in seq=1 source or target otherwise flip this seq=0
2. for the remainder of the edges if edge[seq-1].target == edge[seq].target then flip edge[seq]

We might want to add a utility function like pgr_orientEdges() that takes a pgr_pathResult and flips edges as appropriate.

Nagase-san makes a good case that multi-path results should behave like single path results only they need an additional column to identify the which path a record belongs to and as such we should not drop an existing column to force fit it into the existing types. I tend to agree with this, so pgr_kdijkstra* and pgr_ksp* need a new result type defined.

[HSylvio]

Dear Sanak, while waiting for these modifications you may take a look at the first version of KDijkstra (if it still works): https://github.com/HSylvio/pgrouting/wiki/One_to_many-Dijkstra

where unreachable destination costs should be -1.

There also were different return types for cost and path: Paths are returned as a single (char*) value returning a list of gids (but I'm afraid it should be unuseable in some cases...). I expected that ST_Union would automatically flip edges, am I wrong?

Trying to standardize return types was quite commendable, but it's never easy to deal with...

Good luck!!

[woodbri]

We should also add an example of how to get the paths something like:

SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
  FROM pgr_kdijkstraPath(
                  'SELECT id, source, target, cost FROM edge_table',
                  10, array[4,12], false, false
            ) a,
            edge_table b
WHERE a.id2=b.id
GROUP by id1
ORDER by id1;

This should return one geometry for each path or a null geometry for an impossible path. I'm not sure there is anyway to insure the directionality of the path. (ie: it might get assembled in the reverse direction). Note that you need st_linemerge() to reorder the multipolygon returned by st_union().

[sanak]

Hi HSylvio, woodbri,

Thanks for your advise.

I think that the directionality of the path is useful, in the case of showing animation from start node to end node .etc. The following link is an old post about this. ftp://ftp.remotesensing.org/pgrouting/forum/pgrouting.postlbs.org/ticket/107.html

Thanks,

[woodbri]

Thank you for the link above. A simple wrapper plpgsql function could include the above sql and a quick check on the directionality of the result and flip it with st_reverse(the_geom) if needed.

Our goal around pgrouting 2.0 is to make low level stable functions that can easily be wrapper into application code. I do not think we want to solve everyones specific case or we will end up with hundreds of wrapper function that we need to document, test, and support and that are not widely used by MOST users. This is why we shed many of the legacy functions.

So the plan going forward will be to have people write wrappers and share them in gists, and then to review them and decide if some are generic and widely used/needed in the core code and then add them.

[woodbri]

Checked in changes for code, tests and documentation. Closing.