pgr_lineGraph  Proposed¶
pgr_lineGraph
— Transforms the given graph into its corresponding edgebased
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 ANYINTEGER and ANYNUMERICAL
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
andreverse_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¶
directed
])(seq, source, target, cost, reverse_cost)
 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 as described below. 
Optional parameters¶
Column 
Type 
Default 
Description 





Inner Queries¶
Edges SQL¶
Column 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge ( 


ANYNUMERICAL 
1 
Weight of the edge (

Where:
 ANYINTEGER:
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result columns¶
Returns set of (seq, source, target, cost, reverse_cost)
Column 
Type 
Description 



Sequential value starting from 1.



Identifier of the source vertex of the current edge.



Identifier of the target vertex of the current edge.



Weight of the edge (



Weight of the edge (

Additional Examples¶
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 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
andreverse_cost
values represent the existence of the edge.When positive: the edge exists.
When negative: the edge does not exist.
See Also¶
wikipedia: Line Graph
mathworld: Line Graph
Indices and tables