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

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

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

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

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


graph-traversal prolog meta-predicate transitive-closure
person Sam    schedule 17.11.2014    source источник
comment
@false: ребро между 4 и 5 намеренно имеет несвязный граф. Кстати, это также пример того, что должен обрабатывать closure0, но я не вижу, как его можно расширить без особых сложностей...   -  person CapelliC    schedule 17.11.2014
comment
@CapelliC: Я согласен, что мой комментарий неоднозначен, я хотел сослаться на то, что сказал @ Sam. Буду переписывать..   -  person false    schedule 17.11.2014
comment
[с пояснением] Итак, поскольку между 3 и 4 нет разницы, это должно потерпеть неудачу. Почему между 3 и 4 должно быть преимущество? Преимущество между 5 и одним из 1,2,3 было бы таким же хорошим. Кратко: непонятно, как вы определяете набор вершин.   -  person false    schedule 17.11.2014

Ответы (2)


arrow_upward
2
arrow_downward

Решение 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].
person Wouter Beek    schedule 17.11.2014
comment
Это closure0/3 не closure/3! Пожалуйста, не переименовывайте его! - person false; 17.11.2014
comment
@false Да, соответственно изменил мой ответ. Является ли суффикс 0 каким-то соглашением / что это значит? - person Wouter Beek; 17.11.2014
comment
closure/3 обычно называют переходным замыканием без возвратной части. - person false; 17.11.2014
comment
Ах, так это в основном для предотвращения вмешательства в существующие библиотеки. Кроме того, 0 может относиться к рефлексивной замыкающей части, то есть обходу глубины 0 в графе. - person Wouter Beek; 17.11.2014
comment
Имя не подходило. См. это для closure/3. Если у вас есть лучшее имя, добавьте его к моему вопросу. - person false; 17.11.2014

arrow_upward
2
arrow_downward

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

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

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).
person false    schedule 17.11.2014