CODEWITHSUNDEEP
prologgraph-theory
JmRag
JmRag

Reputation: 1459

Prolog Connected Edge of a graph

I want to make a predicate that check if a node can reach another node in graph in prolog. e.g Connected(1,X,[[1,3],[3,4],[2,5]]) The first argument is the node I want to start the second is the node I want to reach and the third is a list of edges. So far I have managed to do it but I get an infinite loop when I try to get all the nodes I reach by using findall/3.

Is there any way to stop the infinite loop or I should thing the problem from the beggining?

Here is my code so far:

 match([X,Y],List):- member([X,Y], List).
 match([X,Y],List):- member([Y,X], List).


go(X,Y,List):-match([X,Y],List).
go(X,Y,List):-match([X,Z],List),go(Z,Y,List).

goes(X,List,List2):-findall(Y,go(X,Y,List),List2).

I am new in Prolog and I cannot figure out what I am doing wrong.

Upvotes: 3

Views: 1213

Answers (2)

CapelliC
CapelliC

Reputation: 60004

a possible correction to your code

match([X,Y], List, Rest):- select([X,Y], List, Rest).
match([X,Y], List, Rest):- select([Y,X], List, Rest).

go(X,Y,List) :- match([X,Y],List,_).
go(X,Y,List) :- match([X,Z],List,Rest), go(Z,Y,Rest).

goes(X,List,List2) :- findall(Y, go(X,Y,List), List2).

now match 'consumes' an edge, then avoid infinite looping

Upvotes: 4

User
User

Reputation: 14853

Have a look at what ?- gtrace, goes(1,[[1,3],[3,4],[2,5]], X). Does.

For all recursions go :- go you need a condition when it stops.

In you case I recommend to add an argument Traversed which is a list of all nodes(or edges) you have visited. Then you do not go over nodes again if you have visited them already. So you get less and less elements to recursively look at and the recorsion ends at some point.

Many recursions use the predicate !. Have a look at it.

Upvotes: 1

Related Questions