使用Networkx更高效地运行有向图的随机遍历方法

Question

我正在尝试在一个有向的networkx图中模拟随机遍历。下面是伪代码：

Create graph G with nodes holding the value true or false. 
// true -> visited, false -> not visited

pick random node N from G
save N.successors as templist
while true
    nooptions = false
    pick random node N from templist
    while N from templist has been visited
        remove N from templist
        pick random node N from templist
        if templist is empty
            nooptions = true
            break
    if nooptions = true 
        break
    save N.successors as templist 

有没有更有效的方法来标记一条路径为已走过，而不是创建一个临时列表，并在标记为已访问时将元素移除呢？

编辑

这个算法的目标是随机选择图中的一个节点。然后随机选择这个节点的一个后继/子节点。如果这个子节点还没有被访问过，就去那里并标记为已访问。这个过程会一直重复，直到没有后继/子节点，或者所有的后继/子节点都已经被访问过。

Answer 1

根据你的图的大小，你可以使用内置的 all_pairs_shortest_path 函数。你的函数基本上会是这样的：

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]

我没有找到一种方法可以直接生成从 source 开始的随机路径，不过 Python 代码是可以访问的，我觉得加上这个功能应该不难。

还有另外两种可能的方法，可能会更快，但稍微复杂一些，需要手动操作。第一种是使用 bfs_successors，它会进行广度优先搜索，并且在列表中只会包含每个目标节点一次。我对格式不是很确定，所以可能不太方便。

你还可以生成 bfs_tree，它会生成一个没有循环的子图，包含所有可以到达的节点。这样做可能实际上更简单，而且可能路径会更短？

# 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)