Пролог - Начинающий График Связности - PullRequest
Новая
       7

Пролог - Начинающий График Связности

0 голосов
/ 28 марта 2020

Я новичок в Прологе, и у меня есть задача. Мне нужно проверить, если график подключен.

Пока у меня есть это ... 

graph(
[arc(a,b)],
[arc(a,f)],
[arc(b,c)],
[arc(c,d)],
[arc(c,e)],
[arc(e,d)],
[arc(f,c)],
[arc(f,e)],
[arc(f,g)],
[arc(g,c)],
[arc(c,a)]).


edge(X,Y):-arc(X,Y);arc(Y,X).

path(X,Y):-edge(X,Y).
path(X,Y):-edge(X,Z),path(Z,Y).

triangle(X,Y,Z):-arc(X,Y),arc(Y,Z),arc(Z,X).

cycle(X):-arc(X,Y),path(Y,X).

connectivity([]):-forall(member(edge(X,Y)),path(X,Y)).





Check:

connectivity(graph).

верхняя у меня ар c (х, у) и я Нужно проверить, все ли пары подключены.

Не могли бы вы мне помочь?

1 Ответ

1 голос
/ 28 марта 2020

Поскольку вы изменили вопрос после того, как я почти закончил, я опубликую, что бы решить вопрос до изменения, и вы сможете выяснить, как изменить его, чтобы он соответствовал вашему обновлению. 

arc(a,b).
arc(a,f).
arc(b,c).
arc(c,d).
arc(c,e).
arc(e,d).
arc(f,c).
arc(f,e).
arc(f,g).
arc(g,c).
arc(c,a).

edge(X,Y) :-
    arc(X,Y), !.
edge(X,Y) :-
    arc(Y,X).

path_prime(Visited,X,Y) :-
    \+ member(X,Visited),
    edge(X,Y), !.
path_prime(Visited,X,Y) :-
    \+ member(X,Visited),
    edge(X,Z),
    path_prime([X|Visited],Z,Y).

path(X,X) :-
    ground(X), !.

path(X,Y) :-
    path_prime([],X,Y).

nodes(Nodes) :-
    setof(A,B^arc(A,B),Starts),
    setof(B,A^arc(A,B),Ends),
    union(Starts,Ends,Nodes).

connected(X,Y) :-
    nodes(Nodes),
    member(X,Nodes),
    member(Y,Nodes),
    path(X,Y).

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

Это можно сделать с помощью 

nodes(Nodes) :-
    setof(A,B^arc(A,B),Starts),
    setof(B,A^arc(A,B),Ends),
    union(Starts,Ends,Nodes).

Обратите внимание, что как начальный, так и конечный узел AR c делаются отдельно. В частности, обратите внимание, что узел d находится только в пункте назначения ar c.

Поскольку вы включили edge(X,Y):-arc(X,Y);arc(Y,X). в свой вопрос, это указывает на то, что дуги не должны быть направленными, и поэтому можно получить циклы. Чтобы избежать циклов, список посещенных узлов добавляется в список аргументов и проверяется перед продолжением.

Поскольку не было приведено ни тестов, ни примеров правильного решения, иногда узел, связанный с самим собой, действителен и т. Д. добавлен пункт 

path(X,X) :-
    ground(X), !.

.

Это ни в коем случае не оптимальный и не лучший способ сделать это, просто дать вам что-то, что работает.

Частичный прогон 

?- connected(X,Y).
X = Y, Y = a ;
X = a,
Y = b ;
X = a,
Y = c ;
X = a,
Y = d ;
X = a,
Y = e ;
X = a,
Y = f ;
X = a,
Y = g ;
X = b,
Y = a ;
X = Y, Y = b ;
X = b,
Y = c ;

...

Как я часто комментирую, перед написанием кода вам следует сначала решить проблемы с ручкой на бумаге. Если вы не знаете точно, каким будет код, прежде чем начать ввод первой строки кода, то почему вы вводите код?

Вопросы из комментариев:

И setof, union, что это значит? Я просто beigneer, и я не понимаю этот язык и предикаты.

setof / 3 собирает все значения из arc/2. Поскольку требуется только одно из этих двух значений, ^ указывает setup / 3 не связывать переменную в цели или в терминах для начинающих просто игнорировать значения из переменной.

union / 3 просто объединяет наборы to в один набор; помните, что набор будет иметь только уникальные значения.

...