Prolog 中的图形表示

Question

考虑下图

并且它由以下 Prolog 术语描述：

graph([connected(a,[b,c]), connected(b,[a,c]), connected(c,[a,b,d]), connected(d,[c]) ]).

我想定义一个谓词，将上述连接转换为相应对的列表。换句话说，一个谓词产生 [[a,b],[a,c],[b,c],[c,d]] 上面的术语图。

你能告诉我怎么做吗？

到目前为止，我的尝试如下：

将 2 个相邻顶点映射到对：

map2ne(adjacent(H,[K|T]),Pair) :-
    append([H],[K],L),
    append([H],T,M),
    append([L],[M],Pair).

这运行正常。

将 3 个相邻顶点映射到对：

map3n(adjacent(H,[K,L|T]),Pair) :-
    append([H],[K],A1),
    append([H],[L],A2),
    append([A1],[A2],Z),
    append([H],T,M),
    append(Z,[M],Pair).

这也运行正常。

但是当我尝试将它扩展到 n-neighbor 顶点时，它失败了:

mapmany(adjacent(H, [K|_]),Pair) :-
    append([H],[K],L),
    append(L,[],Pair),
    mapmany(adjacent(H,[K|_]),M),
    append(M,Pair,Pair).

下面的也失败了，这是为了将许多 n-neighbor 顶点映射到对：

mapping(Map,Pairs) :-
    select(X,Map,Y),
    mapmany(X,PairX),
    append([PairX],Pairs),
    mapping(Y,Pairs).

Answer 1

你的代码缺陷太多：

由graph/1定义的邻接表由connected(Vertex, Neighbors)形式的项组成；但是，您的代码处理 adjacent(Vertex, Neighbors).
Predicate append/3 不应用于创建 all 列表；例如，您应该使用 L = [H, K].

append([H], [K], L)

在 Prolog 中，将一对项目 V 和 W 表示为 V-W 比 [V,W].
根据您对给定示例的预期答案（即 [a-b,a-c,b-c,c-d]），单个项 V-W（即 {V,W}）表示两个边 (V,W)和（W，V）。因此，为避免冗余，您必须专门选择 V-W 或 W-V 来输入您的答案（不失一般性，您可以选择 V 在 W 之前的术语） .

要创建边，您可以执行以下操作：

edge(V, W, Edge) :-
    (   V @< W
    ->  Edge = V-W
    ;   Edge = W-V ).

示例：

?- edge(a, b, Edge).
Edge = a-b.

?- edge(b, a, Edge).
Edge = a-b.

要创建连接顶点 V 到其邻居 Ns 的所有边而不重复，只需问：

?- V=a, Ns=[b,c,d], setof(E, W^Ns^(member(W,Ns), edge(V,W,E)), Edges).
V = a,
Ns = [b, c, d],
Edges = [a-b, a-c, a-d].

注意构造 Var^Goal 告诉 setof/3 不要在 Goal 中绑定变量 Var （换句话说，表示 Var 是 存在量化).

概括这个想法，我们有：

graph_edges(Graph, Edges) :-
    setof( Edge,
           V^Ns^W^( member(connected(V, Ns), Graph),
                    member(W, Ns),
                    edge(V, W, Edge)),
           Edges ).

graph([connected(a, [b, c]),
       connected(b, [a, c]),
       connected(c, [a, b, d]),
       connected(d, [c])]).

示例：

?- graph(G), graph_edges(G, E).
G = [connected(a, [b, c]), connected(b, [a, c]), connected(c, [a, b, d]), connected(d, [c])],
E = [a-b, a-c, b-c, c-d].

图书馆图表

在 SWI-Prolog 中，一个简单的解决方案是使用 library(ugraphs) 中的谓词 edges/2。不过要小心，因为谓词 edge/2 所基于的无向图的表示与您正在考虑的不同（library(ugraphs) 中的无向图由顶点对列表表示，其中这些对中顶点的顺序很重要）。例如：

?- edges([a-[b,c], b-[a,c], c-[a,b,d], d-[c]], E).
E = [a-b, a-c, b-a, b-c, c-a, c-b, c-d, d-c].

Answer 2

如果您打算使用基于 setof/3 的解决方案，我强烈建议您定义一个辅助谓词。这个谓词应该准确定义我们想要的一组。当我们想要定义“图中所有边的集合”时，数学上我们可能会说“Edges 是所有 Edge 项的集合，其中 Edge 是 Graph".

我们可以很直接的写成这样：

graph_edges(Graph, Edges) :-
    setof( Edge,
           graph_edge(Graph, Edge),
           Edges ).

它仍然定义 graph_edge/2 本身。这个核心可以从slago的解决方案中提炼出来：

graph_edge(Graph, Edge) :-
    member(connected(V, Ns), Graph),
    member(W, Ns),
    edge(V, W, Edge).

将 this 作为单独的谓词的优点是：

setof 调用更易于阅读
谓词本身有一个很好的描述性名称
可以单独测试谓词
谓词可以重复使用
在任何地方都没有 ^ 符号，这在 Prolog 中没有任何意义，除了使不使用辅助谓词的 setof 调用变得复杂
不用担心“存在量化”，它在 Prolog 中没有任何意义，除了使不使用辅助谓词的 setof 调用变得复杂

Prolog 中的图形表示

Graph representations in Prolog

list

graph

prolog

swi-prolog

adjacency-list