algorithm - 时间感知社交图 DS/查询

Question

经典社交网络可以表示为图形/矩阵。

有了图/矩阵就可以轻松计算

• 两个参与者之间的最短路径
• 从 A -> B 的可达性
• 一般统计数据(互惠、平均连通性等)
• 等等

是否有一种理想的数据结构(或对图形/矩阵的修改)可以在具有时间意识的同时轻松计算上述内容？

例如，

输入

t = 0...100

• A <-> B(当 t = 0...10 时)
• B <-> C(当 t = 5...100)
• C <-> A(当 t = 50...100)

示例查询

• A 在任何时候都与 B 相关联吗？ (是)
• A 与 B 相关联而 B 与 C 相关联吗？ (是的。@t = 5...10)
• C 是否可以从 A 到达(是的。@ t=5 )

Answer 1

您正在寻找的是一个明确的持久数据结构。这方面有大量文献，但并不为人所知。 Chris Okasaki 就这个主题写了一本内容丰富的书。看看我对 this question 的回答.

鉴于像 Driscoll 等人的节点拆分结构这样的东西的完整实现，有几种不同的方法来设置您的查询。如果您想了解特定时间范围内的真实情况，您只需检查包含该时间范围内数据的节点。如果你想知道什么时间范围内的事情是真的，你会开始搜索，并在你探索每个新节点时逐渐收紧你的界限。请记住，您的结果可能并不总是连续的 - 考虑两个人开始约会、分手和复合。

我猜想，关于如何对持久图进行有趣的查询，可能至少有一篇值得探索的未探索领域的出版物，如果不是更多的话。