apsp_johnson for 2.2

Question

Planning to fix Issues related:

106

107

116

373

Basically has the same problematic as pgr_apspWarshall - It does not return an actual path, removing apsp will avoid people think of misleading functionality. - negative values returned when only positive values are accepted - has a warning (on travis)

Planning to solve in a similar manner as in this comment for pgr_apspWarshall

该提问来源于开源项目：pgRouting/pgrouting

Answer 1

From the v2.0 documentation and v2.1 documentation:

pgr_costResult[] pgr_apspJohnson(sql text);

• there is no mention about reverse_cost
• there is no directed flag
• results are (seq, id1, id2, cost)

For the 2.2 version:

CREATE OR REPLACE FUNCTION pgr_johnson(edges_sql TEXT, directed BOOLEAN)
RETURNS SET OF (seq bigint, from_vid bigint, to_vid bigint, cost float)

• As it does not returns an actual path, removing apsp will avoid people think of misleading functionality.
• It would be a mirror of boost.graph implementation except for:
• As in the other functions, we insert only edges with positive weights so:
  • the call to boost::graph::johnson_all_pairs_shortest it would be always return true.
• Fixes the negative return values pgr_apspJohnson its giving.
• Returns meaningful names
• Also accepts in the sql: id, source, target types that are ANY-INTEGER.
• if there are V vertices:
• Boost returns a VxV matrix.
  • We would only return the non infinity values.
  • for the undirected graph, even that the matrix its symmetric. So we let to the users choice of deleting the upper or lower part of the matrix using a wrapper.
  • The time complexity is O(V^3).

To fix the issues of the current pgr_apspJohnson:

• It would be a wrapper to pgr_apspJohnson where:
• before calling pgr_apspJohnson:
  • raises a notice of 'Deprecated Function: Use pgr_johnson instead'
  • enforces in the sql: id, source, target types that are integer
  • enforces the fact that it doesn't accept reverse_cost column
  • raises a notice if its found an it will be removed and the query without the reverse_cost column will be performed
• The directed graph version will be performed due to the fact that an undirected graph can be represented with a directed graph, but not vice versa.
• the return values of pgr_apspJohnson will be transformed to pgr_costresult type: (seq, id1, id2, cost)