Prolog

Question

我有一个表示图形邻接矩阵的列表列表。
我正在寻找一种从中提取图形边缘的方法：

?- getEdges([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edges).
Edges = [[1,2],[2,4],[2,3]]

感谢

Answer 1

解决方案（假设有向图）类似于以下内容：

假设您正在检查邻接矩阵并且您位于特定行。您需要一个谓词来检查该行的邻接列表并过滤掉所有 0 元素，从而生成一个包含以下形式的元素的列表：

(From, To)

其中 From 对应行索引，To 对应非零列。执行此操作的一个简单谓词称为 like

?- rowEdges(Row, AdjList, Result).

所以你可以尝试这样做：

rowEdges(Row, AdjList, Result) :- edges(AdjList, 1, Row, [], Result).

edges([H|T], Column, Row, Acc, Res) :-
    NewColumn is Column + 1,
    ( H =:= 1 -> edges(T, NewColumn, Row, [(Row, Column)|Acc], Res);
      edges(T, NewColumn, Row, Acc, Res)).
edges([], _, _, Res, Res).

谓词edges/5 检查行邻接表的每个元素，同时跟踪元素的列索引。如果应该添加一条边，它将采用 (Row, Column) 的形式，这就是我们必须提供 Row 作为参数的原因。

rowEdges/3 只是提供正确的初始化，对于累加器（Acc）应该是一个空列表，对于列索引应该是 1。现在您可以将 rowEdges/3 应用于每一行，您必须通过类似的过程找到所有边。

示例：

?- rowEdges(2, [1,0,1,1,0,1], Result).
Result = [(2, 6), (2, 4), (2, 3), (2, 1)].

如果您希望边缘按列升序生成，您只需修改 rowEdges/3 以生成反向输出，因为 edges/5 使用累加器。

rowEdges(Row, AdjList, Result) :- edges(AdjList, 1, Row, Acc, Res), reverse(Res, Result).

Answer 2

另一种方法是，首先创建一个标识有效边的谓词。对于无向图，这是一个简单的谓词：

edge(M, [R,C]) :-
    nth1(R, M, Row),
    nth1(C, Row, 1),
    R =< C.               % Remove this for directed graphs

这是一个示例查询：

| ?- edge([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edge).

Edge = [1,2] ? a

Edge = [2,3]

Edge = [2,4]

(1 ms) no
| ?-

它用每条回溯标识每条边。它使用 nth1/3 谓词，即关系 nth1(N, List, Element) 表示 Element 位于 N in List，其中第一个元素是元素编号 1.

对于有向图，只需去掉R =< C条件，即可得到：

| ?- edge([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edge).

Edge = [1,2] ? a

Edge = [2,1]

Edge = [2,3]

Edge = [2,4]

Edge = [3,2]

Edge = [4,2]

(1 ms) no
| ?-

如果您想用另一种方式来表示边而不是 2 元素列表 [R,C]，您只需将子句的头部从 edge(M, [R,C]) 更改为例如 [=24] =]:

| ?- edge([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edge).

Edge = 1-2 ? a

Edge = 2-3

Edge = 2-4

(1 ms) no
| ?-

如果你想将所有边收集到一个列表中，你可以使用setof/3:

all_edges(M, Edges) :-
    setof(E, edge(M, E), Edges).

| ?- all_edges([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],E), Edges).

Edges = [1-2,2-3,2-4]

yes
| ?-

Prolog - 从邻接矩阵中提取边

Prolog - extract edges from an adjacency matrix

graph-theory

list