pgr_lineGraphFull - Experimental

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

Possible server crash

  • These functions might create a server crash

Warning

Experimental 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

Availability

  • Version 2.6.0

    • New Experimental function

Description

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.

A possible application of the resulting graph is "routing with two edge restrictions" :

  • Setting a cost of using the vertex when routing between edges on the connecting edge

  • Forbid the routing between two edges by removing the connecting edge

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.

The main characteristics are:

  • This function is for directed graphs.

  • Results are undefined when a negative vertex id is used in the input graph.

  • Results are undefined when a duplicated edge id is used in the input graph.

  • Running time: TBD

Signatures

Summary 

pgr_lineGraphFull(edges_sql)
RETURNS SET OF (seq, source, target, cost, edge)
    OR EMPTY SET

Using defaults 

pgr_lineGraphFull(TEXT edges_sql)
RETURNS SET OF (seq, source, target, cost, edge) OR EMPTY SET
Example :

Full line graph of subgraph of edges \(\{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)'
);
 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)

Parameters

Column

Type

Default

Description

sql

TEXT

SQL query as described above.

Inner query

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)

  • When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source) ,

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Additional Examples

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.

Example :

For generating the LineGraphFull

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);
first 
SELECT * FROM pgr_lineGraphFull('SELECT id,
                                        source,
                                        target,
                                        cost,
                                        reverse_cost
                                   FROM edge_table
                                     WHERE id IN (4,7,8,10)');
second

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

Example :

For creating table that identifies transformed vertices

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)
Example :

For running a dijkstra’s shortest path with turn penalties

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.

See Also

Indices and tables