Algoritmo di disegno del grafico a forza diretta a un passaggio

Question

Sto cercando un algoritmo one-pass (o idee su come scriverlo da solo) in grado di calcolare le coordinate tridimensionali per un grafico diretto non ponderato. Gli unici metadati dei vertici sono titolo e categoria.

Ho bisogno di implementare questo algoritmo in modo che i vertici possano essere aggiunti/rimossi senza ricalcolare l'intera struttura del grafico.

Questo algoritmo deve essere applicato a un set di dati di grandi dimensioni (5gb) che cambia continuamente.

Le mie competenze di Google mi hanno portato ad algoritmi di n-pass che non sono quello che sto cercando.

Answer 1

Immagino che la tua domanda potrebbe essere ancora un problema aperto. Conosco un progetto di ricerca chiamato Tulip (http://tulip.labri.fr/TulipDrupal/) che è un visualizzatore di grafici (su larga scala). Un documento sul metodo è disponibile allo http://dept-info.labri.fr/~auber/documents/publi/auberChapterTulipGDSBook.pdf e sicuramente è possibile trovare più algoritmi che sfogliano la pagina web personale di D. Auber e dei suoi colleghi.

Answer 2

C'è una questione connessa qui:

https://cstheory.stackexchange.com/questions/11889/an-algorithm-to-efficiently-draw-a-extremely-large-graph-in-real-time

La risposta superiore ha un certo numero di carte che potrebbero essere di interesse. Penso che una delle chiavi del problema sia provare e ricalcolare la posizione di una quantità ridotta di nodi nel tuo grafico.