如何在 Prolog 中通过直接访问邻居顶点来表示有向循环图 [英] How to represent directed cyclic graph in Prolog with direct access to neighbour verticies

问题描述

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

I need to construct directed graph (at runtime) with cycles in Prolog and I am not sure know how to represent it. My requirement is that I need to get from one vertex to his neigbour in a constant time.

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

Is it possible to represent it as a tree, e.g.:

t(left_son,V,right_son)

但是如何解决循环?

t(left_son,V,right_son)

but how to solve the cycles?

我可以制作一个边列表:

I can make a list of edges:

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

OR just

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

OR just

推荐答案

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

If your graph has less vertices than max arity allowed by your Prolog (for instance SWI-Prolog has unlimited arity), you could represent the edges as indices of arguments:

可能是

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

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

then use arg(Edge, G, Vert-Edges) to access neighbours.

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

Of course any Prolog will let you describe the graph using facts. This is also the preferred way for very large graphs.

:- dynamic edge/2.

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

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

edit The edge/2 relational representation also get the (potentially large) benefits of automatic indexing.

更多编辑我完全忘记了RDF 和 语义网.真的很强大，我们正朝着这个方向努力.

more edit I totally forgot RDF and Semantic Web. Really powerful, we are going toward that.

这篇关于如何在 Prolog 中通过直接访问邻居顶点来表示有向循环图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！