Nicht besuchte Knoten im Abstand n für jeden Knoten im Diagramm zählen

Question

Für jeden Punkt in einem großen Diagramm versuche ich eine Liste zu erstellen, die die Anzahl der nicht besuchten Knoten im Abstand n vom Startknoten enthält. Ein Beispiel Ausgang ist: [1,3,6] , die im Abstand 0 Es ist der Ausgangsknoten selbst auf Distanz 1 gibt es 3 neue (unerforschten) Knoten usw.

Wenn nur ein Ausgangspunkt haben, ist dies ziemlich bedeutet, dass Ganz einfach: Sie erweitern einfach einen Shell-Counter über die erste Suche. Das Problem beginnt, wenn ich dies für jeden Knoten in meinem Diagramm tun muss. Da mein Graph groß ist (> 100000 Knoten), wird es ziemlich langsam, die obige Routine für jeden Punkt auszuführen.

Mein erster Versuch, dies zu optimieren, war zu überprüfen, ob die Liste am Knoten a aus den Listen aller Nachbarn von a konstruiert werden konnte, aber bisher hatte ich kein Glück, teilweise aufgrund von Zyklen in der Grafik. Ich hoffe, dass einige von euch vielleicht ein paar nette Ideen haben, vielleicht mit ein paar zusätzlichen Informationen, die ich zwischenspeichern kann.

Meine Frage: Gibt es eine Möglichkeit, eine solche Suche zu optimieren, wenn Sie wissen, dass Sie es für jeden Knoten tun müssen?

Answer 1

Es scheint unwahrscheinlich, dass es eine Lösung in weniger als O(n*|V|^2) gibt, also hier ist ein Ansatz in Python, der nicht zu schrecklich scheint.

# 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) 

Der Versuch, es mit 10 Knoten und Entfernung aus 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"] 

wir

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} 

bekommen, die richtige zu sein scheint. Außerdem dauert das Ausführen der einfachen Topologien für die Entfernung 100 mit 100000 Knoten ungefähr eine Minute auf meinem Laptop. Natürlich, wenn Sie einen dichten Graph haben (wie fullE), wird dies explodieren.

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