La mejor manera de almacenar / acceder a un gráfico dirigido

Question

Tengo alrededor de 3500 instalaciones de control de inundaciones que me gustaría representar como una red para determinar las rutas de flujo (esencialmente un gráfico dirigido). Actualmente estoy usando SqlServer y un CTE para examinar recursivamente todos los nodos y sus componentes ascendentes y esto funciona siempre que la ruta ascendente no se bifurque mucho. Sin embargo, algunas consultas toman exponencialmente más tiempo que otras, incluso cuando no están físicamente mucho más lejos en el camino (es decir, dos o tres segmentos '' aguas abajo '') debido a la complejidad agregada aguas arriba; en algunos casos lo dejé pasar más de diez minutos antes de finalizar la consulta. Estoy usando una tabla simple de dos columnas, una columna es la instalación en sí y la otra es la instalación que está aguas arriba de la que aparece en la primera columna.

Intenté agregar un índice usando la instalación actual para ayudar a acelerar las cosas, pero eso no hizo ninguna diferencia. Y, en cuanto a las posibles conexiones en el gráfico, cualquier nodo podría tener múltiples conexiones en sentido ascendente y podría conectarse desde múltiples 'en sentido descendente'. nodos.

Ciertamente es posible que haya ciclos en los datos, pero aún no he descubierto una buena manera de verificar esto (aparte de cuando la consulta CTE informó un golpe de recuento recursivo máximo; fueron fáciles de corregir).

Entonces, mi pregunta es, ¿estoy almacenando esta información de manera incorrecta? ¿Hay otra manera mejor que un CTE para consultar los puntos aguas arriba?

Answer 1

No sé nada sobre las instalaciones de control de inundaciones. Pero tomaría la primera instalación. Y use una tabla temporal y un ciclo while para generar la ruta.

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)


DECLARE @intN INT
SET @intN = 1

INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- Insert first item in list with no up stream items...call this initial condition
  SELECT LastNode, CurrentNode, @intN
  FROM your table
  WHERE node has nothing upstream

WHILE @intN <= 3500
BEGIN
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      SELECT LastNode, CurrentNode, @intN
      FROM your table
      WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)

IF @@ROWCOUNT = 0
     BREAK


 FIN

Si suponemos que cada nodo apunta a un hijo. Entonces esto no debería llevar más de 3500 iteraciones. Si varios nodos tienen el mismo proveedor ascendente, se necesitará menos. Pero lo más importante, esto te permite hacer esto ...

SELECCIONAR LastNode, CurrentNode, N DE la tabla temporal ORDENAR POR N

Y eso le permitirá ver si hay algún bucle o algún otro problema con su proveedor. Por cierto, 3500 filas no es tanto, incluso en el peor de los casos de cada proveedor que apunta a un proveedor ascendente diferente, esto no debería llevar tanto tiempo.

Answer 2

La mejor manera de almacenar gráficos es, por supuesto, usar un gráfico nativo db :-)

Eche un vistazo a neo4j . Se implementa en Java y también tiene enlaces de Python y Ruby.

Escribí dos páginas wiki con ejemplos simples de modelos de dominio representados como gráficos usando neo4j: ensamblaje y roles . Se encuentran más ejemplos en la página galería de modelado de dominio .

Answer 3

Tradicionalmente, los gráficos están representados por una matriz o un vector. La matriz ocupa más espacio, pero es más fácil de procesar (3500x3500 entradas en su caso); el vector ocupa menos espacio (3500 entradas, cada una tiene una lista de a quién se conectan).

¿Eso te ayuda?

Answer 4

creo que su estructura de datos está bien (para SQL Server) pero un CTE puede no ser la solución más eficiente para sus consultas. Puede intentar hacer un procedimiento almacenado que atraviese el gráfico usando una tabla temporal como una cola, esto debería ser más eficiente.

la tabla temporal también se puede usar para eliminar ciclos en el gráfico, aunque no debería haber ninguna

Answer 5

Sí (tal vez). Su conjunto de datos parece relativamente pequeño, puede cargar el gráfico en la memoria como una matriz de adyacencia o lista de adyacencia y consultar el gráfico directamente, suponiendo que programe.

En cuanto al formato en disco, DOT es bastante portátil / popular entre otros. También parece bastante común almacenar una lista de bordes en un formato de archivo plano como:

vertex1 vertex2 {edge_label1}+

Donde la primera línea del archivo contiene el número de vértices en el gráfico, y cada línea posterior describe los bordes. Si los bordes están dirigidos o no, depende del implementador. Si desea bordes dirigidos explícitos, descríbalos usando bordes dirigidos como:

vertex1 vertex2
vertex2 vertex1

Answer 6

Mis experiencias con el almacenamiento de algo como lo que describió en una base de datos de SQL Server:

Estaba almacenando una matriz de distancia, indicando cuánto tiempo se tarda en viajar del punto A al punto B. Hice la representación ingenua y la almacené directamente en una tabla llamada distancias con columnas A, B, distancia, tiempo.

Esto es muy lento en el retiro simple. Descubrí que es mucho mejor almacenar toda mi matriz como texto. Luego retírelo a la memoria antes de los cálculos, cree una estructura matricial en la memoria y trabaje con ella allí.

Podría proporcionar algún código, pero sería C #.