Depending on the size of your graph, you could use the built-in all_pairs_shortest_path
function. Your function would then be basically:
G = nx.DiGraph()
<add some stuff to G>
# Get a random path from the graph
all_paths = nx.all_pairs_shortest_path(G)
# Choose a random source
source = random.choice(all_paths.keys())
# Choose a random target that source can access
target = random.choice(all_paths[source].keys())
# Random path is at
random_path = all_paths[source][target]
There doesn't appear to be a way to just generate the random paths starting at source
that I saw, but the python code is accessible, and adding that feature would be straightforward I think.
Two other possibilities, which might be faster but a little more complicated/manual, would be to use bfs_successors
, which does a breadth-first search, and should only include any target node once in the list. Not 100% sure on the format, so it might not be convenient.
You could also generate bfs_tree
, which generates a subgraph with no cycles to all nodes that it can reach. That might actually be simpler, and probably shorter?
# Get random source from G.node
source = random.choice(G.node)
min_tree = nx.bfs_tree(G, source)
# Accessible nodes are any node in this list, except I need to remove source.
all_accessible = min_tree.node.keys()
all_accessible.remove(source)
target = random.choice(all_accessible.node.keys())
random_path = nx.shortest_path(G, source, target)