Support v2.1 TRSP(pgr_trsp) via edges

[sanak]

Create new function files (trsp_via_nodes.py/trsp_via_edges.py).

[sanak]

Supported this on pgr-2.1.0 branch's following commit. https://github.com/pgRouting/pgRoutingLayer/commit/d4ab01be611b355aa8e5ca3c91e197b344eb7292

Detecting each paths require more pgRouting side improvement. But, I will think about this at pgRouting next version. https://github.com/pgRouting/pgrouting/issues/392

[cvvergara]

Q, what do you mean by detecting each paths?

[cvvergara]

the route_id like for [1, 11, 6] first route is from 1 to 11 second path is from 11 to 6?

[woodbri]

The current pgr_trsp() that supports vias is a simple plpgsql function, it should be easy to clone, rename and add the additional column that you need, because the function just loops through the array and calls pgr_trsp() multiple times, so add a loop counter and return that as value for the extra column.

[sanak]

@cvvergara

Q, what do you mean by detecting each paths? the route_id like for [1, 11, 6] first route is from 1 to 11 second path is from 11 to 6?

Yes. In some cases, each paths' cost calculation may be useful like OSRM result. (From 1 to 11 cost is x, from 11 to 6 cost is y .etc) If result column includes such path ID or from ID, to ID, then its calculation become easier. https://github.com/pgRouting/pgrouting/issues/392#issuecomment-132902682 1. Without path ID (assume id1=node ID, id2=edge ID) ... Detecting each paths is difficult.

 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |  -1 |   1 |  0.5
   1 |   2 |   4 |    1
   2 |   5 |   8 |    1
   3 |   6 |  11 |    1
   1 |  11 |  13 |    1
   2 |  12 |  15 |    1
   3 |   9 |   9 |    1
   4 |   6 |   8 |    1
   5 |   5 |   7 |    1
   6 |   8 |   6 |  0.5
(10 rows)

2. With path ID (assume id1=path ID, id2=node ID, id3=edge ID) ... Detecting each paths is easy.

 seq | id1 | id2 | id3 | cost
-----+-----+-----+-----+------
   0 |   0 |  -1 |   1 |  0.5
   1 |   0 |   2 |   4 |    1
   2 |   0 |   5 |   8 |    1
   3 |   0 |   6 |  11 |  0.5
   4 |   1 |  -1 |  11 |  0.5
   5 |   1 |  11 |  13 |    1
   6 |   1 |  12 |  15 |    1
   7 |   1 |   9 |   9 |    1
   8 |   1 |   6 |   8 |    1
   9 |   1 |   5 |   7 |    1
  10 |   1 |   8 |   6 |  0.5
(11 rows)

In case of No.2 (with path ID), we can get each paths' cost easily (without writing PL/pgSQL script).

SELECT a.id1 AS path_id, SUM(a.cost) AS cost FROM
(select * from pgr_trsp(
    'select id, source::integer, target::integer,cost,
         reverse_cost from edge_table',
    ARRAY[1,11,6]::integer[],           -- array of eids
    ARRAY[0.5, 0.5, 0.5]::float8[],     -- array of pcts
    true,
    true)) AS a
GROUP BY id1 ORDER BY id1;

 path_id | cost 
---------+------
       0 |    3
       1 |    6
(2 rows)

@woodbri Yes, I worte it at the following temporary commit on my pgrouting4w repository.

• https://github.com/sanak/pgrouting4w/commit/5f7bfbb5e098838ed5700a61c9edbf0dfbcb30e6
• routing_trsp_vias.sql

But, QGIS pgRoutingLayer plugin is for official pgRouting module, so I can't assume such additional(unofficial) PL/pgSQL script.

[cvvergara]

@sanak Steve modified trsp vias, in this branch: https://github.com/pgRouting/pgrouting/tree/develop-trsp-fix Its not merged yet into develop because I need to modify the documentation, (2 of the queries don't use the sample data) Right now I am working on adjusting documentation of Dijkstra based on the changes made for the sequence.

[sanak]

@cvvergara Okay, thanks for information. I will check both modifications about 12 hours later.

[cvvergara]

@sanak I already checked them, one of the queries is fixed:

select * from pgr_trsp(
doc_data(#     'select eid as id, source::integer, target::integer,cost,
doc_data'#         reverse_cost from edges1',
doc_data(#     ARRAY[1,8,13,5]::integer[],     -- array of vids
doc_data(#     true,  -- directed graph?
doc_data(#     true,  -- has_reverse_cost?
doc_data(#     -- include the turn restrictions
doc_data(#     'select to_cost, teid as target_id, feid ||
doc_data'#         coalesce('',''||via,'''') as via_path from restrictions1');
 seq | id1 | id2 | cost 
-----+-----+-----+------
   1 |   1 |   1 |    1
   2 |   2 |   4 |    1
   3 |   7 |   8 |    1
   4 |   8 |   8 |    1
   5 |   7 |  10 |    1
   6 |  10 |  14 |    1
   7 |  13 |  14 |    1
   8 |  10 |  10 |    1
   9 |   7 |   7 |    1
  10 |   6 |   6 |    1
  11 |   5 |  -1 |    0
(11 rows)

But not the other one:

elect * from pgr_trsp(
doc_data(#     'select eid as id, source::integer, target::integer,cost,
doc_data'#          reverse_cost from edges1',
doc_data(#     ARRAY[1,11,6]::integer[],           -- array of eids
doc_data(#     ARRAY[0.5, 0.5, 0.5]::float8[],     -- array of pcts
doc_data(#     true,  -- directed graph?
doc_data(#     true,  -- has_reverse_cost?
doc_data(#     -- include the turn restrictions
doc_data(#     'select to_cost, teid as target_id, feid ||
doc_data'#         coalesce('',''||via,'''') as via_path from restrictions1');
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |  -1 |   1 |  0.5
   1 |   2 |   4 |    1
   2 |   7 |   8 |    1
   3 |   8 |  11 |    1
   1 |  11 |  13 |    1
   2 |  12 |  15 |    1
   3 |   9 |   9 |    1
   4 |   8 |   8 |    1
   5 |   7 |   7 |    1
   6 |   6 |   6 |  0.5
(10 rows)

We are going to see this tomorrow morning (our morning)

[sanak]

Okay, thanks for information.

[cvvergara]

@sanak Steve made pgr_trsp3 that inludes the id1= route_id here: https://github.com/pgRouting/pgrouting/blob/develop-trsp-fix/src/trsp/sql/routing_trsp_vias.sql See if it fits your requirements (I haven't changed the documentation, but the code is clear and working)

[robe2]

Let's call it pgr_trsp_vias so it's clearer. The 3 is going to be confusing to a user.

[robe2]

I meant to say pgr_trspVias

[woodbri]

I chose pgr_trsp3() because it is returning pgr_costresult3 and pgr_trsp is returning pgr_costresult.

I think that this will likely totally change in 3.0 so I would not obsess over the names. If you want to change it no big deal. My hope is that trsp will get totally merged into dijkstra so all functions will work with or without restrictions, because we get requests all the time for ksp and kdistrstra to work with restrictions and I don't think we want to duplicate all the dijkstra functions into trsp.

[sanak]

@cvvergara, @woodbri, @robe2 Okay, thanks for your modification and confirmation ! I will check it about 10 hours later.

[cvvergara]

changes are in develop_2_1_0 http://docs.pgrouting.org/dev/src/trsp/doc/index.html#trsp

[cvvergara]

@woodbri @robe2 @sanak I used the suggested name pgr_trspVia that @robe2 suggested (forgot the plural) But, tomorrow morning., I'll do the necessary changes to move it back to pgr_trsp3. I'll post when I am done.

[sanak]

@cvvergara Okay, thanks for information.

[dkastl]

Let's call it pgr_trsp_vias so it's clearer. The 3 is going to be confusing to a user.

Well, I don't like the 3 either, but I also agree with @woodbri that we shouldn't be too obsessed with names, as we hopefully solve this better in v3.0.

Maybe stupid question, but why can't we just name it pgr_trsp? I think the arguments are different, so it will make use of Function Overloading.

[cvvergara]

@dkastl you can overload when the parameters are different, but not when the result structure is different. https://github.com/pgRouting/pgrouting/blob/develop-trsp-fix/src/trsp/sql/routing_trsp_vias.sql#L123 and https://github.com/pgRouting/pgrouting/blob/develop-trsp-fix/src/trsp/sql/routing_trsp_vias.sql#L136 are still there. where they just drop a column from the results of pgr_trsp3 and move the id2 to id1, id3 to id2

[cvvergara]

@sanak I pushed develop_2_1_0 I updated the trsp documentation with very very minimal changes: Changed in the synopsis and changed the examples to use the new name and to use the sample data of the documentation: http://docs.pgrouting.org/dev/src/trsp/doc/index.html#trsp

[cvvergara]

Forgot to mention: It's pgr_trsp_vias the name.

[dkastl]

Speaking about unifying function and column names, I would prefer not to use underscores in function names (except the pgr_ prefix), but for column names it makes sense as it would require quoting them if we would use camel case:

• Function: pgr_myFunction()
• Column: my_attribute

[cvvergara]

ok, so I will change the name to: pgr_trspVias

[dkastl]

Hmmm, why do we use plural? And not just pgr_trspVia?

[cvvergara]

ok pgr_trspVia

[cvvergara]

@sanak in develop_2_1_0 the function name is pgr_trspVia http://docs.pgrouting.org/dev/src/trsp/doc/index.html#trsp

[sanak]

@cvvergara, @dkastl Okay, thanks! I will start to check it about 1 hours later.

[cvvergara]

@sanak ok, I will not make changes to develop_2_1_0 (I am still working on documentation) until you tell me that you tested it.

[sanak]

@cvvergara I confirmed that the function worked correctly. By the way, about the naming I disagree with pgr_trspVia naming, because not only pgr_trspVia but also pgr_trsp accept "via" arguments (vids and eids). I think that it will be pgr_trspWithPathId or something from its meaning (pgr_costResult3 type id1 means path ID to support multiple path case). But, as @woodbri said, this will be temporal function by v3.0, so I agree with pgr_trsp3 naming. Sorry for my late response.

[cvvergara]

@sanak @dkastl It takes me 5 minutes to change the name, also, In the documentation it doesn't say its temporal, experimental, nor proposed. So, I guess it is going to be official part of pgRouting. is an official name going to have a 3? So, as its in develop_2_1_0, we can consider that anything can happen, its not merged into develop, I can do what you instruct me to do. @woodbri didn't delete the original ones, but they are not documented either. (they are a wrapper that drop a column of pgr_trspVia and renames to id1 and id2 the remaining columns).

[sanak]

@cvvergara Okay, thanks for information. TO All: Which naming do you prefer ?

• pgr_trspWithPathId
• pgr_trsp3

[cvvergara]

Thinking on the future.... pgr_DijkstraVia pgr_kspVia I like pgr_trspVia

[cvvergara]

@sanak I merged some changes that @woodbri made.

[woodbri]

I'm fine with pgr_trspVia()

[dkastl]

By the way, about the naming I disagree with pgr_trspVia naming, because not only pgr_trspVia but also pgr_trsp accept "via" arguments (vids and eids). I think that it will be pgr_trspWithPathId or something from its meaning (pgr_costResult3 type id1 means path ID to support multiple path case).

@sanak Thanks for this clarification, because I only thought about the naming and didn't realize that both functions support routing "via" points.

So I'm trying a reset and start over again: why do we need pgr_trsp3? Because it would be more convenient to have another column returned with the "Path ID"?

If that's correct, then wouldn't it be better to just change pgr_trsp and add this column? But this would break backwards compatibility, right? Would it really matter for users, if there is an additional column? But we could just return the same as pgr_trsp plus a column path_id for example. We couldn't use the pgr_costresult3 then, which was convenient for pgRouting developers, but for users there is not so much benefit. Or do I miss something?

Somehow I agree with @sanak and pgr_trspVia makes users think that pgr_trsp does not provide via points, which is not the case.

[cvvergara]

@dkastl There is no backwards compatibility to brake. pgr_trsp with the vias support didn't exist in V2.0 the only thing that avoid us to use pgr_trsp (without the 3) is that the code that returns id1, id2 columns is still there as a wrapper of the one that returns id1, id2, id3

[dkastl]

OK. Then "via" support in pgr_trsp would be just a "hidden feature" (not documented?) and in pgr_trspVia it would be available with the available path ID attribute to make it easier to use?

[cvvergara]

Forgot to mention the pgr_trsp that has the C/C++ code does not provide the via. the 2 column original version yes, would be hidden, undocumented... I think mainly because of what Steve told me, that he made this functions week after 2.0 was released. so people are used to it, but by not making it official, its easier to remove... aka, people have time to adjust their applications to the documented version.

[cvvergara]

And appending the Via word to the name of the algorithm. there can be a pgr_dijkstraVia, pgr_kspVia, pgr_trspVia, pgrFooVia... can help group algorithms by functionalities. Kind of also making a dictionary for function names also. ( @woodbri suggested this)

[cvvergara]

So, more options can be considered: pgr_fooViaPoints, pgr_fooViaEdges, pgr_fooViaVertices

[woodbri]

This is very simple and straight forward as far as pgrouting 2.x is concerned. We have:

create type pgr_costresult as (
  seq,  -- record seq number
  id1,   -- vertex id
  id2,   -- edge id
  cost   -- cost to traverse edge
);
create type pgr_costresult3 as (
  seq,  -- record seq number
  id1,   -- path id
  id2,   -- vertex id
  id3,   -- edge id
  cost   -- cost to traverse edge
);

These two types are already used in other functions. For consistency, if you want to return the path id with the function pgr_trsp() with vias then you should use pgr_costresult3. Since I had already written pgr_trsp() with vias that did not return the path id and now we needed to also have a version that returned the path id. I picked this follow names:

pgr_trsp() with vias without path_id returns pgr_costresult pgr_trsp3() with vias with path_id returns pgr_costresult3

The reason is because they both have the same arguments. And this function has been in develop branch for almost two years.

I'm fine if you want to call it pgr_trspvia(), but that confuses the issue the pgr_trsp() also support vias.

I think it would be better to spend time on what 3.0 should look like, rather than spend all the time on this. pgr_trsp3() is simple to remember that it returns pgr_costresult3 and pgr_trsp() returns pgr_costresult. Then in 3.0 we should be focused on what is common and different between all the rework that Vicky is doing. Do we add via support to other functions? Does TRSP go away and Dijkstra optionally supports turn restrictions? When I did 2.0, I had to make a spreadsheet that should all the functions, all their arguments and there return types then tried to simplify that to something that was easy to work with and consistent. This needs to be done as part of 3.0 planning. Vicky is doing an awesome job with pgrouting but it would help her if we had a google spreadsheet and started documenting all the signatures so we can see the big picture and not focus on just one command.

[cvvergara]

about costResult and costResult3 you can see here: https://github.com/pgRouting/pgrouting/blob/develop_2_1_0/src/common/sql/pgrouting-types.sql That I am not using any extra postgresql types... so for 3.0 costResult and CostResult3 will no longer be needed.

[woodbri]

Right, those 3 types were to abstract the something like 8-10 types we had in 1.5 and there was no consistency at all. every function returned its own random, similar by different type and that made it very hard to to write code that you could change from dijkstra to astar to shooting star to whatever. I don't care what the types are as long as they are consistent with respect to column names and column order so it is easy to interchange results of functions that are doing similar things. This is why building a dictionary makes a huge amount of sense.

[cvvergara]

For pgr_apsJohnson the meaning of id1 id2 are different. http://docs.pgrouting.org/2.0/en/src/apsp_johnson/doc/index.html#pgr-apsp-johnson

[sanak]

If pgr_trsp via mode functions become hidden ones, then I agree to use pgr_trspVia naming. (Then, future pgr_dijkstraVia and pgr_astarVia naming become to make sense.)

[cvvergara]

Ok, thanks, I'll do the merge into develop soon.

[sanak]

@woodbri Is it possible to return round trip edge row twice in via edges case ? (In the following example, return edge ID=10 row twice.) Or is it make sense to add merge_edges argument to pgr_trspVia function with default true ? (If merge_edges value equals false, then pgr_trspVia function returns each rows without merging edges.)

Round trip - via edges case

SELECT seq, id1 AS path, id2 AS node, id3 AS edge, cost FROM pgr_trspVia('
    SELECT id AS id,
        source::int4 AS source,
        target::int4 AS target,
        cost::float8 AS cost 
        FROM edge_table',
    ARRAY[6,10,4]::integer[], ARRAY[0.49,0.51,0.51]::float8[], false, false, null);
 seq | path | node | edge | cost 
-----+------+------+------+------
   1 |    1 |   -1 |    6 | 0.51
   2 |    1 |    8 |    7 |    1
   3 |    1 |    5 |   10 | 1.02
   4 |    2 |    5 |    4 | 0.49
(4 rows)

Because in round trip via nodes case, round trip edge (edge ID=10) is returned twice.

Round trip - via nodes case

SELECT seq, id1 AS path, id2 AS node, id3 AS edge, cost FROM pgr_trspVia('
    SELECT id AS id,
        source::int4 AS source,
        target::int4 AS target,
        cost::float8 AS cost 
        FROM edge_table',
    ARRAY[7,10,2]::integer[], false, false, null);
 seq | path | node | edge | cost 
-----+------+------+------+------
   1 |    1 |    7 |    6 |    1
   2 |    1 |    8 |    7 |    1
   3 |    1 |    5 |   10 |    1
   4 |    2 |   10 |   10 |    1
   5 |    2 |    5 |    4 |    1
   6 |    2 |    2 |   -1 |    0
(6 rows)

[woodbri]

@sanak this is a case I did not think about. The current code will return the same edge multiple times if they are not adjacent. If they are adjacent, then it should try to merge the costs, but this is a corner case that might need more checking. The merge code is in plpgsql function and it is trying to eliminate the -1 in vertex_id and/or edge_id columns at the end and start of the next path that needs to be merged and only leave the final record with edge=-1.

Please take a look and see if you can find a better way to do this merge.

[sanak]

@woodbri Okay, thanks for information! I will check it later.

[cvvergara]

can something like this be helpful in some way? from this output what do you need?

 seq | start_v | end_v | vertex | edge | cost | agg_cost 
-----+---------+-------+--------+------+------+----------
   1 |       7 |    10 |      7 |    6 |    1 |        0
   2 |       7 |    10 |      8 |    7 |    1 |        1
   3 |       7 |    10 |      5 |   10 |    1 |        2
   4 |       7 |    10 |     10 |   -1 |    0 |        3
   5 |      10 |     2 |     10 |   10 |    1 |        3
   6 |      10 |     2 |      5 |    4 |    1 |        4
   7 |      10 |     2 |      2 |   -1 |    0 |        5