×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
• Talk With Other Members
• Be Notified Of Responses
• Keyword Search
Favorite Forums
• Automated Signatures
• 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.

# DFS searching in Prolog2

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

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.

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:

• Talk To Other Members
• Notification Of Responses To Questions
• Favorite Forums One Click Access
• Keyword Search Of All Posts, And More...

Register now while it's still free!