Prolog中的高效可变图表示？

Question

我想以有效的方式在Prolog中表示一个可变图.我将在图中搜索子集并将其替换为其他子集.

我已经设法使用数据库作为我的"图形存储".例如,我有:

:- dynamic step/2.
% step(Type, Name).

:- dynamic sequence/2.
% sequence(Step, NextStep).

然后,我使用一些规则来retract匹配我已经匹配的子集,并使用新的步骤替换它们assert.我真的很喜欢这种方法......它很容易阅读和处理,我让Prolog做了很多繁重的模式匹配工作.

我知道表示图形的另一种方法是使用节点列表和邻接连接.我见过很多使用这种方法的网站,但我有点犹豫,因为它的开销更大.

执行时间对我来说很重要,因为我自己的易于开发.

这两种方法的优缺点是什么？

Answer 1

像往常一样:使用动态数据库为您提供索引,这可能会加快(查找)速度并降低速度(断言时).一般来说,当你断言比你查找更频繁时,动态数据库并不是那么好.但主要的缺点是它也使测试和调试变得非常复杂,因为您不能孤立地测试谓词,并且需要记住数据库的当前隐式状态.在许多情况下,节点列表和邻接连接是很好的表示.我喜欢的一个不同的表示,特别是如果你需要存储节点和边的更多属性,是为每个节点使用一个变量,并使用变量attribtues(SWI-Prolog中的get_attr/3和put_attr/3)来存储边在它们上,例如[edge_to(E1,N_1),edge_to(E2,N_2),...]其中N_i是表示其他节点的变量(具有它们自己的属性),而E_j也是可以进一步附加到其上的变量如果需要,存储关于每个边缘的附加信息(重量,容量等)的属性.