Graph problem; I want to visit all the edges

[leon125]

Hello,

I'm working on a test case generation problem.
I made a model of an application as a graph whereby the vertices are screens where a user is in.
Through user inputs he reaches the same of a next screen.
The graph is a multi arc network, there can be more arcs between two vertices, the arcs are labeled with input as follows:

arc(Vertice1, Label, Vertice2)

For example:
arc(login screen, wrong password, login screen)
arc(login screen, good password, order screen).

There is a start vertice and an end vertice.

Can anyone give me a program or tips whereby all the arcs between the start and the end are visited and the labels are displayed.

Output can be:
wrong password - good password - label 3 ....end label

Thanx in advance

Leon

 

[kahleen]

Is there a depth limit in the graph visitation?

For example, if there is an arc(x, label, x) (like you have in your example), then there could be paths where this edge is traversed many times. If you consider traversing such edges, there is another problem. How many times should such edges be considered, because the algorithm could get stuck at such places.

 

[leon125]

Hi Kathleen,

I want all the paths from start to end whereby each edge is visited maximum once WITHIN 1 path but over the totality of al the paths each edge is visited minimum once.

For example

arc(start screen, wrong user name, start screen).
arc(start screen, wrong password, start screen).
arc(start screen, good login, order screen).
arc(order screen, order data, end screen).

The out put should then be

[wrong user name, good login, order data] // then on ;

[wrong password, good login, order data] // again ;

false

because then all the edges are visited at least one time but within a path maximum 1 time but but all the paths start at the start screen and end at the end screen.

 

[kahleen]

is this another solution?

[wrong pass -> wrong user -> good login -> order data]

each edge is visited only once ... but the start screen is visited 3 times, once in the beginning and 2 more times because of the first 2 steps

your code to display paths would be:

arc('start screen', 'wrong username', 'start screen').
arc('start screen', 'wrong password', 'start screen').
arc('start screen', 'good login', 'order screen').
arc('order screen', 'order data', 'end screen').


path(A, B) :-
	path(A, B, [], Path),
	reverse(Path, GoodPath),
	printPath(GoodPath),
	fail.

path(A, B, Path, [arc(A, Label, B) | Path]) :-
	arc(A, Label, B).
path(A, B, CurrentPath, Path) :-
	arc(A, Label, C),
	not(member(arc(A, Label, C), CurrentPath)),
	path(C, B, [arc(A, Label, C) | CurrentPath], Path).



printPath([arc(_, Label, _)]) :-
	!, write(Label), nl.
printPath([arc(_, Label, _) | Rest]) :-
	write(Label), write(' -> '),
	printPath(Rest).

call it:

?- path('start screen', 'end screen').
wrong username -> wrong password -> good login -> order data
wrong username -> good login -> order data
wrong password -> wrong username -> good login -> order data
wrong password -> good login -> order data
good login -> order data
false

These are all viable paths within the graph from the start node to the end node. I know some of the solutions above do not contain ALL the edges and you said something about each edge being contained at least once or something like that. If you still need that, say so and I will update the code. I'm not doing this now because I'm quite certain that the solutions above are, in fact, what you need. Tell me if I'm right. If yes, then you still need to do some work yourself to make it output the results in a list instead of printing it on screen ...

 

[leon125]

Hi Kathleen,

This is the perfectly right answer and exactly what I mean. All the edges are visited at least once, when we look at all the paths and each path goes from start to end.
Thank you very much for your excellent and quick answer!

Leon