Meilleur moyen de stocker / d'accéder à un graphique dirigé

Question

J'ai environ 3 500 installations de contrôle des inondations que j'aimerais représenter en tant que réseau pour déterminer les chemins d'écoulement (essentiellement un graphe orienté). J'utilise actuellement SqlServer et un CTE pour examiner de manière récursive tous les noeuds et leurs composants en amont, ce qui fonctionne tant que le chemin en amont ne déborde pas beaucoup. Cependant, certaines requêtes prennent exponentiellement plus longtemps que d’autres même quand elles ne sont pas beaucoup plus loin physiquement sur le chemin (c’est-à-dire deux ou trois segments "en aval") en raison de la complexité ajoutée en amont; dans certains cas, je l'ai laissé dépasser dix minutes avant de tuer la requête. J'utilise un simple tableau à deux colonnes, l'une correspondant à l'installation elle-même et l'autre à l'installation située en amont de celle répertoriée dans la première colonne.

J'ai essayé d'ajouter un index à l'aide de l'installation actuelle pour accélérer les choses, mais cela ne faisait aucune différence. Et, en ce qui concerne les connexions possibles dans le graphe, n'importe quel nœud peut avoir plusieurs connexions en amont et peut être connecté à partir de multiples "en aval". nœuds.

Il est certainement possible que les données comportent des cycles, mais je n’ai pas encore trouvé de moyen de le vérifier (sauf lorsque la requête CTE a signalé un nombre maximal de résultats récursifs; ceux-ci étaient faciles à corriger).

Donc, ma question est la suivante: est-ce que je stocke mal les informations? Existe-t-il un meilleur moyen d’interroger les points en amont, autre qu’un CTE?

Answer 1

Je ne connais rien aux installations de contrôle des inondations. Mais je prendrais le premier établissement. Et utilisez une table temporaire et une boucle while pour générer le chemin.

-- 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 nous supposons que chaque nœud pointe vers un enfant. Ensuite, cela ne devrait pas prendre plus de 3 500 itérations. Si plusieurs nœuds ont le même fournisseur en amont, cela prendra moins. Mais plus important encore, cela vous permet de le faire ...

SELECT LastNode, CurrentNode, N FROM TempTable COMMANDER PAR N

Et cela vous permettra de voir s’il ya des boucles ou d’autres problèmes avec votre fournisseur. Incidemment, 3500 lignes n’est pas si important que cela, même dans le pire des cas, lorsque chaque fournisseur pointe vers un fournisseur en amont différent, cela ne devrait pas prendre aussi longtemps.

Answer 2

Le meilleur moyen de stocker des graphiques consiste bien entendu à utiliser un graphique natif db: -)

.

Consultez neo4j . Il est implémenté en Java et comporte également des liaisons Python et Ruby.

J'ai écrit deux pages wiki avec des exemples simples de modèles de domaine représentés sous forme de graphiques à l'aide de neo4j: assembly et rôles . Vous trouverez d'autres exemples à la page Galerie de modélisation de domaine .

Answer 3

Traditionnellement, les graphes sont représentés par une matrice ou un vecteur. La matrice prend plus de place, mais est plus facile à traiter (3500x3500 entrées dans votre cas); le vecteur prend moins de place (3 500 entrées, chacune ayant une liste des personnes auxquelles elles se connectent).

Est-ce que cela vous aide?

Answer 4

Je pense que votre structure de données convient (pour SQL Server), mais un CTE peut ne pas être la solution la plus efficace pour vos requêtes. Vous pouvez essayer de créer une procédure stockée qui traverse le graphique en utilisant une table temporaire comme file d'attente, cela devrait être plus efficace.

la table temporaire peut également être utilisée pour éliminer les cycles dans le graphique, bien qu'il ne devrait pas y en avoir

Answer 5

Oui (peut-être). Votre ensemble de données semble relativement petit, vous pouvez charger le graphique en mémoire sous forme de matrice ou de liste d'adjacence et interroger directement le graphique - en supposant que vous programmez.

En ce qui concerne le format sur disque, le DOT est assez portable / populaire parmi d'autres. Il semble également assez courant de stocker une liste d’arêtes dans un format de fichier plat tel que:

vertex1 vertex2 {edge_label1}+

Où la première ligne du fichier contient le nombre de sommets dans le graphique, et chaque ligne après décrit les arêtes. Que les bords soient dirigés ou non dirigés appartient à l'implémenteur. Si vous voulez des arcs dirigés explicites, décrivez-les en utilisant des arêtes dirigées telles que:

vertex1 vertex2
vertex2 vertex1

Answer 6

Mes expériences avec le stockage de quelque chose comme décrit dans une base de données SQL Server:

Je stockais une matrice de distance, indiquant le temps nécessaire pour parcourir un point A à un point B. J'ai fait la représentation naïve et je les ai stockées directement dans un tableau appelé distances avec les colonnes A, B, distance, temps.

Ceci est très lent pour une simple récupération. J'ai trouvé qu'il était bien préférable de stocker toute ma matrice sous forme de texte. Puis récupérez-le en mémoire avant les calculs, créez une structure matricielle en mémoire et travaillez-y.

Je pourrais fournir du code, mais ce serait du C #.