finding all paths satisfying expressions

From: Willem Hajenius (willem.hajenius_at_scarlet.be)
Date: 03/07/05 

Date: Mon, 7 Mar 2005 21:08:34 +0100

Perhaps someone can help me with this. I'm trying to construct a
program to
help me with some rigorous software testing. The objective is to find
all
possible test paths, given a set of decision tables. Some test cases
refer
to test cases in other tables, which in turn may refer to other
tables.
Currently the approach is to follow all paths by hand and write them
down,
which gets quite confusing and error-prone for deeply linked tables,
besides being a dull job.

I was thinking of using Prolog to automate this procedure, to have
something to verify my results against. The meaning of the tables
could be
expressed as links from a node to an expression yielding new nodes:

main ==> (a1 or a2) and g1
a1 ==> b1 or b2 or b3
a2 ==> b3 and (e1 or e2)
b2 ==> f1

'or' means 'fork path here' and 'and' means 'follow the first path,
return,
and then continue with the second path'.
So for the above example, the required output would be something like
this:
[main, a1, b1, g1]
[main, a1, b2, f1, g1]
[main, a1, b3, g1]
[main, a2, b3, e1, g1]
[main, a2, b3, e2, g1]

I've been trying to construct something along the line below, but so
far I haven't been
able to get it correct. (Prolog sometimes doesn't choose the intended
rule). Since I couldn't get any decent algorithm for the past two
weeks (and believe me, I have really tried!), I seek help from a more
knowledgeable Prologician.

Thanks for your time,

Willem Hajenius.

% add links of the form 'link(x, y).'

:- op(600, yfx, and).
:- op(550, yfx, or).

path(A, B and C, [A, PathB | PathC]) :-
  path(A, B, PathB),
  path(A, C, PathC).

path(A, B or _, [PathB]) :-
  path(A, B, PathB).

path(A, _ or C, [PathC]) :-
  path(A, C, PathC).

path(A, A, [A]).

path(A, B, [A | RestPath]) :-
  link(A, Int),
  path(Int, B, RestPath).

Relevant Pages

  • Re: Expression Evaluate
    ... if nobody answer you when you ask, for example, for neural networks ... out of the context, for prolog is not a functional language, say, as ML. ... :- op(500, yfx, add). ... is a valid expression, whose value is 15. ...
    (comp.lang.prolog)
  • Re: Expression Evaluate
    ... Thanks for helping me, I am new to prolog, i am getting error message ... :- op(500, yfx, add). ... is a valid expression, whose value is 15. ...
    (comp.lang.prolog)