Matriz eculidiana 2D a gráfico/plano cartesiano 2D

Question

¿Alguien puede ayudarnos?

Estoy intentando convertir una matriz 2D de distancias en un gráfico 2D.

Por ejemplo, me gustaría pasar de este :

|     A  B  C  D  E  F  G
|  A  -  2  2  5  1  3  5
|  B     -  2  4  4  2  1
|  C        -  1  2  4  8
|  D           -  4  5  3
|  E              -  1  2
|  F                 -  1
|  G                    -

A esto (enlace a la imagen) : http://i.stack.imgur.com/j8Moa.png

Para mostrar este ejemplo, he utilizado photoshop y GraphViz

graph G { node [shape=circle,height=.2,width=.2]; a -- b [len=2,label="2"]; a -- c [len=2,label="2"]; a -- d [len=5,label="5"]; a -- e [len=1,label="1"]; a -- f [len=3,label="3"]; a -- g [len=5,label="5"]; b -- c [len=2,label="2"]; b -- d [len=4,label="4"]; b -- e [len=4,label="4"]; b -- f [len=2,label="2"]; b -- g [len=1,label="1"]; c -- d [len=1,label="1"]; c -- e [len=2,label="2"]; c -- f [len=4,label="4"]; c -- g [len=8,label="8"]; d -- e [len=4,label="4"]; d -- f [len=5,label="5"]; d -- g [len=3,label="3"]; e -- f [len=1,label="1"]; e -- g [len=2,label="2"]; f -- g [len=1,label="1"]; }

¿Alguien conoce una manera fácil de hacerlo?

Me gustaría hacerlo bajo mathlab o java.

Muchas gracias.

Referencias :

• Crear un gráfico a partir de un conjunto de distancias
• http://albertomurta.wikispaces.com/file/view/coordinates_from_distances.pdf
• https://stackoverflow.com/questions/13513455/drawing-a-graph-or-a-network-from-a-distance-matrix

Answer 1

Si te dan distancias entre cada par de nodos, entonces su problema está seriamente sobredeterminado, y es poco probable que haya una solución en absoluto a menos que los datos de entrada tengan propiedades muy especiales.

Para los datos de ejemplo que muestras, las distancias entre A, B y G son 2, 5 y 1, lo que viola la desigualdad del triángulo, así que ya tienes una imposibilidad entre manos.

Si tienes distancias que crees que admiten una solución, puedes utilizar un algoritmo ingenuo punto por punto:

1. Empieza por colocar los dos primeros puntos $A$ y $B$ horizontalmente uno al lado del otro en el $x$ eje con la distancia adecuada.

2. Para cada nuevo punto, mira sus distancias conocidas a $A$ y $B$ . Utiliza la fórmula de la distancia $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ para obtener dos ecuaciones para las coordenadas de $P$ . Eleva al cuadrado cada lado de cada ecuación para deshacerte de las raíces cuadradas, y resta las ecuaciones entre sí para deshacerte de las raíces cuadradas. $x_P^2$ y $y_P^2$ términos. Observando que $y_A$ y $y_B$ son ambos $0$ y $x_A$ y $x_B$ son ambas conocidas, se obtiene una ecuación lineal en $x_P$ que se resuelve fácilmente.

3. Ahora puede encontrar $y_P$ hasta su signo, por el teorema de Pitágoras dada la distancia $AB$ . Si este es el primer punto con un valor distinto de cero $y$ que coloque, seleccione el signo de su $y$ arbitrariamente; si no, calcula las distancias entre las dos posiciones posibles y un punto que ya hayas colocado fuera del eje y elige la posición que mejor se ajuste a tus datos.