Conteggio nodi non visitati alla distanza n per ogni nodo nel grafico

Per ciascun punto in un grafico di grandi dimensioni, sto cercando di creare un elenco che contenga il numero di nodi non visitati alla distanza n dal nodo iniziale. Un esempio di output è: [1,3,6] che significa che a distanza 0 è il nodo di partenza stessa, ad una distanza 1 ci sono 3 nuovi (inesplorati) nodi, eccConteggio nodi non visitati alla distanza n per ogni nodo nel grafico

Se si ha solo un punto di partenza, questo è abbastanza facile: basta aumentare un contatore di shell in cima a una ricerca in ampiezza. Il problema inizia quando devo farlo per ogni nodo nel mio grafico. Poiché il mio grafico è grande (> 100000 nodi), diventa piuttosto lento eseguire la routine sopra per ogni punto.

Il mio primo tentativo di ottimizzare questo è stato quello di verificare se la lista sul nodo a potesse essere costruita dagli elenchi di tutti i vicini di a, ma finora non ho avuto fortuna, in parte a causa di cicli nel grafico. Spero che alcuni di voi possano avere delle buone idee, magari coinvolgendo alcune informazioni aggiuntive che posso memorizzare nella cache.

La mia domanda: c'è un modo per ottimizzare tale ricerca se si sa che si dovrà fare per il nodo ogni?

fonte

2013-04-09 Ben Ruijl

Il [tutto più breve problema percorsi] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) è fondamentalmente ciò che cercate dopo il raggruppamento dalla distanza e il conteggio, e probabilmente si può fare davvero molto meglio di O (| V |^3). – Nuclearman

La mia ricerca per ampiezza è O (| E |), che è uguale a O (| V |) nel mio caso. Devo farlo per ogni nodo, quindi la mia complessità attuale è O (| V | ²). Ora sto usando il calcolo parallelo per accelerare il processo, ma altri suggerimenti sono i benvenuti! –

Dovrebbe essere ancora O (| V | * | E |), che è O (| V |^3) nel peggiore dei casi. Tuttavia, se stai dicendo che | V | è vicino a | E |, quindi probabilmente non c'è molto di più di quello che puoi fare considerando che ci sono O (| V |^2) possibili combinazioni di vertici per cui dovresti elencare i percorsi più brevi. Sebbene, se la maggior parte dei vertici ha grado 2 o meno, allora può essere pratico elencare semplicemente i percorsi più lunghi (o quelli sufficientemente lunghi) ed estrarre da essi i percorsi più brevi. – Nuclearman

Sembra improbabile che ci sia una soluzione in meno di O(n*|V|^2), quindi ecco un approccio in Python che sembra non troppo terribile.

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

provarlo con 10 nodi e la distanza 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"]

otteniamo

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}

che sembra corretto. Inoltre, l'esecuzione delle topologie semplici per la distanza 100 con 100000 nodi richiede circa un minuto sul mio laptop. Ovviamente se hai un grafico denso (come fullE) questo esploderà.

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

fonte

2015-05-05 22:45:39 mitchus

Conteggio nodi non visitati alla distanza n per ogni nodo nel grafico

risposta

Problemi correlati