10

ノードのすべての K 次隣接ノードのリストを効率的に見つけたい有向グラフがあります。K 次ネイバーは、問題のノードから正確に Kホップで到達できるすべてのノードとして定義されます。

私が見たところnetworkx、関連する唯一の機能はneighbors. ただし、これは順序 1 のネイバーを返すだけです。高次の場合、完全なセットを決定するために反復する必要があります。の K 次近傍にアクセスするより効率的な方法があるはずnetworkxです。

セットをインクリメンタルに構築せずに、K 番目の隣人を効率的に返す関数はありますか?

編集: ここで役立つ可能性のある Python の他のグラフ ライブラリが存在する場合は、それらについて言及してください。

4

5 に答える 5

26

以下を使用できます。 nx.single_source_shortest_path_length(G, node, cutoff=K)

Gグラフ オブジェクトはどこにありますか。

于 2014-01-09T21:43:25.100 に答える
4

NetworkX の場合、おそらく最良の方法は、各 k で近隣のセットを構築することです。コードを投稿していませんが、おそらくすでにこれを行っているようです：

import networkx as nx

def knbrs(G, start, k):
    nbrs = set([start])
    for l in range(k):
        nbrs = set((nbr for n in nbrs for nbr in G[n]))
    return nbrs

if __name__ == '__main__':
    G = nx.gnp_random_graph(50,0.1,directed=True)
    print(knbrs(G, 0, 3))
于 2013-08-24T19:32:29.747 に答える
0

有向グラフがあり、エッジ属性辞書を維持する必要があることを除いて、同様の問題がありました。この相互再帰ソリューションは、必要に応じてエッジ属性ディクショナリを保持します。

def neighbors_n(G, root, n):
    E = nx.DiGraph()

    def n_tree(tree, n_remain):
        neighbors_dict = G[tree]

        for neighbor, relations in neighbors_dict.iteritems():
          E.add_edge(tree, neighbor, rel=relations['rel'])

        #you can use this map if you want to retain functional purity
        #map(lambda neigh_rel: E.add_edge(tree, neigh_rel[0], rel=neigh_rel[1]['rel']), neighbors_dict.iteritems() )

        neighbors = list(neighbors_dict.iterkeys())
        n_forest(neighbors, n_remain= (n_remain - 1))

    def n_forest(forest, n_remain):
        if n_remain <= 0:
            return
        else:
            map(lambda tree: n_tree(tree, n_remain=n_remain), forest)

    n_forest( [root] , n)

    return E
于 2014-01-13T19:55:44.940 に答える