Определение, связан ли граф в прологе

Question

Мне нужно сделать предикат isConnected/1 он принимает граф в качестве аргумента и определяет, существует ли ненаправленный путь между парами.

Предположим, у меня есть список ребер (где G это график):

isEdge(G,1,2).
isEdge(G,2,3).
isEdge(G,4,5).

Так что, поскольку между 3 и 4 нет грани, это должно провалиться.
Как бы я подошел к этой проблеме? Должен ли я пройти через каждое ребро и записать ребра в списке? или есть лучший подход для этого?

Answer 1

Предполагая, что это продолжение этого вопроса:

Во-первых, вам нужно определить, что значит быть подключенным:

connected_to(R_2, A,B) :-
   (  call(R_2, A,B)
   ;  call(R_2, B,A)
   ).

Затем вам нужно определить множество узлов. Обычно набор узлов дается, но кажется, что вы хотите, чтобы они были определены неявно через все ребра:

rel_nodes(R_2, Nodes) :-
   setof(Node, Next^connected_to(R_2, Node,Next), Nodes).

Теперь соединение означает, что каждый узел связан со всеми остальными узлами.

is_connected(R_2) :-
   rel_nodes(R_2, Vs),
   maplist({R_2,Vs}+\V0^setof(V, closure0(connected_to(R_2), V0,V), Vs), Vs).

(Все это предполагает, что узлы на самом деле являются основными терминами.)

Вот все отсутствующие объявления мета-предикатов:

:- meta_predicate connected_to(2,?,?), rel_nodes(2,?), is_connected(2).

Answer 2

Решение 1. Использование библиотеки

Это легко, если вы используете библиотеку теории графов. Сначала я перепишу ваш график, используя S-представление:

[1-[2],2-[1,3],3-[2],4-[5],5-[4]]

Тогда я буду использовать библиотеку ugraph включены в SWI-Prolog ( спасибо Ричарду О'Кифу и Витору Сантосу Коста):

?- use_module(library(ugraph)).
?- G = [1-[2],2-[1,3],3-[2],4-[5],5-[4]], vertices(G, Vs), member(V, Vs), reachable(V, G, Ws).
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 1,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 2,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 3,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 4,
Ws = [4, 5] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 5,
Ws = [4, 5].

Решение 2: "Сделай сам"

Вместо того, чтобы полагаться на существующие библиотеки, вы также можете реализовать это самостоятельно различными способами (очень рекомендуется, если вы хотите стать лучшим программистом!). Одним из способов реализации этой формы с нуля является использование closure0/3, который реализует рефлексивно-транзитивное замыкание над двоичным предикатом (созданным пользователем SO - false).

Если вы добавите соответствующие ребра в вашу базу данных:

edge(1,2).
edge(2,1).
edge(2,3).
edge(3,2).
edge(4,5).
edge(5,4).

... теперь вы можете запросить:

?- member(V, [1,2,3,4,5]), findall(W, closure0(edge, V, W), Ws).
V = 1,
Ws = [1, 2, 3] ;
V = 2,
Ws = [2, 1, 3] ;
V = 3,
Ws = [3, 2, 1] ;
V = 4,
Ws = [4, 5] ;
V = 5,
Ws = [5, 4].