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