# pgr_lineGraph - Proposed¶

pgr_lineGraph — Transforms the given graph into its corresponding edge-based graph.

Warning

Proposed functions for next mayor release.

• They are not officially in the current release.

• They will likely officially be part of the next mayor release:

• The functions make use of ANY-INTEGER and ANY-NUMERICAL

• Name might not change. (But still can)

• Signature might not change. (But still can)

• Functionality might not change. (But still can)

• pgTap tests have being done. But might need more.

• Documentation might need refinement.

Availability

• Version 3.7.0

• Promoted to proposed signature.

• Works for directed and undirected graphs.

• Version 2.5.0

• New Experimental function

## Description¶

Given a graph $$G$$, its line graph $$L(G)$$ is a graph such that:

• Each vertex of $$L(G)$$ represents an edge of $$G$$.

• Two vertices of $$L(G)$$ are adjacent if and only if their corresponding edges share a common endpoint in $$G$$

The main characteristics are:

• Works for directed and undirected graphs.

• The cost and reverse_cost columns of the result represent existence of the edge.

• When the graph is directed the result is directed.

• To get the complete Line Graph use unique identifiers on the double way edges (See Additional Examples).

• When the graph is undirected the result is undirected.

• The reverse_cost is always $$-1$$.

## Signatures¶

pgr_lineGraph(Edges SQL, [directed])
Returns set of (seq, source, target, cost, reverse_cost)
OR EMPTY SET
Example:

For an undirected graph with edges :math:’{2,4,5,8}’

SELECT * FROM pgr_lineGraph(
'SELECT id, source, target, cost, reverse_cost
FROM edges WHERE id IN (2,4,5,8)',
false);
seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
1 |      2 |      4 |    1 |           -1
2 |      2 |      5 |    1 |           -1
3 |      4 |      8 |    1 |           -1
4 |      5 |      8 |    1 |           -1
(4 rows)



## Parameters¶

Parameter

Type

Description

Edges SQL

TEXT

Edges SQL as described below.

### Optional parameters¶

Column

Type

Default

Description

directed

BOOLEAN

true

• When true the graph is considered Directed

• When false the graph is considered as Undirected.

## Inner Queries¶

### Edges SQL¶

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)

• 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

## Result columns¶

Returns set of (seq, source, target, cost, reverse_cost)

Column

Type

Description

seq

INTEGER

Sequential value starting from 1.

• Gives a local identifier for the edge

source

BIGINT

Identifier of the source vertex of the current edge.

• When negative: the source is the reverse edge in the original graph.

target

BIGINT

Identifier of the target vertex of the current edge.

• When negative: the target is the reverse edge in the original graph.

cost

FLOAT

Weight of the edge (source, target).

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

reverse_cost

FLOAT

Weight of the edge (target, source).

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

Given the following directed graph

$$G(V,E) = G(\{1,2,3,4\},\{ 1 \rightarrow 2, 1 \rightarrow 4, 2 \rightarrow 3, 3 \rightarrow 1, 3 \rightarrow 2, 3 \rightarrow 4, 4 \rightarrow 3\})$$

### Representation as directed with shared edge identifiers¶

For the simplicity, the design of the edges table on the database, has the edge’s identifiers are represented with 3 digits:

hundreds:

the source vertex

tens:

always 0, acts as a separator

units:

the target vertex

In this image,

• Single or double head arrows represent one edge (row) on the edges table.

• The numbers in the yellow shadow are the edge identifiers.

Two pair of edges share the same identifier when the reverse_cost column is used.

• Edges $${2 \rightarrow 3, 3 \rightarrow 2}$$ are represented with one edge row with $$id=203$$.

• Edges $${3 \rightarrow 4, 4 \rightarrow 3}$$ are represented with one edge row with $$id=304$$.

The graph can be created as follows:

CREATE TABLE edges_shared (
id BIGINT,
source BIGINT,
target BIGINT,
cost FLOAT,
reverse_cost FLOAT,
geom geometry
);
CREATE TABLE
INSERT INTO edges_shared (id, source, target, cost, reverse_cost, geom) VALUES
(102, 1, 2, 1, -1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(2,  2))),
(104, 1, 4, 1, -1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(0,  0))),
(301, 3, 1, 1, -1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  2))),
(203, 2, 3, 1,  1, ST_MakeLine(ST_POINT(2,  2), ST_POINT(2,  0))),
(304, 3, 4, 1,  1, ST_MakeLine(ST_POINT(0,  0), ST_POINT(2,  0)));


#### Line Graph of a directed graph represented with shared edges¶

SELECT seq, source, target, cost, reverse_cost
FROM pgr_lineGraph(
'SELECT id, source, target, cost, reverse_cost FROM edges_shared',
true);
seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
1 |    102 |    203 |    1 |           -1
2 |    104 |    304 |    1 |           -1
3 |    203 |    203 |    1 |            1
4 |    203 |    301 |    1 |           -1
5 |    203 |    304 |    1 |            1
6 |    301 |    102 |    1 |           -1
7 |    301 |    104 |    1 |           -1
8 |    304 |    301 |    1 |           -1
9 |    304 |    304 |    1 |            1
(9 rows)


• The result is a directed graph.

• For $$seq=4$$ from $$203 \leftrightarrow 304$$ represent two edges

• For all the other values of seq represent one edge.

• The cost and reverse_cost values represent the existence of the edge.

• When positive: the edge exists.

• When negative: the edge does not exist.

### Representation as directed with unique edge identifiers¶

For the simplicity, the design of the edges table on the database, has the edge’s identifiers are represented with 3 digits:

hundreds:

the source vertex

tens:

always 0, acts as a separator

units:

the target vertex

In this image,

• Single head arrows represent one edge (row) on the edges table.

• There are no double head arrows

• The numbers in the yellow shadow are the edge identifiers.

Two pair of edges share the same ending nodes and the reverse_cost column is not used.

• Edges $${2 \rightarrow 3, 3 \rightarrow 2}$$ are represented with two edges $$id=203$$ and $$id=302$$ respectively.

• Edges $${3 \rightarrow 4, 4 \rightarrow 3}$$ are represented with two edges $$id=304$$ and $$id=403$$ respectively.

The graph can be created as follows:

CREATE TABLE edges_unique (
id BIGINT,
source BIGINT,
target BIGINT,
cost FLOAT,
geom geometry
);
CREATE TABLE
INSERT INTO edges_unique (id, source, target, cost, geom) VALUES
(102, 1, 2, 1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(2,  2))),
(104, 1, 4, 1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(0,  0))),
(301, 3, 1, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  2))),
(203, 2, 3, 1, ST_MakeLine(ST_POINT(2,  2), ST_POINT(2,  0))),
(304, 3, 4, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  0))),
(302, 3, 2, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(2,  2))),
(403, 4, 3, 1, ST_MakeLine(ST_POINT(0,  0), ST_POINT(2,  0)));


#### Line Graph of a directed graph represented with unique edges¶

SELECT seq, source, target, cost, reverse_cost
FROM pgr_lineGraph(
'SELECT id, source, target, cost FROM edges_unique',
true);
seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
1 |    102 |    203 |    1 |           -1
2 |    104 |    403 |    1 |           -1
3 |    203 |    301 |    1 |           -1
4 |    203 |    304 |    1 |           -1
5 |    301 |    102 |    1 |           -1
6 |    301 |    104 |    1 |           -1
7 |    302 |    203 |    1 |            1
8 |    304 |    403 |    1 |            1
9 |    403 |    301 |    1 |           -1
10 |    403 |    302 |    1 |           -1
(10 rows)


• The result is a directed graph.

• For $$seq=7$$ from $$203 \leftrightarrow 302$$ represent two edges.

• For $$seq=8$$ from $$304 \leftrightarrow 403$$ represent two edges.

• For all the other values of seq represent one edge.

• The cost and reverse_cost values represent the existence of the edge.

• When positive: the edge exists.

• When negative: the edge does not exist.