Реализация графа (включает ли граф все вершины?)

Question

Попытка реализовать следующий предикат, который принимает на вход

• список списков - один список = один проверенный граф T (в виде ребер)
• сам график G (в виде ребер)

и проверяет, включает ли T все вершины G. Если это так, то (true) должно вернуть его. В основном это фильтрация списка.

Что у меня пока есть:

covb([],G).
covb([H|R],G) :-
    isItCov(G,H), covb(R,G).

isItCov([],H).
isItCov([V-W|R],H) :-
    vertex(V,H),
    vertex(W,H), 
    isItCov(R,H).

vertex(V,[V-_|G]).
vertex(V,[_-V|G]).
vertex(V,[_|G]):- vertex(V,G). 

Для covb([[a-c,c-b,c-d]],[a-b,a-c,a-d,c-d,b-c]) отлично работает (true). Для covb ([[a-c]], [a-b, a-c, a-d, c-d, b-c]) тоже отлично работает (false). У меня возникла проблема при вызове нескольких списков, таких как covb([[a-c,c-b,c-d],[a-c]],[a-b,a-c,a-d,c-d,b-c])., которые должны работать только для первого списка. На самом деле у меня есть два вопроса -

1. Почему это работает только для одного списка?
2. Я хочу вернуть элементов списков списков, которые прошли условие и вернули true (это фильтрующая часть). Как мне это сделать?

Answer 1

Прежде всего, ваша программа имеет несколько предупреждений о одноэлементных переменных. Не игнорируйте предупреждения об одноэлементных переменных. Они могут скрывать реальные ошибки. Кроме того, поскольку здесь более опытные пользователи Prolog знают, что программы с предупреждениями об одноэлементных переменных даже не стоит запускать, они (а) просто увидят предупреждения и решат, что они больше не заинтересованы в попытках помочь вам, или (б) исправят предупреждения на их стороне, но тогда по определению они будут работать над программой, которая больше не является программой, которую вы опубликовали!

Теперь на ваши вопросы.

Почему это работает только для одного списка?

Не совсем понятно, о чем вы спрашиваете здесь или чуть выше с «covb([[a-c,c-b,c-d],[a-c]],[a-b,a-c,a-d,c-d,b-c])., который должен работать только для первого».

Этот запрос завершается с ошибкой :

?- covb([[a-c,c-b,c-d],[a-c]],[a-b,a-c,a-d,c-d,b-c]).
false.

Это сводится к тестированию каждого из двух списков:

?- isItCov([a-b,a-c,a-d,c-d,b-c], [a-c,c-b,c-d]).
true .

?- isItCov([a-b,a-c,a-d,c-d,b-c], [a-c]).
false.

Первый список охватывает график, а второй - нет. В целом, ваше определение covb/2 записывается как успешное, если все списки охватывают график. Это не так, поэтому ваш запрос covb/2 не выполнен.

Это то, что вы хотели знать?

Я хочу вернуть элементы списков списков, которые прошли условие и вернули true (это фильтрующая часть). Как мне это сделать?

Вы могли видеть, есть ли в документации вашего Пролога слово "фильтр". На SWI-Prolog вы можете сделать это:

?- apropos(filter).
true.

Это укажет на предикат include/3, который, кажется, делает то, что вы хотите:

?- include(isItCov([a-b,a-c,a-d,c-d,b-c]), [[a-c,c-b,c-d],[a-c]], Covers).
Covers = [[a-c, c-b, c-d]].

Если вы хотите написать предикат фильтра для вашего конкретного приложения, оно может выглядеть примерно так:

graph_covers(_Graph, [], []).
graph_covers(Graph, [Nodes|NodesRest], Covers) :-
    (   isItCov(Graph, Nodes)
    ->  Covers = [Nodes|CoversRest]
    ;   Covers = CoversRest ),
    graph_covers(Graph, NodesRest, CoversRest).

Это похоже на ваш предикат, он просто добавляет дополнительный аргумент для сбора тех списков узлов, для которых isItCov/2 был успешным. Если это не удалось, он продолжает список , а не , содержащий этот текущий список узлов.

?- graph_covers([a-b,a-c,a-d,c-d,b-c], [[a-c,c-b,c-d],[a-c]], Covers).
Covers = [[a-c, c-b, c-d]] ;
false.