Prolog比较变量的方法
Prolog ways to compare variables
我试图在 Prolog 中实现一些图形算法。我想出了一个想法，使用统一从图结构构建树：
图表定义如下：
Vertex-Variable 对的列表，其中 Vertex 是表示顶点的常量，Variable 是对应的变量，将用作 "reference" 到顶点。例如：
[a-A, b-B, c-C, d-D]
VertexVar-NeighboursList 对的列表，其中 VertexVar 和 NeighboursList 中的单个邻居是 "reference variables"。例如：
[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 == Y 是 true。共享相同邻居的顶点也会出现同样的问题。例如U-[A, B] 和 V-[A, B].
所以我的问题是：有没有其他比较变量的方法可以帮助我解决这个问题？比较 "the variables themselves" 而不是内容的东西，比如比较过程编程语言中的地址？或者这会不会过于程序化并破坏 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 系统在支持循环数据结构方面有所不同，但这并不妨碍您利用这个想法。
您的设计的唯一问题是节点完全由（可能深度嵌套和循环）数据结构标识，该数据结构描述可从其到达的子图。结果是
- 具有相同后代的两个节点无法区分
- 检查两个 "similar looking" 子图是否相同可能非常昂贵
一个简单的解决方法是在您的数据结构中包含一个唯一节点标识符（例如名称或编号）。要使用您的示例（稍作修改以使其更有趣）：
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 的一些图问题，我想我会再尝试一下这个递归数据结构，并提出以下谓词来从边缘列表构造这个数据结构：
数据结构的"manual"创建，如@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), ...]) 表示一个顶点及其邻居。
更"user-friendly"输入格式：
[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.
这些谓词的二进制版本假定，每个顶点只能从边列表中获得 - 图中没有 "edge-less" 个顶点。三元版本为这些情况采用额外的顶点列表。
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 可以在恒定时间内 "assigned"（初始化），例如，在图形的偏序中，带有有关顶点位置的信息。所以这可以用作输出。 （有时在 Prolog 注释中用 +- 表示——一个未初始化的变量作为输入项的一部分，尚未被使用的谓词初始化并提供输出。）
我试图在 Prolog 中实现一些图形算法。我想出了一个想法，使用统一从图结构构建树：
图表定义如下：
Vertex-Variable对的列表，其中Vertex是表示顶点的常量，Variable是对应的变量，将用作 "reference" 到顶点。例如：[a-A, b-B, c-C, d-D]VertexVar-NeighboursList对的列表，其中VertexVar和NeighboursList中的单个邻居是 "reference variables"。例如：[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 == Y 是 true。共享相同邻居的顶点也会出现同样的问题。例如U-[A, B] 和 V-[A, B].
所以我的问题是：有没有其他比较变量的方法可以帮助我解决这个问题？比较 "the variables themselves" 而不是内容的东西，比如比较过程编程语言中的地址？或者这会不会过于程序化并破坏 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 系统在支持循环数据结构方面有所不同，但这并不妨碍您利用这个想法。
您的设计的唯一问题是节点完全由（可能深度嵌套和循环）数据结构标识，该数据结构描述可从其到达的子图。结果是
- 具有相同后代的两个节点无法区分
- 检查两个 "similar looking" 子图是否相同可能非常昂贵
一个简单的解决方法是在您的数据结构中包含一个唯一节点标识符（例如名称或编号）。要使用您的示例（稍作修改以使其更有趣）：
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 的一些图问题，我想我会再尝试一下这个递归数据结构，并提出以下谓词来从边缘列表构造这个数据结构：
数据结构的"manual"创建，如@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), ...]) 表示一个顶点及其邻居。
更"user-friendly"输入格式：
[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.
这些谓词的二进制版本假定，每个顶点只能从边列表中获得 - 图中没有 "edge-less" 个顶点。三元版本为这些情况采用额外的顶点列表。
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 可以在恒定时间内 "assigned"（初始化），例如，在图形的偏序中，带有有关顶点位置的信息。所以这可以用作输出。 （有时在 Prolog 注释中用 +- 表示——一个未初始化的变量作为输入项的一部分，尚未被使用的谓词初始化并提供输出。）