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

存储图形的最佳方式当然是使用本机图形数据库:-)

看一看 neo4j . 它是用Java实现的,也有Python和Ruby绑定。

我写了两个wiki页面,其中包含使用neo4j表示为图形的域模型的简单示例: assembly 和 roles 更多示例请参见 domain modeling gallery 页面。

我对防洪设施一无所知。但我会选择第一个设施。并使用临时表和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次迭代。如果多个节点具有相同的上游提供者,则需要更少的资源。但更重要的是,这可以让你做到这一点。..

选择最后节点、当前节点、N 来自TempTable 按N排序

这将让您看到您的提供商是否存在任何循环或任何其他问题。顺便说一句,即使在每个提供者指向不同上游提供者的最坏情况下,3500行也没那么多,这应该不会花那么长时间。

传统上,图要么由矩阵表示,要么由向量表示。矩阵占用更多空间,但更容易处理(在您的情况下为3500x3500个条目);向量占用更少的空间(3500个条目,每个条目都有一个连接对象的列表)。

这对你有帮助吗?

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

温度表也可以用来消除图中的循环,尽管不应该有任何循环

是的(也许)。你的数据集听起来相对较小,你可以将图作为邻接矩阵或邻接列表加载到内存中,并直接查询图——假设你在编程。

就磁盘格式而言, DOT 在其他人中相当便携/流行。以平面文件格式存储边列表似乎也很常见,例如:

vertex1 vertex2 {edge_label1}+

其中文件的第一行包含图中的顶点数,之后的每一行描述边。边缘是定向的还是无定向的取决于实施者。如果你想要显式的有向边,那么使用有向边来描述它们,比如:

vertex1 vertex2
vertex2 vertex1

我在SQL Server数据库中存储您描述的内容的经验:

我存储了一个距离矩阵,告诉从a点到点B需要多长时间。我做了简单的表示,并将它们直接存储在一个名为距离的表中,表中有列a、B、距离、时间。

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

我可以提供一些代码,但应该是C#。