CODEWITHSUNDEEP
pythonnetworkxgraph-theory
Sven the Mediocre
Sven the Mediocre

Reputation: 125

Possible to determine if a given node will always be visited in a directed graph?

I'm working on a problem where I have a bunch of directed graphs with a single source/sink for each and the edges are probabilistic connections (albeit with 90% of the nodes having only 1 input and 1 output). There also is a critical node in each graph and I'd like to determine if there is any way to traverse the graph that bypasses this node. Ideally I'd also like to enumerate the specific paths which would bypass this node. I've been able to import an example graph into NetworkX and can run some of the functions on the graph without difficulty, but I'm not sure if what I'm looking for is a common request and I just don't know the right terminology to find it in the help files, or if this is something I'll need to code by hand. I'm also open to alternative tools or methods.

Upvotes: 2

Views: 247

Answers (1)

bart cubrich
bart cubrich

Reputation: 1254

First, you might want some way to quantify critical nodes. For that you can use some measure of centrality, probably betweenness centrality in your case. Read more here.

Next, if you know the two nodes you want to travel between you can use this as a kind of psuedocode to help you get there. You can also loop through all possible pairs of nodes that could be traveled through, but that might take a while.

import NetworkX as nx
important_nodes=[]#list of important nodes    
paths = nx.all_simple_paths(G, source, target)
paths=list(paths)
#This is pseudocode, next four lines could be done with list comprehension
exclusive_paths=[]
for path in paths:
    if important_nodes not in path:
        exclusive_paths.append(path)

Read more on all_simple_paths here.

list comprehension might look like this

exclusive_paths=[x for x in paths if important_nodes not in x]

Upvotes: 1

Related Questions