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

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

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