CODEWITHSUNDEEP
prologtransitive-closure
João Pinto
João Pinto

Reputation: 1998

How can I know if all nodes have been visited in a graph before reaching the intended node?

I have a knowledge base of this type:

connect(a, b).
connect(a, d).
connect(a, e).
connect(b, a).
connect(b, c).
...

My objective is, given an origin and a destiny, to go through all the existing nodes once, before reaching the final node.

So far this is what I have got:

path(O, D, L):-
    path(O, D, [O], L).

path(D, D, _, [D]).
path(O, D, A, [O|T]):-
    connect(O, I),
    \+ member(I, A),
    path(I, D, [I|A], T).

In order to deal with the double connections e.g. connect(a, b). connect(b, a). I use a list that saves every node I go through and before going into the recursion call I make sure that the node I am going to does not belong in that list.

Now I need to make sure that I go through all the existing nodes before reaching the final one. I have absolutely no idea how to even approach this. How can I ever be sure that I visited all the other nodes before reaching the last one?

Upvotes: 2

Views: 764

Answers (2)

RdR
RdR

Reputation: 116

You can test it with your own code (not using findall), by making a small change. Instead of throwing away the list of visited nodes, keep it. So, change path/4 to path/5 as follows:

path(D, D, V, V, [D]).
path(O, D, A, V, [O|T]):-
    connect(O, I),
    \+ member(I, A),
    path(I, D, [I|A], V, T).

Now you can query path(a,c,[a], Visited, Path) and test if any connect node exists that is not a member of Visited.

Upvotes: 2

user1812457
user1812457

Reputation:

You have defined a network as a list of edges. A quick-and-dirty way to collect all nodes would be, for example:

findall(X, ( connect(X, _) ; connect(_, X) ), Xs),
sort(Xs, Nodes)

This will first collect all "from"s and "to"s you have listed in your connect/2, then make a set out of it by sorting and removing duplicates.

At that point you can just compare this set to the path you found (after making a set out of it, too).

Obviously, it is important that your predicate fails there is no path that visits all nodes in the network defined by connect/2.

Upvotes: 1

Related Questions