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コードにアクセスでき、その機能を追加するのは簡単だと思います.

他の 2 つの可能性は、より高速ですが、もう少し複雑/手動である可能性がありますbfs_successors。これは、幅優先検索を実行し、ターゲット ノードをリストに 1 回だけ含める必要があります。形式については 100% 確実ではないため、便利ではない可能性があります。

を生成することも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 に答える