グラフ内のすべてのノードの距離nの未訪問ノードのカウント

Question

大きなグラフの各ポイントについて、開始ノードから距離nの未訪問ノードの数を含むリストを作成しようとしています。出力例は次のとおり [1,3,6] 距離0から始まるノード自体が存在することを意味し、距離1で3つの新しい（未調査）ノードがある、等

一つだけの出発点を持っている場合、これはかなりあります簡単です：幅優先検索の上にシェルカウンターを追加するだけです。この問題は、グラフ内のすべてのノードでこれを行う必要があるときに開始されます。私のグラフは大きいので（> 100000ノード）、すべてのポイントに対して上記のルーチンを実行するのがむしろ遅くなります。

これを最適化する私の最初の試みは、ノードaのリストがaのすべての近隣のリストから構築できるかどうかをチェックすることでしたが、今まではグラフのサイクルのために運がなかった。あなたの中には良いアイデアがあるかもしれないと思っています。多分、私がキャッシュすることができるいくつかの追加情報を含んでいるかもしれません。

私の質問：ノードごとに行う必要があることがわかったら、そのような検索を最適化する方法はありますか？

Answer 1

答えがO(n*|V|^2)未満であるとは考えにくいので、ここではあまりにもひどいとは思わないPythonのアプローチがあります。

# some basic topologies 
def lineE(N): 
    return(set((i,i+1) for i in range(N-1))) 

def ringE(N): 
    return(lineE(N).union([(0,N-1)])) 

def fullE(N): 
    return(set([(i,j) for i in range(N) for j in range(i)])) 

# propagate visitors from x to y 
def propagate(V, curr, x, y, d): 
    nexty = set() 
    for cx in curr[x]: 
    if not cx in V[y]["seen"]: 
     V[y]["seen"].add(cx) 
     V[y]["foaf"][d] = V[y]["foaf"].get(d,0) + 1 
     nexty.add(cx) 
    return(nexty) 

# run for D iterations 
def mingle(N, E, D): 
    V = dict((i, {"seen":set([i]), "foaf":{0:1}}) for i in range(N)) 
    curr = dict((i, set([i])) for i in range(N)) 
    for d in range(1, min(D+1, N)): 
    next = dict((i, set()) for i in range(N)) 
    for (h, t) in E: 
     next[t] = next[t].union(propagate(V, curr, h, t, d)) 
     next[h] = next[h].union(propagate(V, curr, t, h, d)) 
    curr = next 
    return(V) 

我々は正しいようだ

line 
0 {0: 1, 1: 1, 2: 1, 3: 1} 
1 {0: 1, 1: 2, 2: 1, 3: 1} 
2 {0: 1, 1: 2, 2: 2, 3: 1} 
3 {0: 1, 1: 2, 2: 2, 3: 2} 
4 {0: 1, 1: 2, 2: 2, 3: 2} 
5 {0: 1, 1: 2, 2: 2, 3: 2} 
6 {0: 1, 1: 2, 2: 2, 3: 2} 
7 {0: 1, 1: 2, 2: 2, 3: 1} 
8 {0: 1, 1: 2, 2: 1, 3: 1} 
9 {0: 1, 1: 1, 2: 1, 3: 1} 

ring 
0 {0: 1, 1: 2, 2: 2, 3: 2} 
1 {0: 1, 1: 2, 2: 2, 3: 2} 
2 {0: 1, 1: 2, 2: 2, 3: 2} 
3 {0: 1, 1: 2, 2: 2, 3: 2} 
4 {0: 1, 1: 2, 2: 2, 3: 2} 
5 {0: 1, 1: 2, 2: 2, 3: 2} 
6 {0: 1, 1: 2, 2: 2, 3: 2} 
7 {0: 1, 1: 2, 2: 2, 3: 2} 
8 {0: 1, 1: 2, 2: 2, 3: 2} 
9 {0: 1, 1: 2, 2: 2, 3: 2} 

full 
0 {0: 1, 1: 9} 
1 {0: 1, 1: 9} 
2 {0: 1, 1: 9} 
3 {0: 1, 1: 9} 
4 {0: 1, 1: 9} 
5 {0: 1, 1: 9} 
6 {0: 1, 1: 9} 
7 {0: 1, 1: 9} 
8 {0: 1, 1: 9} 
9 {0: 1, 1: 9} 

を取得し、10のノードとの距離3で

N=10 
D=3 
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N)), ("full", fullE(N))]: 
    V = mingle(N, E, D) 
    print "\n", topology 
    for v in V: 
    print v, V[v]["foaf"] 

をそれをしようとしています。また、距離100の単純なトポロジを100000ノードで実行することは、私のラップトップで約1分かかります。もちろん、密度の高いグラフ（fullEのような）があれば、これは爆発します。

N=100000 
D=100 
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N))]: 
    V = mingle(N, E, D)