¿Alternativa para Graphviz con una mejor ubicación automática de nodos para gráficos grandes?

Lo siento por la decepción. Graphviz podría ser mejor en muchos sentidos, pero en este punto las perspectivas no son muy buenas porque AT&T no está apoyando el trabajo tanto como lo hizo en el pasado y algunos de los autores (como yo) se han ido para buscar otros trabajar. Estamos buscando personas que quieran hacerse cargo, así que háganoslo saber.

También estamos impresionados con yFiles .

Pruebe también el software Tom Sawyer ; tienen mucho talento en ingeniería y trabajaron mucho en métodos de diseño avanzados y herramientas interactivas. (Es posible que deba gastar $$$ ya que la prueba gratuita parece estar descontinuada).

La pregunta no decía qué herramienta u opciones de diseño específicas se probaron o qué tan grande es una red "grande", por lo que no está claro qué sugerir.

Si "grande" significa quizás cientos de nodos, intente neato -Goverlap=false(para evitar la superposición de etiquetas de texto de nodos) y posiblemente -Gmodel=subsetintente una mejor agrupación. (Estas opciones no son las predeterminadas, porque en el análisis de datos, por ejemplo, en bioinformática, una incrustación directa de MDS brinda una representación más precisa de las distancias en la red subyacente).

Si "grande" significa miles de nodos, quizás muchos miles, use sfdpen lugar de neatonuevamente con -Goverlap=false. (El modelo de distancia de subconjunto no está disponible en sfdp, porque no está claro cómo manejar longitudes de borde variables al fusionar bordes en un solucionador jerárquico). Puede ver un buen ejemplo de un gráfico de 1054 nodos aquí

Para "problemas de espacio desperdiciado" en el caso de componentes desconectados, vea también los atributos pack y packmode. Las soluciones a tales problemas no son obvias (básicamente, está tratando de empaquetar formas irregulares de manera óptima, con restricciones adicionales y, a veces, a la escala de lo que la gente considere "grande", por lo que se necesitan algoritmos subcuadráticos). Para gráficos conectados, experimente con -Opciones de superposición.

Esas son las sugerencias. En cuanto a excusas y explicaciones...

Lo que alguien llama el "efecto de avalancha" también se llama inestabilidad de diseño con respecto a cambios (menores) en el gráfico de entrada. Esta es una propiedad de casi todos los programas de diseño de gráficos por lotes y solucionadores de restricciones. Por lo tanto, debe buscar herramientas interactivas como el diseño de incrustación de resorte D3, y Tim Dwyer hizo un gran trabajo en esto cuando estaba en Microsoft, por lo que quizás algún día su kit de herramientas de diseño gráfico (AGL) adopte sus métodos de restricción interactivos. Solo una observación, la mayoría de los investigadores y programadores no han intentado atacar la escala, la interactividad y la estética al mismo tiempo (elija 2 de las anteriores...)

El tema del estilo también es bueno, simplemente no teníamos tiempo/energía para abordarlo, ya que la mayoría de los gráficos se generan automáticamente, por lo que podría aplicar estilos en alguna herramienta de preprocesamiento o secuencia de comandos. También se debe considerar que el gráfico no es solo un árbol de análisis estático, sino que después de leer un gráfico, se puede cambiar su hoja de estilo o los atributos de los objetos a los que se han aplicado los estilos, y luego se debe escribir el gráfico. correctamente de una manera que aún conserve la estructura original tanto como sea posible. No es insuperable, pero estos son detalles que deben pensarse detenidamente.

Los errores se pueden informar en www.graphviz.org en Seguimiento de errores y problemas.

Enrutamiento de borde global con curvas suaves: problema difícil. Tenga en cuenta que muchos diseños atractivos de otras herramientas usan bordes curvos, pero simplemente dibujan sobre todo lo demás que se interpone en el camino. Creo que también agregamos esta característica a graphviz. También creo que había un documento de CHI o INFOVIS que mostraba que los bordes curvos eran un poco más difíciles de leer correctamente que las líneas rectas.

Cruces: es posible que se realice alguna optimización local. No estoy seguro de qué herramienta se está utilizando. Es fácil señalar ejemplos específicos en los que los diseños podrían ser mejores, pero es más difícil inventar una solución efectiva en la que el "número mínimo de cruces" no empeore las cosas en general.

Tenga en cuenta que estoy directamente afiliado a Graphviz.

Mi recomendación de software es " yEd ", una aplicación gratuita de dibujo de gráficos de propósito general que se esfuerza mucho por resolver los problemas con los que te has estado encontrando. Hasta donde yo sé, este software utiliza las mejores implementaciones disponibles gratuitamente de los algoritmos de diseño.

Ahora a la respuesta más detallada que sería más adecuada para StackOverflow que para "Recomendación de software":

El problema que está tratando de resolver es un problema realmente difícil (especialmente en el sentido de computacionalmente difícil ), por lo que es poco probable que encuentre una herramienta que pueda resolver todos sus problemas igualmente bien. Hay una serie de soluciones gratuitas (GraphViz probablemente sea una de las mejores) y una gran cantidad de competidores comerciales. Para la biblioteca comercial de dibujo de gráficos yFiles , hay una aplicación multiplataforma gratuita (como en la cerveza) disponible, que puede probar. Puede importar datos de varios formatos diferentes, aplicar asignaciones de estilo a sus datos y ofrece una gran colección de diferentes algoritmos de diseño. Se llama yEd y se puede ejecutar sin ninguna instalación en una versión web desde aquí. La versión de escritorio se puede iniciar como una aplicación java "webstart" directamente desde el navegador o después de instalar uno de los programas independientes para Windows, Linux y Mac.

Algunos de los algoritmos de diseño probablemente no deberían usarse con gráficos muy grandes (decenas de miles de elementos), porque se ejecutarán durante mucho tiempo o requerirán demasiada memoria, pero la mayoría de las veces hay al menos un estilo de diseño que debe adaptarse bien a sus datos. Si necesita programar contra la API, necesitará licenciar la biblioteca subyacente (disponible para Java, .net, Javascript), lo cual va en contra de su requisito "gratuito", pero esto le daría aún más control sobre el diseño.

Descargo de responsabilidad : trabajo para la empresa que crea este producto (gratuito); sin embargo, en Stack Exchange no represento a mi empleador. He dedicado la mayor parte de mi tiempo académico y profesional al software de dibujo de gráficos desde finales de la década de 1990 y creo que tengo un conocimiento muy profundo sobre el mercado y el software disponible (tanto gratuito como comercial). Puede haber otras herramientas disponibles y espero que este sitio pueda brindar excelentes alternativas; ciertamente no las negaré.

Para responder muy específicamente a la solicitud de la pregunta, ya que las otras dos respuestas hicieron un gran trabajo para expandirse:

Lo que pides no es posible. Desea un programa que proporcione un "gráfico con el mínimo número posible de cruces", y solicitó específicamente que el programa funcione para gráficos grandes.

Sin embargo, determinar el número de cruces de un gráfico es un problema NP-difícil (Garey y Johnson demostraron que es NP-completo en 1983).

Por lo tanto, un programa de este tipo no podrá garantizar encontrar el gráfico con el mínimo número posible de cruces en un tiempo razonable, lo que hace que el programa sea inútil.

Esto ciertamente se consideraría una "solución basada en GraphViz", pero si está trabajando con GraphViz, es posible que desee consultar Gephi . Es mucho más capaz cuando se trata de procesar gráficos grandes.

PlantUML es una herramienta de código abierto que permite a los usuarios crear diagramas UML a partir de un lenguaje de texto sin formato. El lenguaje de PlantUML es un ejemplo de lenguaje específico de aplicación. Utiliza el software Graphviz para diseñar sus diagramas. Se ha utilizado para permitir que los estudiantes ciegos trabajen con UML. PlantUML también ayuda a los ingenieros de software ciegos a diseñar y leer diagramas UML.