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