1

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?

Improve this question
3
  • \+ edge(X,Y) - there's no edge! :O Commented Jun 20, 2013 at 15:10
  • 1
    This would probably be better if migrated to stackoverflow.com/questions You can ask the moderators to migrate for you. Commented Jun 20, 2013 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. Commented Jun 20, 2013 at 17:25

2 Answers 2

Reset to default
2

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.

Improve this answer
2
  • Prologs with tabling, eg XSB Prolog, can also avoid some cases of infinite loops through recursion. Commented Jun 26, 2013 at 5:35
  • 1
    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. Commented Jun 26, 2013 at 5:36
0

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).
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.