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

Question

我正在尝试模拟一个通过有向网络图的随机遍历。伪代码如下：

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 

除了创建临时列表并在元素被标记为已访问后删除它们之外，还有更有效的将路径标记为已经访问的方法吗？

编辑

该算法的目标是随机选择图中的一个节点。选择该节点的一个随机后继/子节点。如果该节点未被访问，则前往该节点并将其标记为已访问。重复此步骤，直到没有后继/子节点或没有未访问的后继/子节点。

- Linus Liang

---

目标是什么？选择一个随机节点，然后选择它可以访问的另一个随机节点，并提取该路径吗？我的回答是基于这样的假设... - Corley Brigman

感谢您的回复@CorleyBrigman。我已经有了从源代码开始的代码，并且今晚稍后将尝试您的最后一个解决方案！我估计我的节点数量约为十万个。目标是从随机节点开始，随机选择要访问的节点，直到没有更多节点可访问为止。同一节点不应被访问超过一次。我希望运行模拟多次（待确定），并存储每个节点被访问的次数，因此我认为效率将是一个因素。 - Linus Liang

我只是在核对“从随机节点开始并随机选择一个节点”的假设……你的意思是，从一个节点开始，选择一个随机的后继节点，然后选择其中一个节点的后继节点，以此类推，直到到达没有后继节点的节点？ - Corley Brigman

是的，直到我到达一个没有后继节点或所有后继节点都已标记为已访问。 - Linus Liang

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)

- Corley Brigman

---

你为什么从bfs_tree中删除源代码？ - Linus Liang

对于你的上一个解决方案，我不一定想要从一个节点到另一个节点的最短路径。这样会允许真正的随机游走吗？另外，如果我的目标是一个随机选择，比如父节点是源节点，子节点是目标节点。即使目标可能有更多的子节点，我是否只能走一条边？感谢你迄今为止的帮助！ - Linus Liang

bfs_tree 包括源节点和所有可达的目标节点。 DiGraph 的格式是 G.node 是一个字典。 因此， G.node.keys() 是包含源节点和所有目标节点的列表。 要选择一个随机的目标节点，可以使用该列表的 random.choice 函数，但不想要源节点，因此需要将其删除。 - Corley Brigman

你是对的，使用最后一个解决方案，你只会得到那个随机源和目标之间的最短路径。好处是，你已经选择了一个你知道有路径的随机源和目标。但是如果你想要一个真正随机的路径，那么你原来的算法就可以用，我只是会使用集合代替列表——检查成员资格会更便宜。你也可以使用all_simple_paths的方法，这将给出所有没有循环的路径——创建一个列表并选择一个随机条目。这将是相当均匀的随机，但可能不是非常高效的... - Corley Brigman

非常感谢您的帮助！我将切换到使用集合来实现我的原始算法。否则，您的算法效果很好！我只需要一个更均匀的随机行走，以达到“结束”（没有更多的后继或未访问的后继）。 - Linus Liang