CODEWITHSUNDEEP
prologfinite-automatatransitive-closure
jewelltaylor9430
jewelltaylor9430

Reputation: 119

Prolog List Represented Graph Traversal

I am attempting to traverse a graph I have constructed in prolog. The Graph is represent as a list of transitions of the form: next(FromState, ToState, Symbol) where FromState and ToState are nodes of the graph that are represented as: state(Number, IrrelevantVariable). Symbol can take many values but I am interested in only transitions with epsilon as the symbol. Given a group of StartStates I need to see what transitions have FromState = StartState and have Symbol = epsilon. If these two conditions are true I will add ToState to the end StartStates and add FromState to a list of visited nodes. I am having trouble doing so and my current program is not working for some reason. Any ideas why it isnt working? One of the issue seems to be when I use the member predicate to see if I have visited the state at the Head of the list it ends up unifying to make the member predicate true instead of actually checking Visited for Head on the first call of espsilon_closure_helper3

epsilon_closure_helper3([], [Transitions], Visited).

epsilon_closure_helper3([Head|Tail], Transitions, Visited) :-
  member(Head, Visited)
  ->
  epsilon_closure_helper2(Tail, Transitions, Visited)
  ;
  epsilon_closure_helper2(Head, Transitions, ClosureStates1),
  append(Tail, ClosureStates1, Tail1),
  sort(Tail1, Tail2),
  append(Vistited, [Head], Visited1),
  epsilon_closure_helper3(Tail2, Transitions, Visited1).


epsilon_closure_helper2(State, [], States) :-
  States = [State].

epsilon_closure_helper2(State, Transitions, States) :-
   Transitions = [Head|Tail],
   epsilon_closure_helper2(State, Tail, States1),
   Head = next(A, B, Symbol),
   (
   test_state(State, A, Symbol) -> append(States1, [B], States) ; 
   States = States1
   ).

  test_state(TargetState, State, Symbol) :-
    State = TargetState,
    Symbol = epsilon.

Sample Input: epsilon_closure_helper3([state(0, iv)], [next(state(0, iv), state(1, iv), epsilon), next(state(1, iv), state(2, iv), epsilon] Visited, Closure).

Output: Closure = [state(0, iv), state(1, iv), state(2, iv)]

Upvotes: 1

Views: 128

Answers (1)

Guy Coder
Guy Coder

Reputation: 24996

I know the structure is not the same as given in the question, but I also know that you are a student and need to understand and learn the code, so here is a solution that is not using the same structures as yours, but should help you learn and finish your assignment.

The graph is from this page.

transistion(a,b,0).
transistion(a,c,0).
transistion(a,a,1).
transistion(a,b,epsilon).
transistion(b,b,1).
transistion(b,c,epsilon).
transistion(c,c,0).
transistion(c,c,1).

epsilon_closure(End_state,States) :-
    epsilon_closure(End_state,[],States).

epsilon_closure(End_state,States0,States) :-
    bagof([Start,End,Transistion],transistion(Start,End,Transistion),Transitions),
    epsilon_closure_rec(End_state,Transitions,States0,States), !.

epsilon_closure_rec(End,[[Start_state,End,epsilon]|Transitions],States0,States) :-
    \+ memberchk(Start_state,States0),
    epsilon_closure(Start_state,States0,States1),
    epsilon_closure_rec(End,Transitions,States1,States).
epsilon_closure_rec(End,[[_,_,_]|Transitions],States0,States) :-
    epsilon_closure_rec(End,Transitions,States0,States).
% A state is an epsilon transition to itself
epsilon_closure_rec(End_state,[],States0,[End_state|States0]).

Notice that the code does not have any append/3, sort/2, =/2 or ->/2.

Example runs:

?- epsilon_closure(a,States).
States = [a].

?- epsilon_closure(b,States).
States = [b, a].

?- epsilon_closure(c,States).
States = [c, b, a].

Upvotes: 1

Related Questions