prologalgebramathematical-lattices

Define a connectivity graph in Prolog


I'm continuing some researches in lattices and semilattices and suddenly having this question.

Basically, we have a RelationList of [a,b] pairs, which means that (a,b) is an edge. Now we should know, is a graph formed by this RelationList 1-connectivity or not. By the way, we have an ordered graph, so order of (a,b) is important.

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)).

But, for 6-element graph I have stackoverflow.

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

Am I defining it wrong?


Solution

  • I've correct some. Now it's fine

    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).
    

    And

    ?- 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.
    

    Right answer (copy to post)

    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,_)).