Algoritmo per la ricerca dei vicini vicini di un grafico diretto

Question

Algoritmo per la ricerca dei vicini vicini di un grafico diretto

#1 da (2 voti)
#2 da (1 voti)

0

Esiste un algoritmo per cercare un grafico (albero) orientato per il suo vicino di casa?

La mia attuale soluzione brute-force funziona come segue:

for each node n:
   for each child c of n
      for each parent p of c
         if (p != n)
           insert edge (p,n)

Ho a che fare con ca. 700.000 nodi ciascuno con un margine compreso tra 1 e 1000 e attualmente sto affrontando tempi di esecuzione troppo lunghi: il che è dovuto principalmente al motivo per cui eseguo questo algoritmo su un database grafico, poiché richiederebbe troppa memoria.

performance algorithms graph-traversal

posta platzhirsch 07.12.2011 - 10:54

fonte

2 risposte

1

Prova a sottrarre:

surroundings = list[]

for each node p
  for each child c1 of p
    for each child c2 of c1
      if c2 not in surroundings
        surroundings->add(c2) # Add everything, don't mind if it's on the border or inside.
    if c1 in surroundings
      surroundings->remove(c1) # Remove what's not on the border.
  if p in surroundings
    surroundings->remove(p) # Remove the initial node.

for each node border in list
  # Do whatever you want.

Mi dispiace, non penso che troverai qualcosa di più piccolo di un algoritmo in O (n³).

risposta data 07.12.2011 - 12:13

fonte

Leggi altre domande sui tag performance algorithms graph-traversal

Quando terminerà il tuo progetto? Quanto ci vuole per completarlo? Qualche idea su come valuti tale tempistica sul posto? [duplicare] Architettando una soluzione multi-tecnologia

score 2 · Accepted Answer

Le parole "per ogni bambino" e "per ogni genitore" sono altrettanto veloci? Se "per ciascun genitore" è più lento, prova questo:

for each node p
  for each child c1 of p
     for each child c2 of p
       if (c1 != c2)
         insert edge (c1,c2)

EDIT: la versione precedente crea un risultato diverso, un elenco di fratelli. Ora per un altro approccio ...

for each node c
  ps:=c.parents()   
  for each p1 in ps
     for each p2 in ps
       if (p1 != p2)
         insert edge (p1,p2)