DFS searching in Prolog 2

[ridoy]

I am new in Prolog,working with trees such as forming a tree,counting nodes etc.I had done those,face problems when i am trying to apply DFS search to find a node.
Below is my code so far..

constructTree(tree(1,
            tree(2,
                tree(3,nil,nil),
                tree(4,nil,nil)),
            tree(5,
                tree(6,nil,nil),
                tree(7,nil,nil))
        )
    ).
count_nodes(nil,0).
count_nodes(tree(_,L,R),N):-
    count_nodes(L,CL),
    count_nodes(R,CR),
    N is CL+CR+1.

When i test it it gives output like..
?- constructTree(T),count_nodes(T,N).
T = tree(1, tree(2, tree(3, nil, nil), tree(4, nil, nil)), tree(5, tree(6, nil, nil), tree(7, nil, nil))),
N = 7.(total node number)
So how can i modify it for searching a node in DFS? Suppose,i want to search node 5 and count iteration number needs to find that node,finally N will print that count number.

 

[joel76]

You can try

search_node(tree(Node, _, _), Node, 0) :- !.


search_node(tree(_, L, R), Node, N) :-
	(   search_node(L, Node, N1); search_node(R, Node, N1)),
	N is N1+1.

 

[ridoy]

Thanks for your response.I think your code counts level of a node actually,it not counts iteration number according DFS search.Cosider for node 6, it counts 2 according to your code because it is in level 2.But according to DFS search,it should be 5,isn't it?

 

[joel76]

If I understand what you mean, for 6 it should 10 :
6 is not 1 : step 1
then I search in left tree
6 is not 2 : step 2
I search in left tree
6 is not 3 : step 3
I search in left tree
tree empty : step 4
I search in right tree
tree empty : step 5
.....
According to this scheme I propose :

:- dynamic node/1.
search_node(Tree,Node, N) :-
	retractall(node(_)),
	assert(node(1)),
	search_node_(Tree,Node),
	retract(node(N)).


search_node_(tree(Node, _, _), Node) :- !.


search_node_(tree(_, L, R), Node) :-
	(   retract(node(N)),
	    N1 is N+1,
	    assert(node(N1)),
	    search_node_(L, Node)
	;   retract(node(N2)),
	    N3 is N2+1,
	    assert(node(N3)),
	    search_node_(R, Node)).

 

[ridoy]

I think your approach is right,i can do some modification on it according to my requirement.Thank you very much for sharing it. Give a star for your effort..
Hope now i will try for BFS search according to your approach.

 

[joel76]

Thanks !

 

[ridoy]

A little bit clarification needed,do you please explain how the work is going and the function of retract(),retractall() and assert()?

 

[joel76]

This sample can be usefull.

:- dynamic fact/1.

example :-
	test(asserta),
	test(assertz).


test(Pred) :-
	format('~nWith ~w~n~n', [Pred]),

	Call_1 =.. [Pred, fact(1)],
	Call_2 =.. [Pred, fact(2)],
	Call_3 =.. [Pred, fact(3)],

	maplist(call, [Call_1, Call_2, Call_3]),
	list,

	retract(fact(P)),
	format('Retract : value of P : ~w~n~n', [P]),
	list,

	retractall(fact(_)),
	list.

list :-
	listing(fact).

 

[ridoy]

Could you edit your above search_node() for BFS search like the way you do it for DFS?

 

[joel76]

It's easyer than bfs :

bfs_search_node(Tree,Node, N) :-
	bfs_search_node_([Tree],Node, 1, N).

bfs_search_node_([tree(Node, _, _) | _T], Node, FN, FN) :- !.

bfs_search_node_([tree(_, L, R) | T], Node, CN, FN) :-
	CN1 is CN + 1,
	append(T, [L, R], T1),
	bfs_search_node_(T1, Node, CN1, FN).

 

[joel76]

I can't edit my posts so, I give you another way to count nodes in DFS without assert/retract :

dfs_search_node(Tree,Node, N) :-
	dfs_search_node_(Tree,Node, 1, _, N).


dfs_search_node_(tree(Node, _, _), Node, FN, _, FN) :- !.

dfs_search_node_(tree(_, L, R), Node, CN, _TN, FN) :-
	CN1 is CN + 1,
	dfs_search_node_(L, Node, CN1, TN1, FN),
	(   CN1 \== FN
	->  dfs_search_node_(R, Node, TN1, _TN, FN)
	;   true).

dfs_search_node_(nil, _Node, CN, TN, _FN) :-
	TN is CN + 1.

 

[ridoy]

Thanks for your effort.It was so helpful for me.Do you refer any link or tutorial about how to make a chess game in Prolog where the game should be played between me and computer implementing AI?