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

[mamcx]

Ok, estoy armando un sistema de reporteador tipo OLAP.

Quiero que el sistema automagicamente deduzca las relaciones entre las tablas que el usuario selecciona.

Tengo estas tablas relacionadas asi:

Municipio 1-* Barra
Cliente 1-* Barra
Banco 1-* EncabezadoMovimiento
Cliente 1-* EncabezadoMovimiento

Asi que quiero preguntar:

Código Delphi [-]
RelacionesEntre('Cliente','Barra')

=

'Cliente','Barra'

RelacionesEntre('Municipio','Cliente')

=

'Municipio','Cliente','Barra'

RelacionesEntre('Banco','Barra')

=

'Banco','Barra','Cliente','EncabezadoMovimiento'

Tengo todo dentro de un grafo, y ya le aplico un algoritmo de ruta corta para sacar la forma mas eficiente de relacionar, pero no se como substraer de un grafo un subgrafo que sea conectado.

Alguna idea? Seudocodigo estario Ok o ejemplo en cualquier lenguaje menos assembler.

[mamcx]

Le he dado vueltas en google y no encuentro un ejemplo de como poder hacer esto, y me parece que deberia ser un caso comun...

Creo que voy a tener que gastarle mas neuronas de lo anticipado...

[[Delphius]]

Hola Mamx,
Tengo un tanto oxidada la cátedra de estructura de datos, sobre todo la parte de grafos.

No se que tanto te podría ser de ayuda. Pero al menos puedo prestar parte de mi cabeza, Cabeza y media piensan más que una.

No termino de comprender como es que empleas grafos para representar las relaciones.

Si me pudieras dar una pequeña descripción de ello tal vez comprenda mejor algunas cosas. ¿Estás empleando alguna fuente bibliográfica en particular?

Creo que tengo mi carpeta de Estructuras de dato a mano... puede que encuentre algo que sirva.

Pero primero me gustaría sacarme esa duda: ¿Como es que haces la representación de las relaciones con grafos?

No he dicho algo de utilidad, pero si en algo puedo serte útil pegame el grito.

Saludos,

[mamcx]

De forma muy simple, como con los programas que diagraman las tablas tipo UML.


Cada nodo es un tabla, luego usando vertices conecto la tabla de origen con la de destino. Solo conecto tablas, no campos porque en mi estructura es innecesario.

Asi que sale mas o menos:

Clientes
|
------------------
| |
Barras Municipios

[[Delphius]]

Hola mamx,
Dejame ver si te entiendo...
Entonces tienes un grafo más o menos como este:

+---+    +---+    +---+    +---+    +---+
| M |----| B |----| C |----| E |----| B |
+---+    +---+    +---+    +---+    +---+

Siendo la primera B asociada a Barra, y la segunda a Banco.
Se lo vemos como un DER la cosa queda así:

+---+      +---+      +---+      +---+      +---+
| M |-|---<| B |>---|-| C |-|---<| E |>---|-| B |
+---+      +---+      +---+      +---+      +---+

Bueno. Hasta allí creo que puedo entenderte. El tema del encontrar la ruta más corta se basa en el costo peso de ir de un nodo a otro... No se como estarás haciendo esto, el valor de los pesos creería que son todos iguales aunque tengo mis dudas.

¿Estás empleando Dijkstra?
El algoritmo de Dijkstra, si no falla la cabeza, lo que hace es calcular la distancia mínima desde un Nodo a TODOS los demás.
Y si obtenemos las distancias mínimas de un nodo a otro se puede recorrer la estructura a través de dichos mínimos y deternos cuando se haya llegado al nodo destino.
A lo que voy es que el algoritmo de Dijkstra va etiquetando los nodos y llevando una estructura desde los mínimos hasta los máximos, en forma acumulada. Como dicha estructura contiene a todos los nodos, en vez de llegar hasta el final, parar el algoritmo ni bien de detecte el nodo que queremos como destino.

¿O yo estoy comprendiendo mal el problema?

No se... ya me estoy confundiendo.

Lo que estás buscando es que dada dos tablas (nodos) el sistema devuelva las relaciones entre dichas tablas (nodos), entonces si partimos de un nodo a otro ira estableciendo las relaciones hasta llegar al nodo destino.

Hay algo que se me escapa

Saludos,

[mamcx]

Efectivamente uso Dijkstra. No tengo problema en saber la ruta minima.

MI problema es como extraigo un subconjunto del grafo total que representa todas las relaciones de las tablas en la BD a uno mas pequeño que solo contenga las que se seleccionaron y las que hacen falta para conectar esas tablas entre si.

Si tengo una tabla cliente, encabezado y detalle de factura, y selecciono a detalle y cliente, quiero que devuelva a las 3, porque encabezado es indispensable para relacionar a cliente y detalle.