How to restrict or block 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?

Answer 1

The add_edge method of a Graph in NetworkX takes a weight as an attribute. This is a proxy for traversal restriction. If the weight specified is high, then traversal algorithms will avoid that route. For example:

import networkx as nx

G=nx.Graph()

G.add_edge('a','b',weight=0.6)
G.add_edge('b','c',weight=0.2)
G.add_edge('c','d',weight=999) # this one is restricted
G.add_edge('a','d',weight=0.7)

At first glance your example of disallowing routing from 1 -> 2 -> 3 seemed odd. However, this makes good sense if we want to restrict "short cuts". Say we had a graph G representing the floor plan of a building with rooms and hallways. Vertices V represent turn decision points, and edges E represent paths between decision points. An office with two doors and a hallway on either side might provide a quick route from one hallway to the other, but unless it's your office it is not cool to just cut through. In this case the semantics of our graph G(V,E) are too limited - even when adding edge weights.

So, the answer to you question is no, the native graph representations in NetworkX can't handle this scenario. But you could implement a calculus like Milner's bigraph model. This could be done by extending the adjacency relations of NetworkX to include hyperlinks and access semantics.