Biblioteca de Java para almacenar y procesar gráficos grandes (hasta 600k vértices)

Estoy trabajando en un proyecto que implicará ejecutar algoritmos en gráficos grandes. Los dos más grandes tienen alrededor de 300k y 600k vértices (bastante escaso, creo). Espero encontrar una biblioteca de Java que pueda manejar gráficos tan grandes, y también árboles de un tamaño algo más pequeño, ya que uno de los algoritmos que utilizaré implica descomponer un gráfico en un árbol. Idealmente, la biblioteca también incluiría la primera búsqueda de amplitud y los algoritmos de Dijkstra u otros algoritmos de ruta más corta.Biblioteca de Java para almacenar y procesar gráficos grandes (hasta 600k vértices)

Basado en another question, yo he estado mirando algunas bibliotecas (JGraphT, JUNG, jdsl, yworks) pero estoy teniendo dificultades para encontrar cuántos vértices que pueden manejar de forma realista. Mirando su documentación, todo lo que pude encontrar estaba un poco en el JUNG FAQ que decía que podría manejar fácilmente gráficos de más de 150k vértices, que aún es bastante más pequeño que mis gráficos ... Espero que alguien aquí haya usado uno o más de estas bibliotecas y puede decirme si manejará los tamaños de gráfico que necesito, o si hay alguna otra biblioteca que sería mejor.

Para el registro no necesito ninguna herramienta de visualización; esto se trata estrictamente de representar los gráficos y árboles en estructuras de datos y ejecutar algoritmos sobre ellos.

Antecedentes si a alguien realmente le importa: para una clase se supone que debo implementar un algoritmo descrito en un trabajo de investigación, y ejecutar los experimentos en el papel lo mejor que pueda. El papel y los conjuntos de datos que utilizaré se pueden encontrar en here. Mi profesor dice que puedo usar cualquier biblioteca que pueda encontrar, siempre y cuando sepa cuál es la complejidad de tiempo/espacio de los algoritmos/estructuras de datos.

Fuente

2012-03-29 Maltiriel

Acabo de encontrar información sobre [JGraphT] (http://jgrapht-users.107614.n3.nabble.com/Max-limit-of-vertices-td1194057.html). Aparentemente debería manejar estos gráficos sin problema ... – Maltiriel

Debe echar un vistazo a Neo4J que es una base de datos gráfica que podría ser una buena solución para sus problemas.

Fuente

2012-03-29 17:40:16 khmarbaise

Gracias, estoy investigando esto ahora. Definitivamente puede manejar esos conjuntos de datos. – Maltiriel

Primero voy a probar una de las bibliotecas en memoria, ya que eso es lo que se hace en el documento, así que creo que a mi profesor le gustaría algo mejor, pero si eso no funciona, iré con Neo4J. Parece fácil de usar y tiene todos los algoritmos que necesito. ¡Gracias por la sugerencia! – Maltiriel

Pago JGraph también. Sin embargo, está orientado hacia la visualización.

También, tal vez Apache Hama - un marco informático distribuido para cálculos científicos masivos, por ejemplo, algoritmos de matriz, gráfico y red.

Annas También pueden interesarle - de código abierto marco de Java que fue construida para los desarrolladores e investigadores en el campo de la teoría de grafos - AI, Ruta de búsqueda, sistemas distribuidos, etc.

Fuente

2012-03-29 17:42:56 tenorsax

Hmm. La información que he visto hace que parezca que esto no sería tan adecuado ... En el manual del usuario comienzan por hablar de columpio, por ejemplo. No quiero tener que meterme con la visualización en absoluto. Es posible, ¿sabes? – Maltiriel

@Maltiriel, podría trabajar en el modelo de gráfico independiente. Sin embargo, si no necesita visualizar el gráfico, es una exageración. – tenorsax

Gracias por las sugerencias adicionales. Hama puede ser demasiado para lo que estoy haciendo, pero Annas se ve muy interesante. No he encontrado ninguna de mis búsquedas antes de esto. – Maltiriel

Cassovary https://github.com/twitter/cassovary -project de Twitter puede maneja gráficos muy grandes con Scala (así JVM) en la memoria.

Como alternativa, la versión Java de GraphChi puede manejar gráficos aún más grandes, mediante el uso de disco: http://code.google.com/p/graphchi-java/

Sin embargo, GraphChi no será eficaz para los algoritmos de tipo exacta la ruta más corta, ya que requieren acceso aleatorio rápido.

Fuente

2012-08-24 22:20:14

Biblioteca de Java para almacenar y procesar gráficos grandes (hasta 600k vértices)

Respuesta

Cuestiones relacionadas