存储/访问有向图的最佳方式

StackOverflow https://stackoverflow.com/questions/191897

题

我有大约3500个防洪设施，我想将其表示为确定流路径的网络（本质上是有向图）。我目前正在使用SqlServer和CTE递归检查所有节点及其上游组件，只要上游路径不分叉，这就可以工作。然而，由于增加的上游复杂性，一些查询比其他查询指数地长得多，即使它们在物理上不太远（即两个或三个段“下游”）。在某些情况下，我会在杀死查询之前让它超过十分钟。我正在使用一个简单的双列表，一列是设施本身，另一列是第一列中列出的设施的上游设施。

我尝试使用当前设施添加索引以帮助加快速度，但这没有任何区别。并且，对于图中的可能连接，任何节点可以具有多个上游连接，并且可以从多个“下游”连接到多个上游连接。节点

数据中肯定存在循环，但我还没有找到一种好的方法来验证这一点（除了CTE查询报告最大递归计数命中时;这些很容易修复）。

所以，我的问题是，我存储这些信息是错误的吗？有没有比CTE更好的方法来查询上游点？

有帮助吗？

解决方案

我对防洪设施一无所知。但我会选择第一个设施。并使用临时表和while循环来生成路径。

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

如果我们假设每个节点都指向一个孩子。那么这应该不超过3500次迭代。如果多个节点具有相同的上游提供程序，那么它将花费更少。但更重要的是，这可以让你这样做......

SELECT LastNode，CurrentNode，N 来自TempTable ORDER BY N

这将让您了解您的提供商是否存在任何循环或任何其他问题。顺便提一下，3500行并不是那么多，所以即使在每个提供商指向不同的上游提供商的最坏情况下，这也不应该花那么长时间。

其他提示

存储图形的最佳方法当然是使用本机图形db： - ）

查看 neo4j 。 它是用Java实现的，并且还有Python和Ruby绑定。

我写了两个wiki页面，其中包含使用neo4j表示为图形的域模型的简单示例： assembly 和角色。更多示例可在域建模库页面上找到。

传统上，图表由矩阵或向量表示。矩阵占用更多空间，但更容易处理（在您的情况下为3500x3500条目）;向量占用较少的空间（3500个条目，每个条目都有一个连接到谁的列表）。

这对你有帮助吗？

我认为您的数据结构很好（对于SQL Server），但CTE可能不是最有效的查询解决方案。您可以尝试使用临时表作为队列来创建遍历图的存储过程，这应该更有效。

临时表也可用于消除图中的循环，但不应该有任何

是（也许）。您的数据集听起来相对较小，您可以将图形作为邻接矩阵或邻接列表加载到内存中，并直接查询图形 - 假设您编程。

就磁盘格式而言， DOT 相当便携/受欢迎。以平面文件格式存储边缘列表似乎很常见，如：

vertex1 vertex2 {edge_label1}+

文件的第一行包含图表中顶点的数量，之后的每一行描述边缘。边缘是指向还是不指向取决于实现者。如果你想要显式的有向边，那么使用有向边描述它们，如：

vertex1 vertex2
vertex2 vertex1

我在SQL Server数据库中存储类似于您的内容的经验：

我正在存储一个距离矩阵，说明从A点到B点需要多长时间。我已经完成了天真的表示并将它们直接存储到一个名为距离的表中，其中列A，B，距离，时间。

这在简单的撤退上非常缓慢。我发现将整个矩阵存储为文本要好得多。然后在计算之前将其检索到内存中，在内存中创建矩阵结构并在那里使用它。

我可以提供一些代码，但它将是C＃。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top