Line Graph Approach

[vidhan13j07]

Considering the sample data given here.

We will try to transform the given sample data graph into its corresponding Line Graph(Edge based graph).

An undirected edge between A --- B can be converted into two directed edges from A -- > B and B -- > A.

Since the sample graph contains a mixture of directed and undirected edges, we break down each undirected edge into two directed edges.

Each edge in the original graph becomes a node in the transformed graph and the consecutive edges in the original graph form an edge in the transformed graph.

What are consecutive edges?

Let s(e_i) be the starting node and t(e_i) be the target node of edge e_i.

Edges e_i and e_j are termed as consecutive edges if t(e_i) = s(e_j).

One of the doubts I have is what type of edge(directed or undirected) should be placed in the Line graph if the consecutive edges (e_i, e_j), either of them is an undirected edge and the other one directed.

For example, edge 13 is a directed edge and edge 15 is undirected so after the transformation, the edge between node 13 and node 15 should be directed or undirected.

Similarly, for edge (2, 4), (2, 1), (16, 3), (5, 8), (5, 9), (11, 12) and (14, 12).

Now, let us consider a restriction from edge 4 to edge 7. We need to find the shortest path from node 2 to node 8.

The shortest path passes through the restriction and Dijkstra fails to find the alternative path in the original graph. We transform the graph. Due to the transformation, multiple sources and destinations are generated. In order to overcome that, a virtual source and virtual destination is created.

Since, there is restriction from edge 4 - > edge 7 in the original graph, we can remove the directed edge from the node 4 to node 7 in the Line graph.

Using Dijkstra, we can now find the shortest alternative path.

The problem arises when the restriction is of length more than 2. For example, Consider the restriction edge 1 - > edge 4 - > edge 7 in original graph. In this case, the directed edge between node 4 and node 7 cannot be removed since the restriction also depends on the directed edge node 1 to node 4.

What can be some other alternative approaches to fix this?