如何在Prolog中表示直接访问邻居verticies的有向循环图
Ond*_*unc 4 prolog cyclic-graph
我需要在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->[]] 但是如何在搜索邻居时避免在列表上调用函数"成员",这会花费线性时间？
谢谢你的帮助
如果您的图形具有的顶点少于Prolog允许的最大值(例如SWI-Prolog具有无限的arity),则可以将边表示为参数的索引:
可能 
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和语义Web.非常强大,我们正朝着这个方向发展.
除了@chac建议的表示之外,您还可以考虑使用属性变量(如果您的Prolog系统支持它),尤其是在计算过程中需要将其他属性附加到顶点或边缘时.在此表示中,您将为每个顶点使用唯一变量,必要时附加(使用put_attr/3)诸如"name"的属性,并附加"edge"之类的附加属性,例如可以是顶点列表,或者一个术语列表edge(E,Vertex),其中E再次是一个变量,如果需要跟踪影响边缘的信息,可以附加其他属性.
- 这看起来很有趣.一个小例子怎么样？ (2认同)
- [comp.lang.prolog](http://groups.google.com/group/comp.lang.prolog/topics?lnk=srg)中讨论的示例是查找有向图的强连接组件.发布的解决方案如下:[scc.pl](http://www.logic.at/prolog/scc.pl).有关最大匹配和最大流算法等更多示例,请参阅SWI-Prolog中的库(clpfd).这些算法(也是SCC示例)都需要顶点的附加信息,例如,它是否在堆栈中,是否被访问等,并且属性变量可以让您轻松附加和修改这些属性. (2认同)