Como extraer de un grafo un subconjunto conectado (relaciones de tablas)

[[Delphius]]

Entonces lo que buscas es obtener todos los caminos posibles entre un nodo y otro. Y después de dicho conjunto el más optimo?

Si es eso, perdona, es que yo entendía al subconjunto de nodos buscado como la solución.

Umm.. tendría que pensarlo bien. Aunque a primera impresión sería por "fuerza bruta":

Ir recorriendo nodos hasta llegar al destino. Una vez encontrado el camino, volver a repetir el mismo camino y en el nodo anterior virar hacia otro camino (si es viable, claro está) y seguir recorriendo hasta llegar al destino.
Seguir repitiendo el camino mientras se tengan caminos sin explorar, y con el nodo inmediatamente anterior.

Se que no es un método eficiente, habría que pensarlo.

La otra opción, un tanto más complicada es hacer un Disjkstra doble. Repetir Disjsktra desde el principio y a la vez desde el final. La idea es ir avanzando desde ambos extremos y buscando los nodos coincidentes. Si existe en sus conjuntos P() algún nodo es posiblemente de que por allí pase una de las rutas ruta. Repetir el proceso con las puntas condicentes más "alejadas". No se que tan fiable pueda ser esta idea... se me acaba de surgir, y hay que cocinarla mejor porque está un tantito cruda.

Por ahora, eso tengo en mente. Tal vez sirva de algo.
Saludos,

[[kuan-yiu]]

Yo implementé un grafo pesado dirigido de forma visual, pero como guardaba información musical tenía que recorrerlo también linealmente en tiempo real para poder ejecutar la música que contenía.
El problema es que el sistema que yo he usado para guardarlo en memoria no se parece en nada al tuyo, así que no sé si te servirá lo que yo hice.
En mi caso cada nodo es una clase que guarda una lista de los nodos hijo y por desgracia para encontrar grupos aislados tuve que usar la fuerza bruta: recorrer todos los nodos buscando el que no es hijo de nadie.

Me temo que en tu caso tendrás que hacer algo parecido.

[mamcx]

Si, creo que va ser la unica. Leyendo la teoria de grafos me doy cuenta que no hay algoritmo para eso y toca a lo bruto. Menos mal soy bruto!

[[Delphius]]

Hola Mario, ¿lograste avanzar en algo?
Me quedé un tanto inquieto por no haber encontrado algún método... me es de extrañar que sólo se consiga por fuerza bruta. Debe haber algo... pero yo por el momento estoy a oscuras

Saludos,

[mamcx]

Nada, segun parece es solo la fuerza bruta la que funciona e igual veo que es mas cmplicado que lo que suponia. Al final creo que mejor voy a escribir las respuestas de antemano, para unas 20 tablas me sale en menos tiempo que seguirle insisitiendo a esto.