Connected components of a graph using Prolog

Question

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?

This would probably be better if migrated to http://stackoverflow.com/questions You can ask the moderators to migrate for you. — FrustratedWithFormsDesigner, Jun 20 '13 at 16:27
If we're focusing on the graph theory aspects of this question, I think it would be on-topic for Programmers. Based upon Kilian's answer, the problem is fundamental to the graph and not necessarily related to prolog use / misuse. — , Jun 20 '13 at 17:25

score 2 · Answer 1 · answered Jun 20 '13 at 15:11

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.

Prologs with tabling, eg XSB Prolog, can also avoid some cases of infinite loops through recursion. — Joe Osborn, Jun 26 '13 at 05:35
Also: this isn't entirely on-topic, but there are other logic programming languages that _can_ express these kinds of problems without explicitly tracking visited nodes--answer set programming (I like the clasp solver myself) can calculate things like graph closure without danger of infinite loops. There's an expressiveness tradeoff--ASP can only express problems up to NP^NP and no higher--but for many applications it's quite concise, expressive, and reasonably efficient. But it's not Prolog. — Joe Osborn, Jun 26 '13 at 05:36

score 0 · Answer 2 · edited Oct 12 '15 at 09:47

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

Connected components of a graph using Prolog

2 Answers2