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(ei) be the starting node and t(ei) be the target node of edge ei.
Edges ei and ej are termed as consecutive edges if t(ei) = s(ej).
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 (ei, ej), 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?
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 --- Bcan be converted into two directed edges fromA -- > BandB -- > 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(ei) be the starting node and t(ei) be the target node of edge ei.
Edges ei and ej are termed as consecutive edges if t(ei) = s(ej).
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 (ei, ej), either of them is an undirected edge and the other one directed.
For example,
edge 13is a directed edge andedge 15is undirected so after the transformation, the edge betweennode 13andnode 15should 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 4toedge 7. We need to find the shortest path fromnode 2tonode 8.The shortest path passes through the restriction and
Dijkstrafails 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 7in the original graph, we can remove the directed edge from thenode 4tonode 7in 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 restrictionedge 1 - > edge 4 - > edge 7in original graph. In this case, the directed edge betweennode 4andnode 7cannot be removed since the restriction also depends on the directed edgenode 1tonode 4.What can be some other alternative approaches to fix this?