Given a corner x of an undirected Graph G I would like to ask for the connected component of x, but my first try does not work as desired. Here it is:
edge( a,b ).
edge( b,a ).
edge( b,c ).
edge( c,b ).
edge( c,d ).
edge( d,c ).
connected( X,X ).
connected( X,Y ) :- edge(X,Y).
connected( X,Y ) :- + edge(X,Y), edge( X,Z ), connected( Z,Y ).
And here are my queries and the results:
| ?- connected(b,What).
What = b ? ;
What = a ? ;
What = c ? ;
no
| ?- connected(b,b).
true ? ;
true ? ;
true ? ;
no
Why is corner b not connected to corner d? Why is corner b connected to itself three times? I am afraid of other problems I will get with more complex graphs. Are there any?
3
Basically, you are using + too early (and you shouldn’t be using it in the first place).
Trace through the execution of your query, and you’ll see that the first answer comes from the first clause, and the next two from the second clause, but your third clause never succeeds. Why? Because you ask the system to prove that edge(b,Variable) is not true – but it is true, for instance via edge(b,a). The fact that your What would later be bound to another value if processing continued is irrelevant – at the moment you match it, it isn’t bound, so the edge succeeds, and therefore the + fails and stops processing.
That is also the reason why + is the wrong approach here; to process arbitrary graphs, there is no way around programming unbounded recursion, and then you need to keep track of which nodes you’ve already tried so you don’t get stuck in infinite loops. The easiest solution adds another parameter to the recursive case which does this bookkeeping.
2
First clause could remain the same if you want to prove a special case, where node X connects to X.
It is my opinion that, the clauses in the third predicate would literally look for EXACTLY ONE mutual edge, making it more hard-coded. You could make it dynamic by making it recursive.
connected( X,Z ) :-
edge(X,Y),
connected(Y,Z). % This line would fail when the program can no longer find an edge that Y connects to.%
When it does fail, (the second predicate in your answer must be here), you are asking the program to succeed with a satisfaction that it has managed to find the last node it could possibly route to.
connected ( X,Z ) :-
edge(X,Z).