Gráfico de dibujo con bordes ponderados

Question

Estoy buscando construir un algoritmo (o reutilizar uno) que organiza nodos y bordes en un lienzo bidimensional donde los bordes pueden tener pesos correspondientes.

Cualquier material de partida e información sería útil.

Answer 1

¿Qué efecto tendrán los pesos en su ubicación en el lienzo?

Dicho esto, es posible que desee examinar graphviz y, más específicamente, el idioma DOT, que organiza los nodos en un lienzo.

Muchos marcos de visualización de gráficos usan una simulación basada en la fuerza, en la que todos los nodos ejercen una fuerza repulsiva (siendo su masa su tamaño) y los bordes ejercen tensión sobre los nodos que conectan. Esto crea visualizaciones gráficas arregladas estéticamente.

Aunque nuevamente, no estoy seguro de dónde quieres que entren los "pesos" de los nodos. ¿Quieres que los nodos con ponderación estén más en el centro? Para ser más grande? ¿Más lejos aparte?

Answer 2

Muchos algoritmos de diseño de gráfico/red son implícitamente capaces de manejar redes ponderadas, pero es posible que tenga que realizar algunos preprocesamientos y ajustes en la implementación para que funcione. Por lo general, el primer paso es determinar si sus pesos representan "similitudes" (generalmente interpretados para significar que los pesos más fuertes deben colocar los nodos más cerca del árbol) o "diferencias" (pesos más fuertes = padre aparte). El caso más común es el primero, por lo que deberá traducirlos a diferencias, a menudo al restar cada valor de borde del máximo valor de borde observado en la red. La matriz de valores de disimilitud para cada borde puede alimentarse al algoritmo e interpretarse como distancias deseadas en el espacio de disposición para cada borde (es decir, "longitudes de resorte"), generalmente después de multiplicar por una constante para transformarlas en unidades de visualización (píxeles) .

Si me dices qué idioma estás utilizando, puedo mostrarte algunos ejemplos de código.