Traverse undirected graph in prolog

Question

Hi everyone,

In short: I am trying to traverse an undirected graph in prolog, but don't know how to, any advise would be greatly appreciated.

Background:

Trying to model rail system, with stations as nodes and their links as edges with weight 1.

I had no problem doing it in a directed manner, but cant do it in an undirected graph.

From the net generally, i've learned that undirected graph is declared in the following way:

node(1).
node(2).
node(3).
node(4).
node(5).
node(6).

arc(1,2):-node(1),node(2),1==2.
arc(1,4):-node(1),node(4),1==4.
arc(2,3):-node(2),node(3),2==3.
arc(3,5):-node(3),node(5),3==5.
arc(4,5):-node(4),node(5),4==5.
arc(5,6):-node(5),node(6),5==6.

path(X,Z,A) :-  (arc(X,Y),path(Y,Z,A1),A is A1+1;arc(X,Z), A is 1).

thus, the query path(1,2,X). should return 1, but it is not doing so...truly need help/guidance..thanks!

Answer 1

Here goes some pointers: To model an undirected graph you dont need the fact 'node', just the fact 'arc'. What do you want to acknowledge with the fact 'arc', well that there is an arc between the two nodes. So you would only need something like

arc(1, 2).
arc(1, 4).
...

Now, according to your definition of Path, it seems you want the query to succeed if there is a path from X to Y with total weight A. If you were dealing with directed graphs that could be expressed with a predicate like this:

path(X, Y, 1):- arc(X, Y).
path(X, Y, A):- arc(X, Z), Z\=Y,
                path(Z, Y, A1),
                A is A1+1.

Note however, that this may lead to infinite loops if the graph is cyclic. To avoid this problem, you may want to track the visited nodes, so that you visit almost once each node:

path(X, Y, A):- path(X, Y, [X], A).

path(X, Y, _, 1):- arc(X, Y).
path(X, Y, Visited, A):-  arc(X, Z),
                          not(member(Z, Visited)),
                          path(Z, Y, [Z|Visited], A1),
                          A is A1+1.

Now this algorithm can be trivially modified to deal with undirected graphs, adding just one more clause.

Answer 2

Hi, thanks for pointing out that mistake (1==2) i was making, kaarel and thanks for the answer gusbro.

Gusbro, I would like to clarify if indeed an undirected graph is created.

this is what I wrote to create an undirected graph.

arc(1,2).

arc(2,1).

arc(1,4).

arc(4,1).

arc(2,3).

arc(3,2).

arc(3,5).

arc(5,3).

arc(5,6).

arc(6,5).

thus path(1,4) should show 1; 4; no. Where 1 is the direct path between nodes 1,4 and 4 is the path from nodes 1-2-3-5-4.

But it's not happening. Instead, I get

A = 1 ;

A = 3 ;

A = 5 ;

A = 7 ;

A = 9 ;

A = 11

Not sure why though?

Answer 3

Thank you for pointing me in the right direction. I've modified your code a little to achieve my goal of traversing undirected graphs:

path(X, Y, A):- % this method allows user to input a path to be checked

path(X, Y, [X], A). % this is to ensure a list exists, to determine visited nodes later.

member(X,[X|_]). % X can be head of list.

member(X,[_|Tail]) :-

member(X,Tail). %X can be tail of list, regardless of what the head is.

path(X, Y, Visited, A):-

(arc(X,Y), A is 1;not(arc(X,Y)),arc(X, Z),not(member(Z,Visited)), path(Z, Y, [Z|Visited], A1),A is A1+1).
% this method checks if a direct/indirect path exists between X,Y in undirected graph

I still dont feel like i've got a good grasp of recursion yet. Would appreciate any pointers to understanding it better, besides more practice of cse :)

Thanks for the help!