How to restrict certain paths in NetworkX graphs?

Question

I am trying to calculate shortest path between 2 points using Dijkstra and A Star algorithms (in a directed NetworkX graph).

At the moment it works fine and I can see the calculated path but I would like to find a way of restricting certain paths.

For example if we have following nodes:

nodes = [1,2,3,4]

With these edges:

edges = ( (1,2),(2,3),(3,4) )

Is there a way of blocking/restricting 1 -> 2 -> 3 but still allow 2 -> 3 & 1 -> 2.

This would mean that:

• can travel from 1 to 2

• can travel from 2 to 3

• cannot travel from 1 to 3 .. directly or indirectly (i.e. restrict 1->2->3 path).

Can this be achieved in NetworkX.. if not is there another graph library in Python that would allow this ?

Thanks.

Answer 1

Interesting question, I never heard of this problem, probably because I don't have much background in this topic, nor much experience with NetworkX. However, I do have a idea for a algorithm. This may just be the most naive way to do this and I'd be glad to hear of a cleverer algorithm.

The idea is that you can use your restriction rules to transform you graph to a new graph where all edges are valid, using the following algorithm.

The restriction of path (1,2,3) can be split in two rules:

• If you came over (1,2) then remove (2,3)
• If you leave over (2,3) then remove (1,2)

To put this in the graph you can insert copies of node 2 for each case. I'll call the new nodes 1_2 and 2_3 after the valid edge in the respective case. For both nodes, you copy all incoming and outgoing edges minus the restricted edge.

For example:

Nodes = [1,2,3,4]
Edges = [(1,2),(2,3),(4,2)]

The valid path shall only be 4->2->3 not 1->2->3. So we expand the graph:

Nodes = [1,1_2,2_3,3,4] # insert the two states of 2
Edges = [ # first case: no (1_2,3) because of the restriction 
          (1,1_2), (4, 1_2)
          # 2nd case, no (1,2_3)
          (2_3,3), (4,2_3)]

The only valid path in this graph is 4->2_3->3. This simply maps to 4->2->3 in the original graph.

I hope this answer can at least help you if you find no existing solution. Longer restriction rules would blow up the graph with a exponentially growing number of state nodes, so either this algorithm is too simple, or the problem is hard ;-)