INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Jobs

DFS searching in Prolog

DFS searching in Prolog

(OP)
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..

CODE --> prolog

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.

RE: DFS searching in Prolog

You can try

CODE -->

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. 

RE: DFS searching in Prolog

(OP)
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?

RE: DFS searching in Prolog

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 :

CODE -->

:- 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)). 

RE: DFS searching in Prolog

(OP)
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..smile
Hope now i will try for BFS search according to your approach.

RE: DFS searching in Prolog

Thanks !

RE: DFS searching in Prolog

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

RE: DFS searching in Prolog

This sample can be usefull.

CODE

:- 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). 

RE: DFS searching in Prolog

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

RE: DFS searching in Prolog

It's easyer than bfs :

CODE -->

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). 

RE: DFS searching in Prolog

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

CODE

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. 

RE: DFS searching in Prolog

(OP)
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?

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Resources

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close