3

基本上我有如下场景：

vertex --- vertex* --- vertex

但是，在路径中的这一点上，顶点 * 可能具有可变数量的顶点，从而导致

vertex --- vertex1 --- vertex
vertex --- vertex2 --- vertex
vertex --- vertexN --- vertex

N在我遍历到这个顶点之前，我不知道会发生什么。当我第一次遍历该节点时，任意函数将能够确定该顶点在路径中的该点有多少个实例。

我只是记录N为一个属性，还是创建额外N数量的带有中间顶点且值增加的路径？

一个真实的例子是，一个包含未知数量文件夹的文件目录（直到您打开父目录），每个文件夹包含一个文件，您需要遍历每个文件路径。

更新：

这是我所期望的：

（第一次遍历，遇到具有特殊属性*的顶点）

A --- X* --- B

生成相同 X 顶点的附加实例，连接到父 A 和子 B。

A --- X1 --- B
 \--- X2 --/
  \-- X3 -/

或者

   A --- X1 --- B
   A --- X2 --- B
   A --- X3 --- B

所以现在遍历会像

A, X1, B
A, X2, B
A, X3, B

X顶点实例彼此完全相同，然后它们具有索引整数。实例数由第一次初始遍历 ( A, X*, B) 确定。X* 可能会生成 3 或 50 或 100 个额外的实例。

对于存储，我的意思是将此索引值存储在 X* 并每次递增，直到N达到最大整数。因此，对于上面的示例，它的起始索引为 1，最大值为 3。这将绕过在中间插入额外顶点并将其连接到 A 和 B 的需要。但是，我不确定这是否是最适合我的情况，我需要遍历每条生成的路径。

4

2 回答 2

2

我有点困惑你到底在找什么；）

首先，您能否进一步详细说明您的用例？您是否正在搜索两个顶点A和之间的所有顶点的列表B？

A --- vertex1 --- B
A --- vertex2 --- B
A --- vertexN --- B

或者您是否正在搜索可以从A特定深度到达的所有顶点（例如：2）：

A --- vertex1 --- B
A --- vertex2 --- C
A --- vertexN --- D

其次，您是否正在寻找如何以最佳方式存储它的解决方案？或者您是否已经将其存储并正在寻找一种如何查询它的方法？如果你想查询它，你期望得到什么结果？路径数？还是中间顶点列表？

我认为我们可以解决上述所有问题；）

于 2014-05-27T15:52:28.040 回答
2

所以我想现在我得到了你的用例。

你是对的，你基本上必须选择：

  1. 用其他顶点替换顶点“x*”：
    • 首先，我将执行一个简单的查询，搜索具有特殊属性的所有顶点（我不会在此步骤中使用遍历，但此特殊属性上的索引应该更快）
    • 其次，我会用相应数量的真实顶点替换事务中的所有它们（如果您想再次执行此查询，请记住删除“x *”顶点）
    • 第三，您可以使用所有内置的遍历语句，因为查询结构由图表显示。

临：

  • 实施简单。
  • 数据完全符合您的预期，无需解析属性，如果您的应用程序中有 5 条从 A 到 B 的路径，则有 5 条从 A 到 B 的路径存储在您的数据库中。
  • 可以大量使用内置功能而无需（ArangoDB 期望所有边默认都在物理上）

缺点：

  • 冗余数据（X1 - Xn 是彼此的副本），因此如果您在此处存储一些数据，您必须注意保持同步
  • 更高的内存消耗。
  • 图表中有更多路径 => 更多遍历步骤
  • 性能会低于选项 2。

选项 2：仅存储一个中间顶点并使用特殊属性

  1. 只存储顶点 X*
  2. 实现您自己的访问者来检查特殊属性（根据您的描述，如果路径上的最后一个顶点（X *）具有特殊属性，我认为您想在顶点 B 处检查）。如果是这样，则将 (AXB) n 次的值添加到结果中。

临：

  • 高性能
  • 无冗余

缺点：

  • 您必须在应用程序中实现将 X* 替换为 X1 - Xn 的逻辑
  • 您必须实现自己的访问者
  • 您的域模型与数据库中的内容略有不匹配

我会根据您的数据集的大小做出决定。如果您有一个非常小的数据集并且冗余/性能不是问题，我会选择选项 1，它更简单、更省力。如果你有一个大数据集并且需要高性能选项 2 我猜会更好。

希望有帮助；）

于 2014-06-03T08:38:47.143 回答