Line Graphs study for TRSP - pgRouting/pgrouting GitHub Wiki

What is a Line Graph?

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 following figures show a graph (left, with blue vertices) and its line graph (right, with green vertices).

Handling of Costs

• Cost associated with the nodes

  • Consider the following graph with nodes having costs:- The above graph is taken from the sample data

    The transformed Line Graph:-

    Each node of the transformed graph is an edge from the original graph. Here [1,2] denotes the node in the transformed graph which was an edge from node 1 to node 2 in the original graph.

    Each edge of the transformed graph is a tuple of nodes (n1, n2, n3) where n1, n2 and n3 are nodes from the original graph such that there was an edge from n1 -> n2 and another edge from n2 -> n3.

    Thus, the connection [1,4] -> [3, 4] goes through the vertex 4 as it is made up of (1, 4, 3) tuple which has an associated cost of 6 therefore the corresponding edge in the above graph gets a cost of 6.

• Cost associated with the edges

  • Consider the following graph with edges having costs:- The above graph is taken from the sample data

    The transformed Line Graph:-

    Here, the cost associated with an edge in the original graph moves to the corresponding nodes in the transformed Line Graph.

Here is the code that converts a graph into its Line Graph(This graph is limited to very small graphs with nodes <= 10).