3

我正在尝试通过有向 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

除了创建临时列表并删除元素（如果它们被标记为已访问）之外，是否有更有效的方法将路径标记为已行驶？

编辑

该算法的目标是在图中随机选择一个节点。选择该节点的随机后继/子节点。如果它未被访问，请到那里并将其标记为已访问。重复直到没有继任者/孩子或没有未访问的继任者/孩子

4

1 回答 1

4

根据图表的大小，您可以使用内置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，它进行广度优先搜索，并且应该只在列表中包含任何目标节点一次。不是 100% 确定格式，所以可能不方便。

您还可以 generate 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)
于 2014-03-03T15:39:26.460 回答