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.

[[Delphius]]

Empezado por 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.

Hola Mamx,
Le he estado dando vuelta a esto, y debe ser algo que no termino de comprender.
Yo apliqué un algoritmo sencillo, un Dikjstra disponible en Wikipedia y con él obtengo no sólo la ruta mínima sino que además se queda guardado en vector de punteros aquel conjunto de nodos que garantiza la ruta mínima.

Lo hice a mano, con el DER de la DB de ejemplo que viene en Firebird.

la estructura es como sigue:

+---+                +---+
| 1 |---------------<| 2 |
+---+                +---+
  |                    Y
  |    +---+    +---+  |   
  +---<| 3 |---<| 4 |  | 
       +---+    +---+  |
                  V    |
                  |  +---+    +---+
                  +--| 5 |---<| 6 |
                     +---+    +---+
                    L     \
                   /       A
              +---+         +---+
              | 7 |         | 8 |   
              +---+         +---+
                |             Y
                A             |
              +---+         +---+
              | 9 |>--------| 10|
              +---+         +---+

El lado del muchos es aquel que tenga un <, >, A, L, Y.
1. Ciudad
2. Trabajos
3. Clientes
4. Ventas
5. Empleados
6. HistorialSalario
7. Depto
8. AsignacionesProyecto
9. PresupuestoDepartamental
10. Proyecto
El grafo es análogo, simplemente borrares el muchos y tenemos uno.

¿Cual es problema? Los pesos. Por ejemplo si asumimos un valor uniforme a todos, es posble que obtengamos una ruta no muy deseada.
Por ejemplo, digamos que tu buscas la relación entre 4 (Ventas) y (Proyecto). Hay dos caminos posibles, pero el algoritmo te encuentra uno.

Si el costo es 1 para todos, obtendrás esta salida:
D={2,2,1,0,1,2,2,2,3,3}
P={3,5,4,4,4,5,5,5,7,8}
C={/,/,/,/,/,/,/,/,/,/,10} /significa quitado de lista

En la lista P se obtiene en forma inversa, las tablas que intervienen.
P(z), que representa a la tabla destino (z = 10), apunta a 8.
P(8), apunta a 5.
P(5), apunta 4. La inicial.
Entonces intervienen: Proyecto, AsignacionesProyecto, Empleado, Ventas.

Haciendo analogía con lo que tu pides y buscando la manera de interpretar adecuadamente ese "indispensable para relacionar" que tu mencionas puedo llegar a la conclusión de que no necesariamente la ruta más corta te llevará por aquellas relaciones que tu consideras necesarias.

Por ejemplo, haz de cuenta que la tabla 10 es tu Detalle y que la 9 es el Encabezado (se que en el ejemplo no da pero mantengamos el supuesto).
Se ve por la forma de las relaciones que el algoritmo (con estos pesos) prefiere irse por otro lado.

El tema es que mientras exista más de una posibilidad a una tabla no se puede garantizar de que el camino tocará alguna de potencial interés para obtener algo coherente a lo que buscamos.

Volviendo al caso del ejemplo que yo hice: ¿Tiene alguna utilidad haber relacionado las ventas con los empleados, y los proyectos a los cuales fue asignado el empleado?
Puede que si... puede que no... ¿realmente se quería eso? O por el contrario ¿Andaba buscando otra relación?

Y como dije, esto sucede por tener el mismo peso. ¿Que hubiera pasado si la relación entre asignaciones y proyectos tuviera un valor más alto? Por ejemplo 3. El algoritmo hubiera preferido irse por la otra rama.
Y si nos volvemos a aquel supuesto... entonces ahora si fue por un lugar adecuado.

A lo que voy, es que mientras exista más relaciones entre las tablas y exista cierta uniformidad en los pesos no se puede garantizar que pasará por algún punto que realmente sea de interés.

La solución que yo estoy analizando es favorecer con un peso bajo a las relaciones de "amistad" entre las tablas y penar con un valor alto a las tablas que no tienen tanta afinididad. Esto también dependerá también del verdadero y potencial uso que le atribuya el cliente.

¿A que podemos entender afinidad? Pues existe mayor afinidad entre la tablas Encabezados con sus respectivos Detalles que con una tabla a la que actua de esclava.
Por ejemplo es posible que la relación entre Ventas y Empleado tenga un valor bajo mientras que entre Empleado y Asignaciones un valor alto. Cabe la posibilidad de que el cliente le resulta más útil un cubo formado por los datos entre las ventas por Empleado que saber las asignaciones por empleado.

Bueno, eso es lo que mi cansado cerebro está pensando.

Es muy posible de que lo que acabo de decir no sea útil, siento que algo se me está escapando, que algo no estoy comprendiendo.

No se que tan útil te puedo estar siendo.
Saludos,

[mamcx]

Bueno, primero que todo un aplauso por la investigacion (que desparche hacer esos grafos a punta de ASCII Art!).


Pienso que el problema se parte en 2, y solo la primera parte es la dificil para mi.

El problema es:

1- Como, a partir de un numero N de nodos saco los nodo adyacentes que son necesarios para sacar un subgrafo conectado
2- Cual es la ruta mas optima entre un nodo x y uno y. Esa es muy facil y la tengo resuelta.

Imagina en tu grafica que selecciono a 1 y 5. Hay dos caminos posibles, uno mas largo que otro. Lo unico que deseo es tener ambos caminos, que usando el algoritmo de ruta corta saco cual es la mas efectiva entre 1 y 5.

No te preocupes por los pesos... pero si es necesario preocuparse, digamos que le pongo peso 1 a las maestras, 2 a las de movimiento. O 1 a las relaciones 1-1 y 2 a las 1-muchos.

[[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.