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

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