我试图在Prolog中实现一些图形算法。我想出了一个想法，使用统一从图结构构建一棵树：
该图将定义如下：
-
Vertex-Variable对的列表，其中Vertex是表示顶点的常量，Variable是相应的变量，将用作顶点的"引用"。 例如：[a-A, b-B, c-C, d-D] -
VertexVar-NeighboursList对的列表，其中VertexVar和NeighboursList中的单个邻居是"参考变量"。 例如：[A-[B, C, D], B-[A, C], C-[A, B], D-[A]]的意思是b、c、d是a等的邻居。
然后，在一些可以使用从原始图构建的某种树的图算法(如搜索组件或简单的DFS/BFS等)之前，可以使用一些谓词，如unify_neighbours将VertexVar-NeighbourList对统一为VertexVar = NeighboursList。之后，顶点变量可以解释为其邻居的列表，其中每个邻居又是其邻居的列表。
因此，这将在遍历图形时产生良好的性能，因为不需要对图形中的每个顶点进行线性搜索某些顶点及其邻居。
但我的问题是：如何比较这些顶点变量？(检查它们是否相同。我尝试使用A == B，但存在一些冲突。对于上面的例子，(使用unify_neighbours谓词)Prolog在内部将图形解释为：
[a-[S_1, S_2, S_3], b-S_1, c-S_2, d-S_3]
哪里：
S_1 = [[S_1, S_2, S_3], S_2]
S_2 = [[S_1, S_2, S_3], S_1]
S_3 = [[S_1, S_2, S_3]]
问题出在S_1和S_2(又名b和c)上，因为X = [something, Y], Y = [something, X], X == Ytrue。共享相同邻居的顶点也会面临同样的问题。例如U-[A, B]和V-[A, B].
所以我的问题是：有没有其他方法可以比较变量，可以帮助我解决这个问题？比较"变量本身"而不是内容的东西，比如比较过程编程语言中的地址？还是这太程序化了，打破了Prolog的陈述性想法？
例
graph_component(Vertices, Neighbours, C) :-
% Vertices and Neighbours as explained above.
% C is some component found in the graph.
vertices_refs(Vertices, Refs),
% Refs are only the variables from the pairs.
unify_neighbours(Neighbours), % As explained above.
rec_(Vertices, Refs, [], C).
rec_(Vertices, Refs, Found, RFound) :-
% Vertices as before.
% Refs is a stack of the vertex variables to search.
% Found are the vertices found so far.
% RFound is the resulting component found.
[Ref|RRest] = Refs,
vertices_pair(Vertices, Vertex-Ref),
% Vertex is the corresponding Vertex for the Ref variable
not(member(Vertex, Found)),
% Go deep:
rec_(Vertices, Ref, [Vertex|Found], DFound),
list_revpush_result([Vertex|Found], DFound, Found1),
% Go wide:
rec_(Vertices, RRest, Found1, RFound).
rec_(Vertices, Refs, Found, []) :-
% End of reccursion.
[Ref|_] = Refs,
vertices_pair(Vertices, Vertex-Ref),
member(Vertex, Found).
这个例子并不真正有效，但它就是这个想法。(另外，检查是否找到顶点是线性完成的，所以性能仍然不好，但这只是为了演示。现在，找到变量的相应顶点的谓词实现为：
vertices_pair([Vertex-Ref|_], Vertex-Ref).
vertices_pair([_-OtherRef|Rest], Vertex-Ref) :-
Ref == OtherRef,
vertices_pair(Rest, Vertex-Ref).
==运算符并不是我真正想要的，它会产生这些冲突。
Prolog的一个内在特征是，一旦你把一个变量绑定到一个术语，它就变得与术语本身没有区别。 换句话说，如果将两个变量绑定到同一项，则有两个相同的东西，并且无法区分它们。
应用于您的示例：一旦您将每个顶点变量与相应的邻居列表统一起来，所有变量都消失了：您只剩下一个嵌套的(很可能是循环的)数据结构，由列表列表组成......
但正如您所建议的，嵌套结构是一个有吸引力的想法，因为它使您可以直接访问相邻节点。 尽管Prolog系统在支持循环数据结构方面有所不同，但这并不需要阻止您利用这个想法。
您的设计的唯一问题是节点纯粹由(可能是深度嵌套和循环的)数据结构来标识，该结构描述了可从它访问的子图。 其后果是
- 具有相同后代的两个节点无法区分
- 检查两个"外观相似"的子图是否相同可能非常昂贵
解决此问题的一种简单方法是在数据结构中包含唯一的节点标识符(例如名称或编号)。使用您的示例(稍作修改以使其更有趣)：
make_graph(Graph) :-
Graph = [A,B,C,D],
A = node(a, [C,D]),
B = node(b, [A,C]),
C = node(c, [A,B]),
D = node(d, [A]).
然后，您可以使用该标识符来检查匹配的节点，例如在深度优先遍历中：
dfs_visit_nodes([], Seen, Seen).
dfs_visit_nodes([node(Id,Children)|Nodes], Seen1, Seen) :-
( member(Id, Seen1) ->
Seen2 = Seen1
;
writeln(visiting(Id)),
dfs_visit_nodes(Children, [Id|Seen1], Seen2)
),
dfs_visit_nodes(Nodes, Seen2, Seen).
示例运行：
?- make_graph(G), dfs_visit_nodes(G, [], Seen).
visiting(a)
visiting(c)
visiting(b)
visiting(d)
G = [...]
Seen = [d, b, c, a]
Yes (0.00s cpu)
谢谢，@jschimpf，你的答案。它为我澄清了很多事情。我刚刚回到Prolog的一些图形问题，并认为我会再次尝试这种递归数据结构，并提出了以下谓词来从边缘列表中构造此数据结构：
数据结构的"手动"创建，如@jschimpf所建议的：
my_graph(Nodes) :-
Vars = [A, B, C, D, E],
Nodes = [
node(a, [edgeTo(1, B), edgeTo(5, D)]),
node(b, [edgeTo(1, A), edgeTo(4, E), edgeTo(2, C)]),
node(c, [edgeTo(2, B), edgeTo(6, F)]),
node(d, [edgeTo(5, A), edgeTo(3, E)]),
node(e, [edgeTo(3, D), edgeTo(4, B), edgeTo(1, F)]),
node(e, [edgeTo(1, E), edgeTo(6, C)])
],
Vars = Nodes.
其中edgeTo(Weight, VertexVar)表示某个顶点的边，其权重与其相关联。权重只是为了表明可以针对任何其他信息进行自定义。node(Vertex, [edgeTo(Weight, VertexVar), ...])表示与其相邻的顶点。
更"用户友好"的输入格式：
[edge(Weight, FromVertex, ToVertex), ...]
使用可选的顶点列表：
[Vertex, ...]
对于上面的示例：
[edge(1, a, b), edge(5, a, d), edge(2, b, c), edge(4, b, e), edge(6, c, f), edge(3, d, e), edge(1, e, f)]
此列表可以转换为具有以下谓词的递归数据结构：
% make_directed_graph(+Edges, -Nodes)
make_directed_graph(Edges, Nodes) :-
vertices(Edges, Vertices),
vars(Vertices, Vars),
pairs(Vertices, Vars, Pairs),
nodes(Pairs, Edges, Nodes),
Vars = Nodes.
% make_graph(+Edges, -Nodes)
make_graph(Edges, Nodes) :-
vertices(Edges, Vertices),
vars(Vertices, Vars),
pairs(Vertices, Vars, Pairs),
directed(Edges, DiretedEdges),
nodes(Pairs, DiretedEdges, Nodes),
Vars = Nodes.
% make_graph(+Edges, -Nodes)
make_graph(Edges, Nodes) :-
vertices(Edges, Vertices),
vars(Vertices, Vars),
pairs(Vertices, Vars, Pairs),
directed(Edges, DiretedEdges),
nodes(Pairs, DiretedEdges, Nodes),
Vars = Nodes.
% make_directed_graph(+Vertices, +Edges, -Nodes)
make_directed_graph(Vertices, Edges, Nodes) :-
vars(Vertices, Vars),
pairs(Vertices, Vars, Pairs),
nodes(Pairs, Edges, Nodes),
Vars = Nodes.
这些谓词的二进制版本假设每个顶点只能从边列表中获取 - 图中没有"无边"顶点。三元版本正是针对这些情况的附加顶点列表。
make_directed_graph假定输入边是定向的，make_graph假定它们是无向的，因此它会在相反的方向上创建额外的有向边：
% directed(+UndirectedEdges, -DiretedEdges)
directed([], []).
directed([edge(W, A, B)|UndirectedRest], [edge(W, A, B), edge(W, B, A)|DirectedRest]) :-
directed(UndirectedRest, DirectedRest).
要从边列表中获取所有顶点：
% vertices(+Edges, -Vertices)
vertices([], []).
vertices([edge(_, A, B)|EdgesRest], [A, B|VerticesRest]) :-
vertices(EdgesRest, VerticesRest),
+ member(A, VerticesRest),
+ member(B, VerticesRest).
vertices([edge(_, A, B)|EdgesRest], [A|VerticesRest]) :-
vertices(EdgesRest, VerticesRest),
+ member(A, VerticesRest),
member(B, VerticesRest).
vertices([edge(_, A, B)|EdgesRest], [B|VerticesRest]) :-
vertices(EdgesRest, VerticesRest),
member(A, VerticesRest),
+ member(B, VerticesRest).
vertices([edge(_, A, B)|EdgesRest], VerticesRest) :-
vertices(EdgesRest, VerticesRest),
member(A, VerticesRest),
member(B, VerticesRest).
要为每个顶点构造未初始化的变量：
% vars(+List, -Vars)
vars([], []).
vars([_|ListRest], [_|VarsRest]) :-
vars(ListRest, VarsRest).
要配对顶点和顶点变量：
% pairs(+ListA, +ListB, -Pairs)
pairs([], [], []).
pairs([AFirst|ARest], [BFirst|BRest], [AFirst-BFirst|PairsRest]) :-
pairs(ARest, BRest, PairsRest).
构造递归节点：
% nodes(+Pairs, +Edges, -Nodes)
nodes(Pairs, [], Nodes) :-
init_nodes(Pairs, Nodes).
nodes(Pairs, [EdgesFirst|EdgesRest], Nodes) :-
nodes(Pairs, EdgesRest, Nodes0),
insert_edge(Pairs, EdgesFirst, Nodes0, Nodes).
首先，初始化每个顶点的空节点列表：
% init_nodes(+Pairs, -EmptyNodes)
init_nodes([], []).
init_nodes([Vertex-_|PairsRest], [node(Vertex, [])|NodesRest]) :-
init_nodes(PairsRest, NodesRest).
然后逐个插入边缘：
% insert_edge(+Pairs, +Edge, +Nodes, -ResultingNodes)
insert_edge(Pairs, edge(W, A, B), [], [node(A, [edgeTo(W, BVar)])]) :-
vertex_var(Pairs, B, BVar).
insert_edge(Pairs, edge(W, A, B), [node(A, EdgesTo)|NodesRest], [node(A, [edgeTo(W, BVar)|EdgesTo])|NodesRest]) :-
vertex_var(Pairs, B, BVar).
insert_edge(Pairs, edge(W, A, B), [node(X, EdgesTo)|NodesRest], [node(X, EdgesTo)|ResultingNodes]) :-
A = X,
insert_edge(Pairs, edge(W, A, B), NodesRest, ResultingNodes).
获取给定顶点的顶点变量：(这实际上在两个方向上都有效。
% vertex_var(+Pairs, +Vertex, -Var)
vertex_var(Pairs, Vertex, Var) :-
member(Vertex-Var, Pairs).
```Prolog
This, of course, brings additional time overhead, but you can do this once and then just copy this data structure every time you need to perform some graph algorithm on it and access neighbours in constant time.
You can also add additional information to the `node` predicate. For example:
```Prolog
node(Vertex, Neighbours, OrderingVar)
例如，未初始化的变量OrderingVar可以在常量时间内"分配"(初始化)，其中包含有关图形部分顺序中顶点位置的信息。因此，这可以用作输出。(有时由Prolog注释中的+-表示 - 作为输入项一部分的未初始化变量，尚未由使用的谓词初始化并提供输出。