# 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

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

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

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

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

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

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