时间感知社交图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）就这个主题写了一本相当丰富的书。看看我对这个问题的回答。

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

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