pgr_KSP

pgr_KSP - Returns the "K" shortest paths.

images/boost-inside.jpeg

Boost Graph Inside

Availability

  • Version 2.1.0

    • Signature change

      • Old signature no longer supported

  • Version 2.0.0

    • Official function

Support

Description

The K shortest path routing algorithm based on Yen’s algorithm. "K" is the number of shortest paths desired.

Signatures

Summary

pgr_KSP(edges_sql, start_vid, end_vid, K [, directed] [, heap_paths])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET

Using defaults

pgr_ksp(edges_sql, start_vid, end_vid, K);
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
Example :

TBD

Complete Signature

pgr_KSP(edges_sql, start_vid, end_vid, K [, directed] [, heap_paths])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
Example :

TBD

Parameters

Column

Type

Description

edges_sql

TEXT

SQL query as described above.

start_vid

BIGINT

Identifier of the starting vertex.

end_vid

BIGINT

Identifier of the ending vertex.

k

INTEGER

The desiered number of paths.

directed

BOOLEAN

(optional). When false the graph is considered as Undirected. Default is true which considers the graph as Directed.

heap_paths

BOOLEAN

(optional). When true returns all the paths stored in the process heap. Default is false which only returns k paths.

Roughly, if the shortest path has N edges, the heap will contain about than N * k paths for small value of k and k > 1 .

Inner query

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)

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

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

Result Columns

Returns set of (seq, path_seq, path_id, node, edge, cost, agg_cost)

Column

Type

Description

seq

INTEGER

Sequential value starting from 1 .

path_seq

INTEGER

Relative position in the path of node and edge . Has value 1 for the beginning of a path.

path_id

BIGINT

Path identifier. The ordering of the paths For two paths i, j if i < j then agg_cost(i) <= agg_cost(j).

node

BIGINT

Identifier of the node in the path.

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 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 .

Additional Examples

Example :

To handle the one flag to choose signatures

The examples in this section use the following Network for queries marked as directed and cost and reverse_cost columns are used

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2,
      directed:=true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
(10 rows)

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
(10 rows)

Example :

For queries marked as directed with cost and reverse_cost columns

The examples in this section use the following Network for queries marked as directed and cost and reverse_cost columns are used

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
(10 rows)

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2, heap_paths:=true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
  11        3         1     2     4     1         0
  12        3         2     5    10     1         1
  13        3         3    10    12     1         2
  14        3         4    11    13     1         3
  15        3         5    12    -1     0         4
(15 rows)

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2, true, true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
  11        3         1     2     4     1         0
  12        3         2     5    10     1         1
  13        3         3    10    12     1         2
  14        3         4    11    13     1         3
  15        3         5    12    -1     0         4
(15 rows)

Examples :

For queries marked as undirected with cost and reverse_cost columns

The examples in this section use the following Network for queries marked as undirected and cost and reverse_cost columns are used

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2, directed:=false
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     2     1         0
   2        1         2     3     3     1         1
   3        1         3     4    16     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5    10     1         1
   8        2         3    10    12     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
(10 rows)

SELECT * FROM pgr_KSP(
     'SELECT id, source, target, cost, reverse_cost FROM edge_table',
      2, 12, 2, false, true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     2     1         0
   2        1         2     3     3     1         1
   3        1         3     4    16     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
  11        3         1     2     4     1         0
  12        3         2     5    10     1         1
  13        3         3    10    12     1         2
  14        3         4    11    13     1         3
  15        3         5    12    -1     0         4
  16        4         1     2     4     1         0
  17        4         2     5    10     1         1
  18        4         3    10    12     1         2
  19        4         4    11    11     1         3
  20        4         5     6     9     1         4
  21        4         6     9    15     1         5
  22        4         7    12    -1     0         6
(22 rows)

Example :

For queries marked as directed with cost column

The examples in this section use the following Network for queries marked as directed and only cost column is used

SELECT  * FROM pgr_KSP(
     'SELECT id, source, target, cost FROM edge_table',
      2, 3, 2
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
(0 rows)

SELECT  * FROM pgr_KSP(
     'SELECT id, source, target, cost FROM edge_table',
      2, 12, 2
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
(10 rows)

SELECT   * FROM pgr_KSP(
     'SELECT id, source, target, cost FROM edge_table',
      2, 12, 2, heap_paths:=true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
  11        3         1     2     4     1         0
  12        3         2     5    10     1         1
  13        3         3    10    12     1         2
  14        3         4    11    13     1         3
  15        3         5    12    -1     0         4
(15 rows)

SELECT  * FROM pgr_KSP(
     'SELECT id, source, target, cost FROM edge_table',
      2, 12, 2, true, true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
  11        3         1     2     4     1         0
  12        3         2     5    10     1         1
  13        3         3    10    12     1         2
  14        3         4    11    13     1         3
  15        3         5    12    -1     0         4
(15 rows)

Example :

For queries marked as undirected with cost column

The examples in this section use the following Network for queries marked as undirected and only cost column is used

SELECT  * FROM pgr_KSP(
     'SELECT id, source, target, cost FROM edge_table',
      2, 12, 2, directed:=false
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
(10 rows)

SELECT  * FROM pgr_KSP(
     'SELECT id, source, target, cost FROM edge_table',
      2, 12, 2, directed:=false, heap_paths:=true
   );
 seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
   1        1         1     2     4     1         0
   2        1         2     5     8     1         1
   3        1         3     6     9     1         2
   4        1         4     9    15     1         3
   5        1         5    12    -1     0         4
   6        2         1     2     4     1         0
   7        2         2     5     8     1         1
   8        2         3     6    11     1         2
   9        2         4    11    13     1         3
  10        2         5    12    -1     0         4
  11        3         1     2     4     1         0
  12        3         2     5    10     1         1
  13        3         3    10    12     1         2
  14        3         4    11    13     1         3
  15        3         5    12    -1     0         4
(15 rows)

See Also

Indices and tables