title: prolog depth first iterative deepening
body: <p>I am trying to implement a depth first iterative deepening search of a state space graph.
  I have a graph with three vertices and their are two activating edges and two inhibition edges. Each node has a binary value, collectively this is the state of the graph. The graph can transition to a new state by seeing if one of the nodes is above a threshold or below a threshold (calculated from summing all the incoming nodes). At most one node will change at each transition. As their are three nodes, their are three state transition edges leaving each state in the state transition graph. <img src="https://i.stack.imgur.com/gVE9W.png" alt="Diagram of states"></p>
  
  <p>I think my state_change/3 works correctly, for instance I can query:</p>
  
  <pre><code>?-g_s_s(0,1,1,Begin),node(Arc),state_change(g_s(Begin),Second,Arc).
  </code></pre>
  
  <p>And it gives me the three correct answers:</p>
  
  <pre><code>Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
  Arc = v1,
  Second = g_s([node(v1, 1), node(v2, 1), node(v3, 1)]) ;
  
  Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
  Arc = v2,
  Second = g_s([node(v1, 0), node(v2, 0), node(v3, 1)]) ;
  
  Begin = [node(v1, 0), node(v2, 1), node(v3, 1)],
  Arc = v3,
  Second = g_s([node(v1, 0), node(v2, 1), node(v3, 0)]) 
  </code></pre>
  
  <p>I am trying to use the predicate id_path given in  Bratkos Prolog for A.I book, the solution to question 11.3 but I am having problems using/adapting it.   <strong>I want to create a path from a start node to the other nodes, with out getting into loops- I don't want it to have repeat elements or to get stuck when a path does not exist</strong>. I want the path to say the starting state, then a succession of states you can visit from the start state. If there is a self loop I want this to be included once for every way of getting there. Ie I want to keep track of the way that I got to the state space and make this unique not just that the state space is unique in the path. </p>
  
  <p>For instance from 011 I want all three paths of length one to be found with the arcs. </p>
  
  <pre><code> ?-id_path(g_s([node(v1,0),node(v2,1),node(v3,1)],Last,[Temp],Path).
  Path = [[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,1)],v1)];
  Path =[[node(v1,0),node(v2,1),node(v3,1)], to([node(v1,0),node(v2,0),node(v3,1)],v2)];
  Path=[[node(v1,0),node(v2,1),node(v3,1)],to([node(v1,1),node(v2,1),node(v3,0)],v3)];
  </code></pre>
  
  <p>and then at the next level all the paths with three nodes, showing the two arcs it needs to get to the nodes, then at the next level all the paths with fours nodes showing the three arcs it needs etc</p>
  
  <p>I have also put my code in SWISH if this is helpful? (Trying this for the first time?!) </p>
  
  <p><a href="http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&amp;togetherjs=xydMBkFjQR" rel="noreferrer">http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&amp;togetherjs=xydMBkFjQR</a> </p>
  
  <pre><code>a(v1,v3). %a activating edge
  a(v3,v1).
  i(v1,v2). %a inhibition edge
  i(v2,v3).
  
  nodes([v1,v2,v3]).
  
  node(X):- nodes(List),member(X,List). %to retrieve a node in graph a) or an arc in graph b)
  
  g_s_s(X,Y,Z,g_s([node(v1,X),node(v2,Y),node(v3,Z)])). %graph_state_simple - I use this to simply set a starting graph state.
  
  sum_list([], 0).
  sum_list([H|T], Sum) :-
     sum_list(T, Rest),
     Sum is H + Rest.
  
  invert(1,0).
  invert(0,1).
  
  state_of_node(Node,g_s(List),State):-
     member(node(Node,State),List).
  
  %all activating nodes in a graph state for a node
  all_a(Node,As,Ss,g_s(NodeList)):-
     findall(A, a(A,Node),As),
     findall(S,(member(M,As),member(node(M,S),NodeList)),Ss).
  
  %all inhibiting nodes in a graph state for a node
  all_i(Node,Is,Ss,g_s(NodeList)):-
     findall(I, i(I,Node),Is),
     findall(S,(member(M,Is),member(node(M,S),NodeList)),Ss).
  
  %sum of activating nodes of a node in a state
  sum_a(Node,g_s(NodeList),Sum):-
     all_a(Node,_As,Ss,g_s(NodeList)),
     sum_list(Ss,Sum).
  
  %sum of inhibiting nodes of a node in a state
  sum_i(Node,g_s(NodeList),Sum):-
     all_i(Node,_Is,Ss,g_s(NodeList)),
     sum_list(Ss,Sum).
  
  above_threshold(Threshold,Node,g_s(NodeList),TrueFalse):-
     sum_a(Node,g_s(NodeList),Sum_A),
     sum_i(Node,g_s(NodeList),Sum_I),
     TrueFalse = true,
     Threshold &lt; (Sum_A-Sum_I),
     !.
  above_threshold(Threshold,Node,g_s(NodeList),TrueFalse):-
     sum_a(Node,g_s(NodeList),Sum_A),
     sum_i(Node,g_s(NodeList),Sum_I),
     TrueFalse = false,
     Threshold &gt;= (Sum_A-Sum_I).
  
  %arc needs to be instantiated
  state_change(g_s(State1),g_s(State1),Arc):-
     above_threshold(0,Arc,g_s(State1),true),
     state_of_node(Arc,g_s(State1),1).
  state_change(g_s(State1),g_s(State2),Arc):-
     above_threshold(0,Arc,g_s(State1),false),
     state_of_node(Arc,g_s(State1),1),
     my_map(State1,State2,Arc).
  state_change(g_s(State1),g_s(State2),Arc):-
     above_threshold(0,Arc,g_s(State1),true),
     state_of_node(Arc,g_s(State1),0),
     my_map(State1,State2,Arc).
  state_change(g_s(State1),g_s(State1),Arc):-
     above_threshold(0,Arc,g_s(State1),false),
     state_of_node(Arc,g_s(State1),0).
  
  %
  my_map([],[],_).
  my_map([X|T],[Y|L],Arc):-
     X= node(Node,Value1),
     Node =Arc,
     invert(Value1,Value2),
     Y = node(Node,Value2),
     my_map(T,L,Arc).
  my_map([X|T],[Y|L],Arc):-
     X= node(Node,Value1),
     Node \= Arc,
     Y = node(Node,Value1),
     my_map(T,L,Arc).
  
  %this is the def in the book which I can not adapt.
  path(Begin,Begin,[start(Begin)]).
  path(First, Last,[First,Second|Rest]):-
     state_change(First,Second,Arc),
     path(Second,Last,[Second|Rest]).
  
  %this is the def in the book which I can not adapt.
  id_path(First,Last,Template,Path):-
     Path = Template,
     path(First,Last,Path)
  ;  copy_term(Template,P),
     path(First,_,P),
     !,
     id_path(First,Last,[_|Template],Path).
  </code></pre>