pgr_lineGraphFull — Transforms a given graph into a new graph where all of the vertices from the original graph are converted to line graphs.
Warning
Experimental functions
pgr_lineGraphFull, converts original directed graph to a directed line graph by converting each vertex to a complete graph and keeping all the original edges. The new connecting edges have a cost 0 and go between the adjacent original edges, respecting the directionality.
This is possible because each of the intersections (vertices) in the original graph are now complete graphs that have a new edge for each possible turn across that intersection.
pgr_lineGraphFull(edges_sql)
RETURNS SET OF (seq, source, target, cost, edge)
OR EMPTY SET
pgr_lineGraphFull(TEXT edges_sql)
RETURNS SET OF (seq, source, target, cost, edge) OR EMPTY SET
| Example: |
|---|
SELECT * FROM pgr_lineGraphFull(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table
WHERE id IN (4,7,8,10)'
);
seq | source | target | cost | edge
-----+--------+--------+------+------
1 | -1 | 5 | 1 | 4
2 | 2 | -1 | 0 | 0
3 | -2 | 2 | 1 | -4
4 | -3 | 8 | 1 | -7
5 | -4 | 6 | 1 | 8
6 | -5 | 10 | 1 | 10
7 | 5 | -2 | 0 | 0
8 | 5 | -3 | 0 | 0
9 | 5 | -4 | 0 | 0
10 | 5 | -5 | 0 | 0
11 | -6 | -2 | 0 | 0
12 | -6 | -3 | 0 | 0
13 | -6 | -4 | 0 | 0
14 | -6 | -5 | 0 | 0
15 | -7 | -2 | 0 | 0
16 | -7 | -3 | 0 | 0
17 | -7 | -4 | 0 | 0
18 | -7 | -5 | 0 | 0
19 | -8 | -2 | 0 | 0
20 | -8 | -3 | 0 | 0
21 | -8 | -4 | 0 | 0
22 | -8 | -5 | 0 | 0
23 | -9 | -6 | 1 | 7
24 | 8 | -9 | 0 | 0
25 | -10 | -7 | 1 | -8
26 | 6 | -10 | 0 | 0
27 | -11 | -8 | 1 | -10
28 | 10 | -11 | 0 | 0
(28 rows)
| edges_sql: | an SQL query, which should return a set of rows with the following columns: |
|---|
| Column | Type | Default | 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. | |
| cost | ANY-NUMERICAL |
Weight of the edge (source, target)
|
|
| reverse_cost | ANY-NUMERICAL |
-1 | Weight of the edge (target, source),
|
Where:
| ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
|---|---|
| ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
| Column | Type | Default | Description |
|---|---|---|---|
| sql | TEXT |
SQL query as described above. |
The examples of this section are based on the Sample Data network.
The examples include the subgraph including edges 4, 7, 8, and 10 with reverse_cost.
This example displays how this graph transformation works to create additional edges for each possible turn in a graph.
SELECT id, source, target, cost, reverse_cost
FROM edge_table
WHERE id IN (4,7,8,10);
SELECT * FROM pgr_lineGraphFull('SELECT id,
source,
target,
cost,
reverse_cost
FROM edge_table
WHERE id IN (4,7,8,10)');
In the transformed graph, all of the edges from the original graph are still present (yellow), but we now have additional edges for every turn that could be made across vertex 6 (orange).
The vertices in the transformed graph are each created by splitting up the vertices in the original graph. Unless a vertex in the original graph is a leaf vertex, it will generate more than one vertex in the transformed graph. One of the newly created vertices in the transformed graph will be given the same vertex-id as the vertex that it was created from in the original graph, but the rest of the newly created vertices will have negative vertex ids. Following is an example of how to generate a table that maps the ids of the newly created vertices with the original vertex that they were created from
The first step is to store your results graph into a table and then create the vertex mapping table with one row for each distinct vertex id in the results graph.
CREATE TABLE lineGraph_edges AS SELECT * FROM pgr_lineGraphFull(
$$SELECT id, source, target, cost, reverse_cost
FROM edge_table WHERE id IN (4,7,8,10)$$
);
SELECT 28
CREATE TABLE lineGraph_vertices AS
SELECT *, NULL::BIGINT AS original_id
FROM (SELECT source AS id FROM lineGraph_edges
UNION
SELECT target FROM lineGraph_edges) as foo
ORDER BY id;
SELECT 16
Next, we set the original_id of all of the vertices in the results graph that were given the same vertex id as the vertex that it was created from in the original graph.
UPDATE lineGraph_vertices AS r
SET original_id = v.id
FROM edge_table_vertices_pgr AS v
WHERE v.id = r.id;
UPDATE 5
Then, we cross reference all of the other newly created vertices that do not have the same original_id and set their original_id values.
WITH
unassignedVertices
AS (SELECT e.id, e.original_id
FROM lineGraph_vertices AS e
WHERE original_id IS NOT NULL),
edgesWithUnassignedSource
AS (SELECT *
FROM lineGraph_edges
WHERE cost = 0 and source IN (SELECT id FROM unassignedVertices)),
edgesWithUnassignedSourcePlusVertices
AS (SELECT *
FROM edgesWithUnassignedSource
JOIN lineGraph_vertices
ON(source = id)),
verticesFromEdgesWithUnassignedSource
AS (SELECT DISTINCT edgesWithUnassignedSourcePlusVertices.target,
edgesWithUnassignedSourcePlusVertices.original_id
FROM edgesWithUnassignedSourcePlusVertices
JOIN lineGraph_vertices AS r
ON(target = r.id AND r.original_id IS NULL))
UPDATE lineGraph_vertices
SET original_id = verticesFromEdgesWithUnassignedSource.original_id
FROM verticesFromEdgesWithUnassignedSource
WHERE verticesFromEdgesWithUnassignedSource.target = id;
UPDATE 8
WITH
unassignedVertices
AS (SELECT e.id, e.original_id
FROM lineGraph_vertices AS e
WHERE original_id IS NOT NULL),
edgesWithUnassignedTarget
AS (SELECT *
FROM lineGraph_edges
WHERE cost = 0 and target IN (SELECT id FROM unassignedVertices)),
edgesWithUnassignedTargetPlusVertices
AS (SELECT *
FROM edgesWithUnassignedTarget
JOIN lineGraph_vertices
ON(target = id)),
verticesFromEdgesWithUnassignedTarget
AS (SELECT DISTINCT edgesWithUnassignedTargetPlusVertices.source,
edgesWithUnassignedTargetPlusVertices.original_id
FROM edgesWithUnassignedTargetPlusVertices
JOIN lineGraph_vertices AS r
ON(source = r.id AND r.original_id IS NULL))
UPDATE lineGraph_vertices
SET original_id = verticesFromEdgesWithUnassignedTarget.original_id
FROM verticesFromEdgesWithUnassignedTarget
WHERE verticesFromEdgesWithUnassignedTarget.source = id;
UPDATE 3
The only vertices left that have not been mapped are a few of the leaf vertices from the original graph. The following sql completes the mapping for these leaf vertices (in the case of this example graph there are no leaf vertices but this is necessary for larger graphs).
WITH
unassignedVertexIds
AS (SELECT id
FROM lineGraph_vertices
WHERE original_id IS NULL),
edgesWithUnassignedSource
AS (SELECT source,edge
FROM lineGraph_edges
WHERE source IN (SELECT id FROM unassignedVertexIds)),
originalEdgesWithUnassignedSource
AS (SELECT id,source
FROM edge_table
WHERE id IN (SELECT edge FROM edgesWithUnassignedSource))
UPDATE lineGraph_vertices AS d
SET original_id = (SELECT source
FROM originalEdgesWithUnassignedSource
WHERE originalEdgesWithUnassignedSource.id =
(SELECT edge
FROM edgesWithUnassignedSource
WHERE edgesWithUnassignedSource.source = d.id))
WHERE id IN (SELECT id FROM unassignedVertexIds);
UPDATE 0
WITH
unassignedVertexIds
AS (SELECT id
FROM lineGraph_vertices
WHERE original_id IS NULL),
edgesWithUnassignedTarget
AS (SELECT target,edge
FROM lineGraph_edges
WHERE target IN (SELECT id FROM unassignedVertexIds)),
originalEdgesWithUnassignedTarget
AS (SELECT id,target
FROM edge_table
WHERE id IN (SELECT edge FROM edgesWithUnassignedTarget))
UPDATE lineGraph_vertices AS d
SET original_id = (SELECT target
FROM originalEdgesWithUnassignedTarget
WHERE originalEdgesWithUnassignedTarget.id =
(SELECT edge
FROM edgesWithUnassignedTarget
WHERE edgesWithUnassignedTarget.target = d.id))
WHERE id IN (SELECT id FROM unassignedVertexIds);
UPDATE 0
Now our vertex mapping table is complete:
SELECT * FROM lineGraph_vertices;
id | original_id
-----+-------------
2 | 2
5 | 5
6 | 6
8 | 8
10 | 10
-11 | 10
-10 | 6
-9 | 8
-5 | 5
-4 | 5
-3 | 5
-2 | 5
-1 | 2
-8 | 5
-7 | 5
-6 | 5
(16 rows)
One use case for this graph transformation is to be able to run a shortest path search that takes into account the cost or limitation of turning. Below is an example of running a dijkstra’s shortest path from vertex 2 to vertex 8 in the original graph, while adding a turn penalty cost of 100 to the turn from edge 4 to edge -7.
First we must increase set the cost of making the turn to 100:
UPDATE lineGraph_edges
SET cost = 100
WHERE source IN (SELECT target
FROM lineGraph_edges
WHERE edge = 4) AND target IN (SELECT source
FROM lineGraph_edges
WHERE edge = -7);
UPDATE 1
Then we must run a dijkstra’s shortest path search using all of the vertices in the new graph that were created from vertex 2 as the starting point, and all of the vertices in the new graph that were created from vertex 8 as the ending point.
SELECT * FROM
(SELECT * FROM
(SELECT * FROM pgr_dijkstra($$SELECT seq AS id, * FROM lineGraph_edges$$,
(SELECT array_agg(id) FROM lineGraph_vertices where original_id = 2),
(SELECT array_agg(id) FROM lineGraph_vertices where original_id = 8)
)) as shortestPaths
WHERE start_vid = 2 AND end_vid = 8 AND (cost != 0 OR edge = -1)) as b;
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
29 | 2 | 2 | 8 | -1 | 1 | 1 | 0
31 | 4 | 2 | 8 | -4 | 5 | 1 | 1
33 | 6 | 2 | 8 | -10 | 25 | 1 | 2
35 | 8 | 2 | 8 | -3 | 4 | 1 | 3
36 | 9 | 2 | 8 | 8 | -1 | 0 | 4
(5 rows)
Normally the shortest path from vertex 2 to vertex 8 would have an aggregate cost of 2, but since there is a large penalty for making the turn needed to get this cost, the route goes through vertex 6 to avoid this turn.
If you cross reference the node column in the dijkstra results with the vertex id mapping table, this will show you that the path goes from v2 -> v5 -> v6 -> v5 -> v8 in the original graph.
Indices and tables