Il modo migliore per archiviare / accedere a un grafico diretto

Question

Ho circa 3500 strutture di controllo delle inondazioni che vorrei rappresentare come una rete per determinare i percorsi di flusso (essenzialmente un grafico diretto). Attualmente sto usando SqlServer e un CTE per esaminare in modo ricorsivo tutti i nodi e i loro componenti a monte e questo funziona finché il percorso a monte non si biforca molto. Tuttavia, alcune query impiegano in modo esponenziale più lungo di altre anche quando non sono fisicamente più lontane lungo il percorso (cioè due o tre segmenti "a valle") a causa della complessità a monte aggiunta; in alcuni casi l'ho lasciato passare più di dieci minuti prima di uccidere la query. Sto usando una semplice tabella a due colonne, una delle quali è la struttura stessa e l'altra è la struttura che è a monte di quella elencata nella prima colonna.

Ho provato ad aggiungere un indice usando l'attuale funzione per velocizzare le cose, ma questo non ha fatto differenza. E, per quanto riguarda le possibili connessioni nel grafico, qualsiasi nodo potrebbe avere più connessioni upstream e potrebbe essere collegato da più "downstream" nodi.

È certamente possibile che ci siano cicli nei dati, ma non ho ancora trovato un buon modo per verificarlo (tranne quando la query CTE ha riportato un hit conteggio ricorsivo massimo; quelli erano facili da risolvere).

Quindi, la mia domanda è: sto memorizzando queste informazioni in modo errato? Esiste un modo migliore oltre a un CTE per interrogare i punti a monte?

Answer 1

Non so nulla delle strutture di controllo delle inondazioni. Ma vorrei prendere la prima struttura. E usa una tabella temporanea e un ciclo while per generare il percorso.

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


 FINE
 

Se assumiamo che ogni nodo punti a un figlio. Quindi questo non dovrebbe richiedere più di 3500 iterazioni. Se più nodi hanno lo stesso provider upstream, ci vorrà meno. Ma soprattutto, questo ti consente di farlo ...

SELEZIONA LastNode, CurrentNode, N DA TempTable ORDINA PER N

E questo ti permetterà di vedere se ci sono loop o altri problemi con il tuo provider. Per inciso 3500 righe non è così tanto, anche nel caso peggiore di ciascun provider che punta a un diverso provider upstream, questo non dovrebbe richiedere così tanto tempo.

Answer 2

Il modo migliore per memorizzare i grafici è ovviamente quello di utilizzare un db grafico nativo :-)

Dai un'occhiata a neo4j . È implementato in Java e ha anche i collegamenti Python e Ruby.

Ho scritto due pagine wiki con semplici esempi di modelli di dominio rappresentati come grafici usando neo4j: assembly e ruoli . Altri esempi sono disponibili nella galleria di modellizzazione del dominio .

Answer 3

Tradizionalmente i grafici sono rappresentati da una matrice o da un vettore. La matrice occupa più spazio, ma è più facile da elaborare (voci 3500x3500 nel tuo caso); il vettore occupa meno spazio (3500 voci, ognuna con un elenco di chi si connette).

Ti aiuta?

Answer 4

Penso che la tua struttura dati vada bene (per SQL Server) ma un CTE potrebbe non essere la soluzione più efficiente per le tue query. Potresti provare a creare una procedura memorizzata che attraversa il grafico usando una tabella temporanea come coda, questo dovrebbe essere più efficiente.

la tabella temporanea può anche essere usata per eliminare i cicli nel grafico, sebbene non ci dovrebbe essere alcun

Answer 5

Sì (forse). Il set di dati sembra relativamente piccolo, è possibile caricare il grafico in memoria come matrice di adiacenza o elenco di adiacenza e interrogare direttamente il grafico, presupponendo che si programma.

Per quanto riguarda il formato su disco, DOT è abbastanza portatile / popolare tra gli altri. Sembra anche abbastanza comune memorizzare un elenco di spigoli in un formato file piatto come:

vertex1 vertex2 {edge_label1}+

Dove la prima riga del file contiene il numero di vertici nel grafico e ogni riga successiva descrive i bordi. Se i bordi sono diretti o non diretti dipende dall'implementatore. Se vuoi i bordi diretti espliciti, descrivili usando i bordi diretti come:

vertex1 vertex2
vertex2 vertex1

Answer 6

Le mie esperienze con l'archiviazione di qualcosa come te descritto in un database di SQL Server:

Stavo memorizzando una matrice di distanza, raccontando quanto tempo ci vuole per viaggiare dal punto A al punto B. Ho fatto la rappresentazione ingenua e li ho memorizzati direttamente in una tabella chiamata distanze con colonne A, B, distanza, tempo.

Questo è molto lento con un semplice recupero. Ho scoperto che è molto meglio memorizzare tutta la mia matrice come testo. Quindi recuperalo in memoria prima dei calcoli, crea una matrice di memoria in memoria e lavora lì con esso.

Potrei fornire un po 'di codice, ma sarebbe C #.