Определить граф связности в Прологе - PullRequest
Новая
       69

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

1 голос
/ 19 февраля 2011

Я продолжаю некоторые исследования в решетках и полурешетках и вдруг у меня возникает этот вопрос.

По сути, у нас есть RelationList из [a, b] пар, что означает, что (a, b) является ребром. Теперь мы должны знать, является ли граф сформированным из этого RelationList 1-связностью или нет. Кстати, у нас есть упорядоченный граф, поэтому важен порядок (a, b). 

clear_link(X, Y, RelationList) :-
    (member([X,Y], RelationList)
    ;
    member([Y,X], RelationList)),
    X =\= Y.

linked(X, Y, RelationList) :-
    clear_link(X, Y, RelationList),
    !.
linked(X, Y, RelationList) :-
    clear_link(X, Z, RelationList),
    linked(Z, Y, RelationList).

simple_connect(RelationList, E) :-
    forall((member(X, E),
    member(Y, E), X < Y),
    linked(X, Y, RelationList)).

Но для 6-элементного графа у меня есть стекопоток. 

?- simple_connect([[2,1],[2,3],[4,3],[4,5],[6,5]],[1,2,3,4,5,6]).
ERROR: Out of local stack

Я неправильно это определяю?

1 Ответ

2 голосов
/ 19 февраля 2011

Я исправил некоторые. Теперь все нормально 

clear_link(X, Y, RelationList) :-
    member([X,Y], RelationList),
    X =\= Y.

linked(X, Y, RelationList) :-
    clear_link(X, Y, RelationList),
    !.
linked(X, Y, RelationList) :-
    clear_link(X, Z, RelationList),
    linked(Z, Y, RelationList),
    !.

simple_connect(RelationList, E) :-
    forall((member(X, E),
    member(Y, E), X < Y),
    linked(X, Y, RelationList)).

connective_graph(RelationList, E) :-
    findall(Relation, (
        member(X, RelationList),
        sort(X, Relation)
    ),SortRelationList),
    simple_connect(SortRelationList, E).

И 

?- connective_graph([[2,1],[2,3],[4,3],[4,5],[6,5]],[1,2,3,4,5,6]).
true.

?- connective_graph([[2,1],[4,3],[4,5],[6,5]],[1,2,3,4,5,6]).
false.

Правильный ответ (копия в пост) 

connected(X, Y, RelationList) :-
    (member([X,Y], RelationList);
    member([Y,X], RelationList)).

path(X, Y, RelationList, Path) :-
    travel(X, Y, RelationList, [X], ReversePath),
    reverse(ReversePath, Path),!.

travel(X, Y, RelationList, Point, [Y | Point]) :-
    connected(X, Y, RelationList).
travel(X, Y, RelationList, Visited, Path) :-
    connected(X, Z, RelationList),
    Z =\= Y,
    \+member(Z, Visited),
    travel(Z, Y, RelationList, [Z|Visited], Path).

connective_graph(RelationList, E) :-
    forall((member(X, E),
        member(Y, E),
        X < Y)
    ,path(X,Y,RelationList,_)).
...