java - 图:将双向边建模为两条单独的边有哪些优缺点？

Question

我目前正在开发一个应用程序，我们基本上是在“项目”之间建立一个图表。我认为这些项目之间存在不同类型的链接，但我现在正在努力决定如何为这些项目建模，尤其是双向链接。

<强>1。示例:

ItemB --isChildOf---> ItemA
ItemA --isMasterOf--> ItemB

我认为可以这样建模:

示例 2

ItemA <---> ItemB

在我的数据库模型中，我目前对我的链接建模如下:

* sourceID
* targetID
* relationType (e.g. isMasterOf, isChildOf, maybe more...)

我是否还需要将方向作为表格中的一个字段？到目前为止，我没有将它作为一个单独的字段，因为在 IMO 中，方向是由 sourceID 和 targetID 隐式定义的。

我不确定在哪些情况下我需要示例 1，在哪些情况下示例 2 就足够了。我认为示例 1 就像推特，其中 UserA 可以关注 userB，但反之则不然。另一方面，在我看来，Facebook 始终是示例 2。

希望我的问题有道理。

Answer 1

如果您想要一个尽可能通用的解决方案，并且适用于任何简单的图形建模案例(一对多/多对一，多对多)，只需将链接建模为 (source_id , target_id) 对在单独的链接表中。这样你们都可以

• 通过具有边缘对 (a.id, b.id) 和 (b.id, a.id) 和单向链接通过具有依赖于方向的边对来建模双向链接
• 通过查看哪个节点是源节点和哪个节点是目标节点来区分边缘方向 - 无需单独的方向场。

如果您想为特定情况制定优雅的解决方案，而您想要建模的图类型存在实际限制，您首先需要决定

1. 您希望在对象之间允许什么样的链接:它们将始终是单向还是双向的，或者您是否需要区分两者和
2. 无论是树状结构(其中一个对象只有一个父对象但有多个子对象)，还是更通用的图(其中一个对象可能有多条边来来去去)。

关于第一点，如果你知道所有的链接都是同类的，你真的不需要在代码中区分 edge (source_id, target_id) 和 edge (target_id, source_id)，因为两者都意味着两个对象/节点之间的边。

就第二点而言:如果您要建模的图形类似于一棵树或一片森林(每个对象都有 0 或 1 个父对象和 0 到 n 个子对象，则所有链接都是同一类型 - uni- 或双向)，您可以只向对象本身添加类似 parent_id 的内容，而不是在单独的链接表上对连接进行建模。

显然，如果您需要为边添加其他属性(例如重量或方向以外的某种类型属性)，则必须相应地添加字段。在那种情况下，在任何情况下在单独的表上对边建模都是最有意义的，因为边将不仅仅是节点之间的简单链接，而是具有实际属性的对象。