Getting all nodes that have atleast 2 nodes connected to them

Question

Having some issues with a Prolog question:

The following clauses represent a directed graph, where nodes are atoms, and edges are denoted by the connected predicate. Given that the following clauses are in the database, answer the two questions below.

connected(a,b).
connected(b,d).
connected(b,e).
connected(b,f).
connected(a,c).
connected(c,f).
connected(c,g).
connected(h,c).
path(X,Y) :- connected(X,Y).
path(X,Z) :- connected(X,Y), path(Y,Z).

Show the Prolog query that returns all nodes having two or more different incoming edges (i.e., at least two different nodes are connected to it). Also, show the result of entering the query (asking for every solution). Your query may return the same node multiple times, and may printout the values of other variables in the query. The variable denoting the node in question should be called DNode.

So far I have:

path(DNode,__) , path(__,DNode).

But that only give me b and c
I think the letters with more than one nodes are a, b, c, f.
I tried this to get a, b and c:

path(__,DNode),path(DNode,__) ; path(DNode,__) , path(DNode,__).

But I got a, b, c and h.
I am assuming I'll have to like this to get all the letters I want:

path(__,DNode),path(DNode,__) ; path(DNode,__) , path(DNode,__) ; path(__,DNode) , path(__,DNode).

It gives me a, b, c, e, f, g and h though.

Any advice about how to get the 4 letters I want would be appreciated.

CapelliC CapelliC · Accepted Answer · 2013-05-13T07:30:36

if you display your graph, perhaps with Graphviz

enter image description here

?- writeln('digraph G {'), forall(connected(A,B), writeln(A->B)), writeln('}').

you can see that only [c,f] have 2 incoming edges, and that you don't need path/2. It's sufficient a join on the second argument of connected/2, with a test that the first arguments are different (operator (\=)/2).

Getting all nodes that have atleast 2 nodes connected to them

1 Answers