Line Graph Approach For dijkstraTRSP

[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 other alternative approaches to fix this?

References:-

1. http://geo.fsv.cvut.cz/gdata/2013/pin2/d/dokumentace/line_graph_teorie.pdf

   As far as I understand, this paper does not talk about more than 2 length edge restrictions.

2. https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation

[woodbri]

I think you need to create some additional connections in the graph to allow the other paths to be completed. Like create a node 4' that allows other incoming nodes to 4 going to 7 to complete.

[vidhan13j07]

@woodbri I didn't get you. Can you elaborate?

[woodbri]

Ok, so my thought is that when you remove the restricted path 1-4-7, that it breaks other valid paths like: 1-4-10, 1-4-8, 1-4-1, 2-4-7, 7-4-7, 8-4-7, 10-4-7, and vs-4-7 so you create a new node 4' and add those paths back in, making sure that the added paths are not also restricted. I probably don't have this totally correct, but take one path as an example: edge 4-7 is removed, but this also breaks paths (2,4,8,10)-4-7 so you create a node 4' and add edges from (2,4,8,10) - 4' - 7

[vidhan13j07]

I have an alternative approach.

Let us take the above example of restriction from edge 1 - > edge 4 - > edge 7 in the original graph.

Now, let us find the shortest path from node 1 - > node 7 in the original graph.

The corresponding Line Graph :-

We'll start from node 1 of edge-based-graph. We can only reach node 1 from here.

We'll also store the previous node from which we have reached to the current node. So, the previous node for node 1 is virtual source node.

From node 1, we can proceed only to the node 4 and assign the value of previous node value of node 4 to be node 1. We'll also check if there is any restriction that ends at node 4 involving the path we have used. Since, we do not have any restriction ending at node 4 so we are good till here.

From node 4, we can proceed to node 7, node 8 or node 10. In case of node 4 - > node 7, we have a turn restriction that ends at node 7 which is node 1 - > node 4 - > node 7, we then check previous node value of node 4 that turns out to be 1 so we can distinguish the path from node 4 - > node 7 as a restricted path. So, we can leave node 7 as is and move to either node 8 or node 10 based on the cost.

So, the valid path can be VS - > node 1 - > node 4 - > node 8 - > node 7 - > node 6 - > VD.

[cvvergara]

More references: https://pdfs.semanticscholar.org/5332/7406b6bbb374142891ae9b546c55cd51344e.pdf https://pdfs.semanticscholar.org/2e95/141eb79dc92869f2f04e0408b23d69215281.pdf https://stackoverflow.com/questions/43655284/boost-graph-library-turn-restrictions-or-turn-penalties

[woodbri]

This is an interesting discussion of the problem by the OSRM team. and it might have some ideas on how we can deal with the same problem in pgRouting. Some of the discussion is involves issues about contraction of the graph, and these can be ignored as we are not currently doing that, but there is discussion on how to add paths to the line graph to deal with these issues. https://github.com/Project-OSRM/osrm-backend/issues/2681