# pgRouting Manual (3.0-rc1)

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

Support

- Supported versions: current(3.0)
- Unsupported versions: 2.6

## 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);

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

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

- https://en.wikipedia.org/wiki/Line_graph
- https://en.wikipedia.org/wiki/Complete_graph

Indices and tables

- Index
- Search Page