pgr_edgeDisjointPaths - Proposed

Name

pgr_edgeDisjointPaths — Calculates edge disjoint paths between two groups of vertices.

Warning

These are proposed functions

  • They are not officially of the current release.
  • They likely will not be officially be part of the next release:
    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
    • Name might change.
    • Signature might change.
    • Functionality might change.
    • pgTap tests might be missing.
    • Might need c/c++ coding.
    • May lack documentation.
    • Documentation if any might need to be rewritten.
    • Documentation examples might need to be automatically generated.
    • Might need a lot of feedback from the comunity.
    • Might depend on a proposed function of pgRouting
    • Might depend on a deprecated function of pgRouting
_images/boost-inside.jpeg

Boost Graph Inside

Synopsis

Calculates the edge disjoint paths between two groups of vertices. Utilizes underlying maximum flow algorithms to calculate the paths.

Characteristics:

The main characterics are:
  • Calculates the edge disjoint paths between any two groups of vertices.
  • Returns EMPTY SET when source and destination are the same, or cannot be reached.
  • The graph can be directed or undirected.
  • One to many, many to one, many to many versions are also supported.
  • Uses pgr_maxFlowBoykovKolmogorov - Proposed to calculate the paths.
  • No cost or aggregate cost of the paths are returned. (Under discussion)

Signature Summary

pgr_edgeDisjointPaths(edges_sql, source_vertex, destination_vertex)
pgr_edgeDisjointPaths(edges_sql, source_vertex, destination_vertex, directed)
pgr_edgeDisjointPaths(edges_sql, source_vertices, destination_vertex, directed)
pgr_edgeDisjointPaths(edges_sql, source_vertex, destination_vertices, directed)
pgr_edgeDisjointPaths(edges_sql, source_vertices, destination_vertices, directed)

RETURNS SET OF (seq, path_seq, [start_vid,] [end_vid,] node, edge) OR EMPTY SET

Signatures

Minimal signature

pgr_edgeDisjointPaths(edges_sql, source_vertex, destination_vertex)
RETURNS SET OF (seq, path_seq, node, edge) OR EMPTY SET

The minimal signature is between source_vertex and destination_vertex for a directed graph.

Example:
SELECT * FROM pgr_edgeDisjointPaths(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    3, 5
);
 seq | path_seq | node | edge 
-----+----------+------+------
   1 |        1 |    3 |    2
   2 |        2 |    2 |    4
   3 |        3 |    5 |   -1
   4 |        1 |    3 |    5
   5 |        2 |    6 |    8
   6 |        3 |    5 |   -1
(6 rows)

One to One

The available signature calculates edge disjoint paths from one source vertex to one destination vertex. The graph can be directed or undirected.

pgr_edgeDisjointPaths(edges_sql, source_vertex, destination_vertex, directed)
RETURNS SET OF (seq, path_seq, node, edge) OR EMPTY SET
Example:
SELECT * FROM pgr_edgeDisjointPaths(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    3, 5,
    directed := false
);
 seq | path_seq | node | edge 
-----+----------+------+------
   1 |        1 |    3 |    2
   2 |        2 |    2 |    4
   3 |        3 |    5 |   -1
   4 |        1 |    3 |    3
   5 |        2 |    4 |   16
   6 |        3 |    9 |    9
   7 |        4 |    6 |    8
   8 |        5 |    5 |   -1
   9 |        1 |    3 |    5
  10 |        2 |    6 |   11
  11 |        3 |   11 |   12
  12 |        4 |   10 |   10
  13 |        5 |    5 |   -1
(13 rows)

One to Many

The available signature calculates the maximum flow from one source vertex to many sink vertices.

pgr_edgeDisjointPaths(edges_sql, source_vertex, destination_vertices, directed)
RETURNS SET OF (seq, path_seq, end_vid, node, edge) OR EMPTY SET
Example:
SELECT * FROM pgr_edgeDisjointPaths(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    3, ARRAY[4, 5, 10]
);
 seq | path_seq | end_vid | node | edge 
-----+----------+---------+------+------
   1 |        1 |       5 |    3 |    2
   2 |        2 |       5 |    2 |    4
   3 |        3 |       5 |    5 |   -1
   4 |        1 |       5 |    3 |    5
   5 |        2 |       5 |    6 |    8
   6 |        3 |       5 |    5 |   -1
(6 rows)

Many to One

The available signature calculates the maximum flow from many source vertices to one sink vertex.

pgr_edgeDisjointPaths(edges_sql, source_vertices, destination_vertex)
RETURNS SET OF (seq, path_seq, start_vid, node, edge)
  OR EMPTY SET
Example:
SELECT * FROM pgr_edgeDisjointPaths(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    ARRAY[3, 6], 5
);
 seq | path_seq | start_vid | node | edge 
-----+----------+-----------+------+------
   1 |        1 |         3 |    3 |    2
   2 |        2 |         3 |    2 |    4
   3 |        3 |         3 |    5 |   -1
   4 |        1 |         6 |    6 |    8
   5 |        2 |         6 |    5 |   -1
(5 rows)

Many to Many

The available signature calculates the maximum flow from many sources to many sinks.

pgr_edgeDisjointPaths(edges_sql, source_vertices, destination_vertices, directed)
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge) OR EMPTY SET
Example:
SELECT * FROM pgr_edgeDisjointPaths(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    ARRAY[3, 6], ARRAY[4, 5, 10]
);
 seq | path_seq | start_vid | end_vid | node | edge 
-----+----------+-----------+---------+------+------
   1 |        1 |         3 |       5 |    3 |    2
   2 |        2 |         3 |       5 |    2 |    4
   3 |        3 |         3 |       5 |    5 |   -1
   4 |        1 |         6 |       5 |    6 |    8
   5 |        2 |         6 |       5 |    5 |   -1
   6 |        1 |         6 |       4 |    6 |    9
   7 |        2 |         6 |       4 |    9 |   16
   8 |        3 |         6 |       4 |    4 |   -1
(8 rows)

Description of the Signatures

Description of the SQL query

edges_sql:an SQL query, which should return a set of rows with the following columns:
Column Type 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.
going ANY-NUMERIC A positive value represents the existence of the edge (source, target).
coming ANY-NUMERIC A positive value represents the existence of the edge (target, source).
Where:
  • ANY-INTEGER:SMALLINT, INTEGER, BIGINT
  • ANY-NUMERIC:SMALLINT, INTEGER, BIGINT, REAL, DOUBLE PRECISION

Description of the parameters of the signatures

Column Type Description
edges_sql TEXT SQL query as described above.
source_vertex BIGINT Identifier(s) of the source vertex(vertices).
sink_vertex BIGINT Identifier(s) of the destination vertex(vertices).
directed BOOLEAN (optional) Determines the type of the graph. Default TRUE.

Description of the return values

Column Type Description
seq INT Sequential value starting from 1.
path_seq INT Relative position in the path. Has value 1 for the beginning of a path.
start_vid BIGINT Identifier of the starting vertex. Used when multiple starting vertices are in the query.
end_vid BIGINT Identifier of the ending vertex. Used when multiple ending vertices are in the query.
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.

Indices and tables