is it possible to get networkx dijkstra to avoid certain edges?

I have a problem where I have a directed (or non-directed) non-weighted graph, and I need to find the simple path from s-t. The only complication is that I need to avoid certain nodes that are marked red.

I found the python NetworkX graph library, and found it very fitting. I would like to use either the networkx.dijkstra_path() (or maybe the bfs function which could work as well) to find a shortest path.

In this code, I build a very simple graph, and find a path from s = 0 to t = 4:

import networkx


G = networkx.Graph()

for i in range(5):
    G.add_node(i)

# from zero
G.add_edge(0,1)
G.add_edge(0,3)

# from 1
G.add_edge(1,2)

# from 2
G.add_edge(2,4)

# from 3
G.add_edge(3,4)

path = networkx.dijkstra_path(G, 0, 4)

This network has these nodes: [0, 1, 2, 3, 4] These Edges: [(0, 1), (0, 3), (1, 2), (2, 4), (3, 4)] And the dijkstra gives us this path from 0-4: [0, 3, 4] The graph looks like this visually (made with matplotlib):

But now I would like to be able to say that node 3 was red. So that we would need to avoid it. This would make the shortest path [0,1,2,4]. Is there any way to obstruct node 3 so that dijkstra could avoid it?

Solution

I am not aware of any inbuilt function that can do this. However, you can try the following steps to get the desired result:

Add a node attribute based on which you will filter the nodes while creating the Graph.
Filter the nodes and create a subgraph.

Call the Dijkstra function on the new subgraph

import networkx 

G = networkx.Graph()

#Add an attribute color
for i in range(5):

    if i==3:
        G.add_node(i, color='red')
    else:
        G.add_node(i, color='blue')

# Add edges
G.add_edge(0,1)
G.add_edge(0,3)
G.add_edge(1,2)
G.add_edge(2,4)
G.add_edge(3,4)

# Functin to get filtered subgraph
def get_filtered_graph(G, ignore_attribute, ignore_val):
    # Filter the nodes based on the node attribute and value
    # In this case it is red color
    filtered_nodes = [x for x,y in G.nodes(data=True)
                   if y[ignore_attribute]!=ignore_val]

    # Create the subgraph
    H = G.subgraph(filtered_nodes)
    return H

ignore_attribute ='color'
ignore_val = 'red'
path = networkx.dijkstra_path(get_filtered_graph(G, filter_attribute, filter_val), 0, 4)

print(path)
# [0, 1, 2, 4]

References: