Via - Category

proposed

Warning

Proposed functions for next mayor release.

  • They are not officially in the current release.
  • They will likely officially be part of the next mayor release:
    • The functions make use of ANY-INTEGER and ANY-NUMERICAL
    • Name might not change. (But still can)
    • Signature might not change. (But still can)
    • Functionality might not change. (But still can)
    • pgTap tests have being done. But might need more.
    • Documentation might need refinement.

General Information

This category intends to solve the general problem:

Given a graph and a list of vertices, find the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all vertices

In other words, find a continuos route that visits all the vertices in the order given.

path:represents a section of a route.
route:is a sequence of paths

Parameters

Used on:

Parameter Type Default Description
Edges SQL TEXT   SQL query as described.
via vertices ARRAY[ ANY-INTEGER ]   Array of ordered vertices identifiers that are going to be visited.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Besides the compulsory parameters each function has, there are optional parameters that exist due to the kind of function.

Via optional parameters

Used on all Via functions

Parameter Type Default Description
strict BOOLEAN false
  • When true if a path is missing stops and returns EMPTY SET
  • When false ignores missing paths returning all paths found
U_turn_on_edge BOOLEAN true
  • When true departing from a visited vertex will not try to avoid

Inner Queries

Depending on the function one or more inner queries are needed.

Edges SQL

Column Type Default Description
id ANY-INTEGER   Identifier of the edge.
source ANY-INTEGER   Identifier of the first end point vertex of the edge.
target ANY-INTEGER   Identifier of the second end point vertex of the edge.
cost ANY-NUMERICAL   Weight of the edge (source, target)
reverse_cost ANY-NUMERICAL -1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Restrictions SQL

Column Type Description
path ARRAY[ ANY-INTEGER ] Sequence of edge identifiers that form a path that is not allowed to be taken. - Empty arrays or NULL arrays are ignored. - Arrays that have a NULL element will raise an exception.
Cost ANY-NUMERICAL Cost of taking the forbidden path.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Column Type Description
seq INTEGER Sequential value starting from 1.
path_id INTEGER Identifier of a path. Has value 1 for the first path.
path_seq INTEGER Relative position in the path. Has value 1 for the beginning of a path.
start_vid BIGINT Identifier of the starting vertex of the path.
end_vid BIGINT Identifier of the ending vertex of the path.
node BIGINT Identifier of the node in the path from start_vid to end_vid.
edge BIGINT

Identifier of the edge used to go from node to the next node in the path sequence.

  • -1 for the last node of the path.
  • -2 for the last node of the route.
cost FLOAT Cost to traverse from node using edge to the next node in the path sequence.
agg_cost FLOAT Aggregate cost from start_vid to node.
route_agg_cost FLOAT Total cost from start_vid of seq = 1 to end_vid of the current seq.

Note

When start_vid, end_vid and node columns have negative values, the identifier is for a Point.

See Also

Indices and tables