tutorial online nodesep example compiler graph graphviz dot directed-graph

online - graphviz tutorial



Algoritmo de puntos Graphviz (1)

Aquí hay algunas referencias para ti. El más completo (a excepción del código fuente en sí) es probablemente el n.º 2, el documento "Una técnica para dibujar gráficos dirigidos", escrito por varios de los colaboradores de Graphiz.

(1) "Dibujar gráficos con punto"

En Dibujo de gráficos con punto , el algoritmo de diseño de punto se describe así:

dot dibuja gráficos en cuatro fases principales. Saber esto te ayuda a comprender qué tipo de diseños hace dot y cómo puedes controlarlos. El procedimiento de disposición utilizado por punto se basa en que el gráfico es acíclico. Por lo tanto, el primer paso es romper cualquier ciclo que ocurra en el gráfico de entrada al invertir la dirección interna de ciertos bordes cíclicos. El siguiente paso asigna nodos a rangos o niveles discretos. En un dibujo de arriba a abajo, los rangos determinan las coordenadas Y. Los bordes que abarcan más de un rango se dividen en cadenas de nodos "virtuales" y bordes de longitud de unidad. El tercer paso ordena nodos dentro de rangos para evitar cruces. El cuarto paso establece las coordenadas X de los nodos para mantener los bordes cortos, y el último paso dirige las estrías de los bordes. Este es el mismo enfoque general que la mayoría de los programas de dibujo de gráficos jerárquicos, basados ​​en el trabajo de Warfield [War77], Carpano [Car80] y Sugiyama [STT81]. Remitimos al lector a [GKNV93] para una explicación detallada de los algoritmos de punto

Los documentos citados en ese párrafo son estos:

  • [Car80] M. Carpano. Visualización automática de gráficos jerarquizados para el análisis de decisiones asistido por computadora. Transacciones IEEE en Ingeniería de Software, SE-12 (4): 538-546, abril de 1980. (Evidentemente disponible para comprar aquí ).

  • [GKNV93] Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North y Kiem-Phong Vo. Una técnica para dibujar gráficos dirigidos. IEEE Trans. Sofware Eng., 19 (3): 214-230, mayo de 1993. (Disponible aquí en el sitio Graphviz.org).

  • [STT81] K. Sugiyama, S. Tagawa y M. Toda. Métodos para la comprensión visual de las estructuras del sistema jerárquico. Transacciones IEEE en sistemas, hombre y cibernética, SMC-11 (2): 109-125, febrero de 1981. (Evidentemente disponible para comprar aquí ).

  • [War77] John Warfield. Teoría de cruce y mapeo de jerarquía. IEEE Transactions on Systems, Man and Cybernetics, SMC-7 (7): 505-523, julio de 1977. (Evidentemente disponible para comprar aquí ).

(2) "Una técnica para dibujar gráficos dirigidos"

El algoritmo de dot se describe en detalle en el documento "Una técnica para gráficos dirigidos al dibujo" , publicado en la revista IEEE Transactions on Software Engineering en 1993 (y disponible de forma gratuita en el sitio Graphviz.org). Esta es la fuente "[GKNV93]" citada anteriormente.

El resumen, por lo que vale, es este:

Describimos un algoritmo de cuatro pasadas para dibujar gráficos dirigidos. El primer pase encuentra una asignación de rango óptima usando un algoritmo simplex de red. El segundo paso establece el orden de los vértices dentro de los rangos mediante una heurística iterativa que incorpora una nueva función de ponderación y transposiciones locales para reducir los cruces. El tercer pase encuentra las coordenadas óptimas para los nodos al construir y clasificar un gráfico auxiliar. El cuarto pase crea splines para dibujar bordes. El algoritmo hace buenos dibujos y corre rápido.

(3) "Usar Graphviz como una biblioteca"

"Usar Graphviz como una biblioteca" proporciona un resumen de los algoritmos de cada motor de diseño en la Sección 3.1. Parte de la descripción para dot es esta:

El algoritmo de puntos produce un diseño ordenado de un gráfico que respeta las direcciones de los bordes si es posible. Es particularmente apropiado para mostrar jerarquías o gráficos acíclicos dirigidos. El esquema de diseño básico se atribuye a Sugiyama et al. [STT81] El algoritmo específico utilizado por punto sigue los pasos descritos por Gansner et al. [GKNV93]

Los pasos en el diseño de puntos son: 1) inicializar 2) rango 3) minicross 4) posición 5) puertos iguales 6) splines 7) compoundEdges

Después de la inicialización, el algoritmo asigna a cada nodo un rango discreto (rango) usando un programa entero para minimizar la suma de las longitudes de borde (discretas). El siguiente paso (mincross) reorganiza los nodos dentro de los rangos para reducir los cruces de borde. Esto es seguido por la asignación (posición) de las coordenadas reales a los nodos, usando otro programa entero para compactar el gráfico y enderezar los bordes. En este punto, todos los nodos tendrán una posición establecida en el atributo coord. Además, se establece el atributo bb del cuadro delimitador de todos los clústeres.

La referencia "[GKNV93]" es "Una técnica para dibujar gráficos dirigidos", como se relacionó anteriormente.

La referencia "[STT81]" es a "Métodos para la comprensión visual de las estructuras del sistema jerárquico" como se citó anteriormente.

(4) También podría estar interesado en:

¿Hay alguna documentación (pseudo código completo) sobre el algoritmo de punto dentro de la Biblioteca Graphviz?

Solo encontré documentación parcial de pseudo código.