3

我试图在 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-NeighbourListVertexVar = 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_1and S_2（又名band c）X = [something, Y], Y = [something, X], X == Y原样true。同样的问题也会出现在共享相同邻居的顶点上。例如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).

\==运营商并不是我真正想要的，它会产生这些冲突。

4

2 回答 2

4

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)
于 2019-04-03T16:18:07.090 回答
0

谢谢@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.

whereedgeTo(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 注释中表示 - 作为输入项的一部分的未初始化变量，尚未由使用的谓词初始化并提供输出。）

于 2019-06-19T10:05:48.690 回答