CODEWITHSUNDEEP
prologgraph-theoryprolog-dif
CPUFry
CPUFry

Reputation: 576

Two different paths from X to Y in a graph

I am stuck with the following Prolog question: Given the edges of a graph with no cycles as facts. e.g:

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

I have to write a predicate that tests whether there are two different paths between vertices X and Y. e.g the call two_paths(a, c). should return true if there are two different paths from node a to node c. I know how to check whether there is a path between two vertices:

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

But how should I do this to check for two distinct paths? Thank you very much for your help.

Upvotes: 2

Views: 555

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476503

An idea might be to create a predicate path/3 that returns the constructed path, and then query for two paths that are different. Something like:

path(X,Y,[X,Y]) :- edge(X,Y).
path(X,Y,[X|T]) :- edge(X,Z), path(Z,Y,T).

Now path(a,c,T) will show you the path:

?- path(a,c,L).
L = [a, b, c] ;
false.

Now you could construct a predicate:

two_paths(X,Y) :-
    path(X,Y,La),
    path(X,Y,Lb),
    dif(La,Lb).

In other words, you ask Prolog to construct for you a path La, next construct for you a path Lb and then check if they are not equal (dif(La,Lb)). The first constructed Lb will be equivalent to La, but due to Prologs backtracking mechanism, it will try to construct you another path for which the condition might succeed. This is a rather pure Prolog implementation (with no cut (!), once/1, etc.). More efficient approaches exists since here you will "redo" the work in your second call.

A more efficient approach could be to construct a predicate path_avoid/3 (or path_avoid/4) where you feed the first constructed path to the predicate and thus force your program to at least at some point perform a different step from the one presented. I leave this open as a potential exercise.

Upvotes: 5

Related Questions