27 replies to this topic

[JoAnCa]

Hola a todos
Pues me han mandado un ejercicio en la Universidad de hacer un software que me grafique un grafo mostrando en un color resaltado la ruta mas corta

Inicialmente para introducir los datos se me ocurre hacer una tabla (matriz) con cada nodo en las filas y columnas, y donde se crucen poner el peso del arco
Para resolver el camino mas corto lo haré segun las iteraciones como se hacen a lapiz en las conferencias

Pero el problema está en como llevarlo a un grafico, dibujar los nodos y sus enlaces

Se tienen como datos el nodo inicial, el final y la cantidad de nodos, ademas del peso de los arcos
El software debe servir para cualquier cantidad de nodos

[Delphius]

Hola JoAnCa,
Por el tema estético quizá puedas inspirarte o tomar como base un ejemplo práctico del uso de TShape que el buen mestro Seoane elaboró. 

Respecto al aspecto lógico y la implementación del algoritmo tengo entendido que se resuelve con el algoritmo de Dijkstra.
En los libros de estructuras de datos y algoritmos es posible que encuentres más información al respecto. Por mi parte recomiendo la lectura al libro de Aho y otros aunque recomiendo que acudas a la biblioteca de tu universidad y revises primero las fuentes bibliográficas que ha dado tu profesor.

Saludos,

[jorgeu]

hace aaaaaaaaaaaaaños cuando estudié esto a u compañero se le ocurrió mostrar los nodos en dos columnas donde facilmente podian hacerse lineas entre ellos. (disculpen lo horrible del dibujo de ejemplo)



Uploaded with ImageShack.us

[jorgeu]

Los algoritmos:

El algoritmo de Dijkstra es el más rápido si no hay ciclos absorvente. Esto es que no hay un ciclo cuya suma de pesos es negativa. Da camino más corto desde un nodo al resto. http://es.wikipedia....tmo_de_Dijkstra

El de bellman-ford es más tolerante a pesos negativos y también calcula camino más corto desde un nodo al resto http://es.wikipedia....de_Bellman-Ford

Suerte

[JoAnCa]

Gracias por sus respuestas
Ya estoy estudiando los algoritmos, ya me da la idea de como resolverlo por la parte logica, ya veré como me sale la implementacion

La otra parte, la de graficarlo, es la que no se me ocurre nada todavía
Trate de descargar el ejemplo de seoane que me indico delphius, pero me da error el archivo, tengo que esperar a ver si lo sube de nuevo

[jorgeu]

La otra parte, la de graficarlo, es la que no se me ocurre nada todavía

¿se entendió la idea que te di de nodos en dos columnas?
una vez lo entiendas y veas un par de ejemplos de TShape seguro te sale

[JoAnCa]

¿se entendió la idea que te di de nodos en dos columnas?
una vez lo  entiendas y veas un par de ejemplos de TShape seguro te sale

Mas o menos entendi algo, pero no ilustra bien el resultado, pues tiende a confundir, lo mas correcto seria dibujarlo como se ilustra en al algoritmo de Dijkstra, señalando en un color diferente la ruta mas corta                   

Attached Files

•  1913_4d2f0c4a48403166752c16d52e7eb68c48464c7d.gif   8.55KB   1 downloads

[Delphius]

Los algoritmos:

El algoritmo de Dijkstra es el más rápido si no hay ciclos absorvente. Esto es que no hay un ciclo cuya suma de pesos es negativa. Da camino más corto desde un nodo al resto. http://es.wikipedia....tmo_de_Dijkstra

El de bellman-ford es más tolerante a pesos negativos y también calcula camino más corto desde un nodo al resto http://es.wikipedia....de_Bellman-Ford

Suerte

Hola,

He aprendido algo nuevo  ... desconocía el algoritmo de Bellman-Ford... al menos no recuerdo haberlo estudiado en cátedra de Estructura de datos y Algoritmos cuando vimos el tema de grafos.

Saludos,

[jorgeu]

¿se entendió la idea que te di de nodos en dos columnas?
una vez lo  entiendas y veas un par de ejemplos de TShape seguro te sale

Mas o menos entendi algo, pero no ilustra bien el resultado, pues tiende a confundir, lo mas correcto seria dibujarlo como se ilustra en al algoritmo de Dijkstra, señalando en un color diferente la ruta mas corta                 

Supongo asumes que los colocarás en posiciones aleatorias y luego harás las líneas.
Te cuento que acomodar los nodos de manera que las líneas no se intercepten es un problema NP-Completo de alta complejidad. No recomendado meterse con eso.

[JoAnCa]

Supongo asumes que los colocarás en posiciones aleatorias y luego harás  las líneas.

En realidad, las posiciones no son tan aleatorias que digamos, y lo de cruzarse las líneas, parece que me va a ser inevitable

La idea que se me ocurre es poner el primer nodo (origen) al inicio del grafo, y el último nodo (destino), al final del grafo

Despues, en dependencia de la cantidad de nodos, calcular la cantidad de filas y columnas para los nodos intermedios, ubicandolos que no queden tan alineados en las filas para que los arcos no pasen por encima de los nodos que le queden en el trayecto

Mas o menos esa es la idea que se me ocurrió 
Lo que no se me ha ocurrido todavía es como implementar eso 

[jorgeu]

La idea que se me ocurre es poner el primer nodo (origen) al inicio del grafo, y el último nodo (destino), al final del grafo

Despues, en dependencia de la cantidad de nodos, calcular la cantidad de filas y columnas para los nodos intermedios, ubicandolos que no queden tan alineados en las filas para que los arcos no pasen por encima de los nodos que le queden en el trayecto

Te recuerdo el conjunto de nodos es un conjunto y por lo tanto no hay un orden establecido. Estás pensando en grafos de libro de texto que se escriben de izquierda a derecha.

[JoAnCa]

Te recuerdo el conjunto de nodos es un conjunto y por lo tanto no hay un orden establecido. Estás pensando en grafos de libro de texto que se escriben de izquierda a derecha.

Pues sí, para no complejizar mucho el problema, lo estoy viendo de esa forma, como en los libros de texto, pues el soft es mas bien con fines didacticos, incluso la cantidad de nodos puede limitarse

Ya lo tengo resuelto todo por la parte lógica, aplicando el algoritmo de Dijkstra, ya me funciona bien

Pero sigo sin encontrar la solución para distribuir los nodos gráficamente  , no se me ocurre ninguna ecuacion que me sirva para fijar las coordenadas de los circulos en el canvas de un TImage
Hasta ahora en lugar de salirme como debe ser, me salen todos "apilonados" o si no, pegados por los bordes

En fin, sigo experimentando y "tirando piedras" a ver cuando me sale 

o a cuando me den una idea ... 

[jorgeu]

Pero sigo sin encontrar la solución para distribuir los nodos gráficamente  , no se me ocurre ninguna ecuacion que me sirva para fijar las coordenadas de los circulos en el canvas de un TImage
Hasta ahora en lugar de salirme como debe ser, me salen todos "apilonados" o si no, pegados por los bordes

En fin, sigo experimentando y "tirando piedras" a ver cuando me sale 

o a cuando me den una idea ... 

Visita de nuevo la idea de las dos columnas y lo dibujas en hileras horizontales abajo y arriba.

para nodo i -> 1 .. Nnodos
x = margenIzq + (i-(20*(i div 21))-1)*separacionX
y = margenTop + (i div 21)*separacionY

La idea es acomodar hasta 40 nodos. Si la división i/21 se hace entera (para eso el i div 21) va a dar 0 en nodos hasta el 20 y el resto volverá a la posición inicial de x al dar 1 y hacer efectiva la resta. En cuanto a y son dos hileras y a partir del nodo 21 se aplica una separación.

Luego haces los arcos entre los vértices y listo.

[Delphius]

Hola JoAnCa,

El punto es que como te han indicado, no hay una solución o un método elegante y fácil que permita organizar los nodos de un grafo. Es un problema NP-Completo como lo ha dejado en claro jorgeu.
Los algoritmos NP-Completo son difíciles de resolver... o hasta imposibles. Su resolución no puede calcularse en forma polinómica. Para el caso en cuestión, no hay otra vía que la de explorar nodo a nodo como se vincula con el resto. Es cosa de ensayo y error... de pruebas exhaustivas.

Una posible vía de como se encaran es por aproximación, por heurísticas, etc. Pero no hay suficiente garantía de que sea el mejor resultado.

Una posible idea en la que te puedes apoyar es la tomar al grafo más conectado y ponerlo arriba y dejas que los demás "caigan". Es como si tomaras unas cuerdas hechas nudos por un extremo y la sacudieras... los nudos más débiles se soltarán más rápidos, y quedarán abajo por la gravedad los nudos más duros. En términos de grafos, tomas al nodo más conectado y "sacudes" el grafo. esto hará que los más conectados queden por un lado y los menos conectado por el otro.

No se si me explico. Aún así, esto no es garantía de que lleve a la mejor solución, es una aproximación.

Saludos,

[jorgeu]

el problema es NP-completo si se quiere que sea plano. Es decir que los arcos no se crucen en el dibujo.

Con la alternativa que le planteo dejando cruzarse algunos arcos puede dibujar su grafo sin problemas.

No sé, siento que no se ha entendido mi idea 

[JoAnCa]

Pues sí jorgeu, entendí bien tu idea, incluso estaba tratando de hacerlo en 3 columnas, en lugar de 2 como me habias indicado. (tal vez por eso no encontre el polinomio)

Ahora que me das esas formulas se me aclaran mas las cosas, lo probaré

Y en realidad, no me interesa que se cruzen las lineas de los arcos, lo que al principio me refería es a que los nodos no contiguos en una misma columna no se pueden unir con una línea recta. Es donde tengo que inventar un enlace que me sea legible

[jorgeu]

Pues sí jorgeu, entendí bien tu idea, incluso estaba tratando de hacerlo en 3 columnas, en lugar de 2 como me habias indicado. (tal vez por eso no encontre el polinomio)

Ahora que me das esas formulas se me aclaran mas las cosas, lo probaré

Y en realidad, no me interesa que se cruzen las lineas de los arcos, lo que al principio me refería es a que los nodos no contiguos en una misma columna no se pueden unir con una línea recta. Es donde tengo que inventar un enlace que me sea legible

Pudieras aplicarle a la cordenada Y una especie de curva para que los que estén contiguos no toquen otros nodos al hacer líneas entre ellos.

Algo así como una función que en 1 sea 0 luego suba hasta 10 luego baje hasta 20 negativo hasta un min en 30 y luego 0 en 40. Se me ocurre algo como unos factores sobre la función seno ->  a+sin(b*x)*d

¿got it?

[JoAnCa]

Ok, lo probaré también

Parece que las matematicas se me están olvidando un poco, pues esas ecuaciones nunca se me ocurrieron

Con lo que me has dicho ya es un gran avance 

[jorgeu]

Ok, lo probaré también

Parece que las matematicas se me están olvidando un poco, pues esas ecuaciones nunca se me ocurrieron

Con lo que me has dicho ya es un gran avance 

Bueno... pensandolo bien haz mejor un arreglo de 40 posiciones y al nodo i le sumas la posicion curva[i]

Ejemplo

curva = {0,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,0,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,-0}
y le multiplicas un factor

[JoAnCa]

Vaya jorgeu, que ud es mas matemático que informático