prolog - 如何在 Prolog 中通过直接访问相邻顶点来表示有向循环图

Question

我需要在 Prolog 中使用循环构造有向图（在运行时），但我不确定如何表示它。我的要求是我需要在恒定时间内从一个顶点到达他的邻居。

是否可以将其表示为一棵树，例如：

t(left_son,V,right_son)

但如何解决循环？

我可以列出边：

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

要不就

[a->[b],b->[c],c->[a,d],d->[]]

但是如何避免在搜索邻居时调用列表中的函数“成员”，这会花费线性时间？

谢谢你的帮助

Answer 1

如果您的图形的顶点数少于 Prolog 允许的最大数量（例如 SWI-Prolog 具有无限数量），则可以将边表示为参数的索引：

可能

G = graph(a-[2],b-[3],c-[1,4],d-[2]).

然后使用arg (Edge, G, Vert-Edges) 访问邻居。

当然，任何 Prolog 都会让您使用事实来描述图形。这也是非常大的图形的首选方式。

:- dynamic edge/2.

edge(a,b).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).

编辑edge/2 关系表示也获得了自动索引的（可能很大的）好处。

更多编辑我完全忘记了RDF和语义网。真的很强大，我们正朝着那个方向前进。

Answer 2

除了@chac 建议的表示之外，您还可以考虑使用属性变量（如果您的 Prolog 系统支持它），特别是如果您需要在计算期间将更多属性附加到顶点或边时。在此表示中，您将为每个顶点使用唯一变量，如有必要，附加（使用 put_attr/3）一个属性，如“name”，并附加一个附加属性，如“edges”，例如顶点列表，或术语边缘（E，Vertex）的列表，其中 E 再次是一个变量，如果您需要跟踪影响边缘的信息，您可以将更多属性附加到该变量。

Answer 3

library(ugraphs)在许多 Prolog 系统中都有YAP、SWI、SICStus、Ciao等。（请随时在此处添加更多参考资料！）在那里，图表表示为对列表Vertex-Neighbours。乍一看，您可能会觉得这不是一个非常有效的表示。毕竟，对单个顶点的访问与列表的长度成正比。然而，直接访问顶点很少受到关注。大多数情况下，图表会一举处理——这通常会摊销访问成本。