CODEWITHSUNDEEP
prolog
Henry
Henry

Reputation: 777

List all reachable nodes

I have a predicate that is bi-directional and tells, whether one node is connected to another. E.g. 

has(a, b).
has(b, c).
has(d, b).

Now I would like to list all nodes which can be reached (from a specific node) with a given number of steps.

connected_nodes(a, T, 2).

should therefore output

T = c 
T = d

My current code looks like this:

connected_nodes(A, B, 0) :- write(A).
connected_nodes(A, B, N) :- 
    N > 0, M is N - 1,
    has(A, X),
    connected_nodes(X, B, M).

This works for T = c but not for T = d, as this is a bi-directional relation.

Am I thinking correctly in terms of recursion or how in which other way does this problem have to be solved?

Upvotes: 0

Views: 560

Answers (1)

Tasos Papastylianou
Tasos Papastylianou

Reputation: 22255

Your connected predicate seems fine. It might have made more sense to make the base case rely on has, but it's up to you.

However, you say your has predicate is "bi-directional" but you haven't explicitly created a rule that indicates this.

The following code is a "bi-directional" version of your code:

has(a, b).
has(b, c).
has(d, b).

bi_has(X,Y) :- has(X,Y).
bi_has(X,Y) :- has(Y,X).

connected_nodes(A, B, 0) :- write(A).
connected_nodes(A, B, N) :- 
    N > 0, M is N - 1,
    bi_has(A, X),
    connected_nodes(X, B, M).

Note however that your query now returns a as a possible answer too. This makes since, because you never explicitly stated you don't want to return back to the same element after 2 steps.

If you don't want this behaviour, then you need to also keep a list of elements visited so far (i.e. an accumulator), and confirm that you're not revisiting elements.

Upvotes: 1

Related Questions