实现Prolog谓词：筛选包含图G全部顶点的测试图列表

首先，先明确你的需求：给定一个测试图列表（每个测试图是边的列表）和一个目标图（边的列表），筛选出所有包含目标图全部顶点的测试图。

现有代码的正确部分 #

你的vertex/2和isItCov/2逻辑是正确的：

• vertex(V, Graph)：正确实现了检查顶点V是否存在于图Graph（边列表）中的功能，通过匹配边的两个端点或递归遍历剩余边来验证。
• isItCov(G, H)：通过遍历目标图G的每条边，检查两个端点都在测试图H中，从而确保G的所有顶点都被H包含——这个逻辑是对的，因为目标图的所有顶点就是其边的端点集合。

需要调整的部分 #

你的covb/2谓词没有实现筛选功能，而是在检查整个测试图列表中的每个图都满足条件。我们需要改写它，让它能从列表中挑出符合条件的测试图。

完善后的完整代码 #

% 主谓词：筛选出测试图列表中所有包含目标图全部顶点的图
% 参数：TestGraphs（输入：测试图列表）, TargetGraph（输入：目标图）, ResultGraphs（输出：符合条件的图列表）
filter_covering_graphs([], _, []).
filter_covering_graphs([TestGraph|Rest], TargetGraph, [TestGraph|ResultRest]) :-
    is_it_cov(TargetGraph, TestGraph),
    filter_covering_graphs(Rest, TargetGraph, ResultRest).
filter_covering_graphs([TestGraph|Rest], TargetGraph, ResultRest) :-
    \+ is_it_cov(TargetGraph, TestGraph),
    filter_covering_graphs(Rest, TargetGraph, ResultRest).

% 检查目标图的所有顶点都存在于测试图中
is_it_cov([], _).
is_it_cov([V-W|GEdges], TestGraph) :-
    vertex(V, TestGraph),
    vertex(W, TestGraph),
    is_it_cov(GEdges, TestGraph).

% 检查顶点V是否在图（边列表）中存在
vertex(V, [V-_|_]).
vertex(V, [_-V|_]).
vertex(V, [_|RestEdges]) :-
    vertex(V, RestEdges).

代码说明 #

1. filter_covering_graphs/3：

   • 空输入列表对应空输出列表。
   • 如果当前测试图满足顶点覆盖条件（is_it_cov返回真），就把它加入结果列表，再递归处理剩余的测试图。
   • 如果不满足条件，就跳过该图，直接递归处理剩余列表。

2. is_it_cov/2：

   • 空目标图默认满足条件（因为没有顶点需要覆盖）。
   • 对目标图的每条边，验证两个端点都在测试图中，再递归处理剩余边。

3. vertex/2：

   • 直接匹配顶点作为边的第一个/第二个端点。
   • 如果当前边不匹配，就递归遍历剩余边。

验证示例 #

我们用一个实际例子测试：

% 测试图列表：三个不同的图
TestGraphs = [
    [a-b, b-c],  % 包含顶点a,b,c
    [a-c, d-e],  % 包含顶点a,c,d,e
    [x-y]        % 包含顶点x,y
]
% 目标图：包含顶点a和c
TargetGraph = [a-c]

% 查询
?- filter_covering_graphs(TestGraphs, TargetGraph, Result).
Result = [[a-b, b-c], [a-c, d-e]] ;
false.

结果符合预期：前两个测试图都包含a和c，第三个不包含，所以被排除。

再测试空目标图的情况：

?- filter_covering_graphs([[a-b], [x-y]], [], Result).
Result = [[a-b], [x-y]] ;
false.

所有测试图都符合条件，因为空目标图没有顶点需要覆盖。

内容的提问来源于stack exchange，提问作者user7303261