Melhor maneira de armazenar / Acesso um grafo direcionado

Question

Eu tenho cerca de 3500 instalações de controle de inundação que gostaria de representar como uma rede para determinar caminhos de fluxo (essencialmente um grafo direcionado). Atualmente estou usando o SQLServer e uma CTE para examinar de forma recursiva todos os nós e seus componentes a montante e isso funciona, desde que o caminho a montante não desembolsar muito. No entanto, algumas consultas tomar exponencialmente mais tempo do que os outros, mesmo quando eles não são muito mais longe fisicamente para o caminho (isto é, dois ou três segmentos de "jusante"), devido à complexidade adicionada a montante; em alguns casos, eu deixá-lo ir mais de dez minutos antes de matar a consulta. Eu estou usando uma simples tabela de duas colunas, uma coluna sendo a instalação em si e sendo o outro a facilidade que está a montante do listado na primeira coluna.

Eu tentei adicionar um índice usando a facilidade atual para coisas ajudar a acelerar, mas que não fez diferença. E, tal como para as ligações possíveis no gráfico, todos os nós podem ter várias ligações a montante e pode ser ligado a partir de vrios ns "a jusante".

É certamente possível que existem ciclos nos dados, mas eu ainda não descobri uma boa maneira de verificar isso (excepto quando a consulta CTE relatou um hit máximo contagem recursiva, aqueles eram fáceis de correção)

Então, minha pergunta é, estou armazenando esta errado informações? Existe uma maneira melhor que não seja um CTE para consultar os pontos a montante?

Answer 1

Eu não sei nada sobre as instalações de controle de inundações. Mas gostaria de aproveitar a primeira instalação. E usar uma tabela temporária e um loop while para gerar o caminho.

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


END

Se assumirmos que todos os pontos de nó para uma criança. Então este não deve demorar mais de 3500 iterações. Se vários nós têm o mesmo provedor, então vai demorar menos. Mas o mais importante, isso permite que você faça isso ...

SELECIONAR LastNode, CurrentNode, N DE TempTable ORDER BY N

E isso vai deixá-lo ver se existem loops ou quaisquer outros problemas com seu provedor. Aliás 3500 linhas não é que é assim mesmo no pior caso de cada provedor apontando para um provedor diferente, isso não deve demorar muito tempo.

Answer 2

A melhor maneira de armazenar gráficos é, naturalmente, para usar um db gráfico nativo: -)

Dê uma olhada Neo4j . É implementado em Java e tem Python e Ruby ligações também.

Eu escrevi duas páginas wiki com exemplos simples de modelos de domínio representados como gráficos usando Neo4j: montagem papéis . Mais exemplos são encontrados na href="http://wiki.neo4j.org/content/Domain_Modeling_Gallery" rel="noreferrer"> modelagem de domínio página da galeria

Answer 3

Tradicionalmente gráficos são representadas por uma matriz ou um vector. A matriz toma mais espaço, mas é mais fácil de processo (3500x3500 entradas no seu caso); o vetor ocupa menos espaço (3500 entradas, cada um tem uma lista de quem eles se conectam).

Isso ajuda você?

Answer 4

i acha que sua estrutura de dados é bom (para SQL Server), mas um CTE pode não ser a solução mais eficiente para suas consultas. Você pode tentar fazer um procedimento armazenado que atravessa o gráfico usando uma tabela temporária como uma fila em vez disso, este deve ser mais eficiente.

tabela a temperatura pode também ser usada para eliminar os ciclos no gráfico, no entanto, não deve haver qualquer

Answer 5

Sim (talvez). Seu conjunto de dados sons relativamente pequenas, você poderia carregar o gráfico para a memória como uma matriz de adjacência ou lista de adjacência e consultar o gráfico diretamente - supondo que você programa.

formato

Tanto quanto no disco, DOT é bastante portátil / popular entre outros. Parece também bastante comum para armazenar uma lista de arestas em um formato de arquivo simples como:

vertex1 vertex2 {edge_label1}+

Quando a primeira linha do arquivo contém o número de vértices no gráfico, e cada linha depois que descreve bordas. Se as bordas são dirigida ou não dirigida é até o implementador. Se você quiser arestas dirigidas explícitas, em seguida, descrevê-los usando arestas dirigidas como:

vertex1 vertex2
vertex2 vertex1

Answer 6

As minhas experiências com armazenar algo como você descreveu em um banco de dados SQL Server:

Eu estava armazenando uma matriz de distância, como dizer quanto tempo leva para viajar do ponto A ao ponto B. Eu fiz a representação ingênua e armazenados-los diretamente em uma tabela chamada distâncias com colunas A, B, distância, tempo.

Isto é muito lento em simples retreival. Eu descobri que é muito melhor para armazenar toda a minha matriz como texto. Em seguida, recuperá-la na memória antes de os cálculos, criar um struxture matriz na memória e trabalhar com ele lá.

Eu poderia fornecer com algum código, mas seria C #.