Libreria Java per la memorizzazione e l'elaborazione di grafici di grandi dimensioni (fino a 600k vertici)

Question

Sto lavorando a un progetto che prevede l'esecuzione di algoritmi su grafici di grandi dimensioni. I due più grandi hanno circa 300k e 600k di vertici (penso che siano piuttosto scarni). Spero di trovare una libreria java in grado di gestire grafici di grandi dimensioni e anche alberi di dimensioni leggermente inferiori, poiché uno degli algoritmi che utilizzerò prevede la scomposizione di un grafico in un albero. Idealmente, la libreria includerebbe anche la prima ricerca di ampiezza e gli algoritmi di Dijkstra o altri percorsi più brevi.

Sulla base di another question, ho cercato in alcune librerie (JGraphT, JUNG, jdsl, yworks) ma sto avendo difficoltà a trovare quanti vertici possono realisticamente gestire. Guardando la loro documentazione, tutto quello che ho trovato è stato un po 'nello JUNG FAQ che diceva che poteva facilmente gestire grafici di oltre 150k vertici, che è ancora un po' più piccolo dei miei grafici ... Spero che qualcuno qui ne abbia usato uno o più di queste librerie e può dirmi se gestirà le dimensioni del grafico che mi servono, o se c'è qualche altra libreria che sarebbe meglio.

Per la cronaca non ho bisogno di strumenti di visualizzazione; si tratta rigorosamente di rappresentare i grafici e gli alberi in strutture dati e algoritmi in esecuzione su di essi.

Contesto se qualcuno si preoccupa veramente: per una lezione dovrei implementare un algoritmo descritto in un documento di ricerca, e far correre gli esperimenti sulla carta nel miglior modo possibile. La carta e i set di dati che utilizzerò possono essere trovati here. Il mio professore dice che posso usare qualsiasi libreria che riesca a trovare finché posso dire quale sia la complessità tempo/spazio degli algoritmi/strutture dati.

Answer 1

Si dovrebbe dare un'occhiata a Neo4J che è un database grafico che potrebbe essere una buona soluzione per i vostri problemi.

Answer 2

Checkout JGraph pure. Tuttavia è orientato alla visualizzazione.

Inoltre, forse Apache Hama - un framework di calcolo distribuito per massicci calcoli scientifici, ad esempio algoritmi a matrice, grafico e di rete.

Annas può anche interessare - framework open-source Java che è stato costruito per gli sviluppatori e ricercatori nel campo della teoria dei grafi - AI, Percorso trovare, sistemi distribuiti, ecc

Answer 3

Cassovary https://github.com/twitter/cassovary -project da Twitter può gestire grafici molto grandi con Scala (quindi JVM) in memoria.

alternativa, versione Java di GraphChi può gestire grafici ancora più grandi, utilizzando disk: http://code.google.com/p/graphchi-java/

Tuttavia, GraphChi non sarà efficace per algoritmi di tipo esatto cammini minimi, in quanto richiedono rapido accesso casuale.