/*-------------------------------------------------------------*/
/*            NCL Marker Passing                               */
/*            (C) 1993 Zdravko Markov, II-BAS                  */
/*-------------------------------------------------------------*/
/*
DESCRIPTION:
-----------
This is simple illustration of the marker passing algorithm, as
described by Hendler (Hendler, J. A., Integrating Marker-passing
and Problem Solving: spreading activation approach to improved
choice in planning, Lawrence Erlbaum Associates, N.J., 1987).
 
The network encodes the knowledge that "The elephants are grey",
"Clyde is an elephant" and "Clyde is pink". The problem is to
answer questions like "What color are elephants?" and "What color
is Clyde?". The basic idea of the marker passing algorithm is to
allow markers to propagate along the SN links. When an SN node
receives a marker from a link it propagates it along the other
links it is connected to. There is also a mechanism which allows
the SN nodes to report the markers they have received. Thus if we
want  to find the connection between "clyde" and "color" nodes we
can mark them with different markers, say "m1" and "m2". Then
after spreading the markers along the SN, the node "pink" will
report that it has received both markers and we can conclude that
the color of Clyde is pink. Following this scheme the node "grey"
would also report for both "m1" and "m2", however this will be a
confusion about the color of Clyde. To resolve such conflicts
cancellation links are used. In our case such a link connects
"clyde" and "grey" and means that if any of them receives a
marker through this link, then it stops working. In this way we
encode the knowledge that "Clyde is not grey". Generally this
technique can be viewed as an approach to defining exceptions in
SN's.
 
The NCL program implementing this algorithm consists of two parts
- a net-clause and a Prolog procedure. The net-clause represents
the semantic network, where the SN node are represented by
spreading activation nodes, and the SN links - by net-variables
shared among them. The inhibitory inputs to the spreading
activation nodes allow to represent the cancellation links. The
procedure "p" used in the spreading activation nodes (defined in
Prolog) binds the net-variables thus passing the markers among
the SN nodes. It also indicates the cases when two deferent
markers meet at some node printing the name of the node. The free
nodes in the net-clause are used to set markers at some SN nodes
(by binding net-variables) and thus to initiate the spreading
activation mechanism.
*/
/*-------------------------------------------------------------*/
elephant(Elephant):
clyde(Clyde):
colour(Color):
grey(Grey):
pink(Pink):
 
node(Elephant,Eg,Isa,1,p([Elephant,Eg,Isa],elephant)):
node(Grey,Eg,Gc,~Cg,~Cg,1,p([Grey,Eg,Gc,Cg],grey)):
node(Clyde,Isa,Cp,~Cg,~Cg,1,p([Clyde,Isa,Cp,Cg],clyde)):
node(Pink,Cp,Pc,1,p([Pink,Cp,Pc],pink)):
node(Color,Pc,Gc,1,p([Color,Pc,Gc],color)).
 
p([_],_):-!.
p([X,X|T],N):-!,p([X|T],N).
p(_,N):-write(N),nl.
 
/*-------------------------------------------------------------*/
/* EXAMPLES:                                                   */
/*-------------------------------------------------------------*/
?- netmode(0).  /* Switch off the depth-first mode. */
 
/*
?- top(T),colour(m1),clyde(m2),spread(T). What is Clyde's color ?
pink
pink
 
?- top(T),colour(m1),elephant(m2),spread(T).
grey
clyde
 
(Normally it is expected that the "elephant" node should not
activate the "clyde" node. However due to the simplification of
the network, using bi-directional links, "clyde" also reports
that it has received two markers.This shows that "clyde" is on
the path between "color" and "elephant" nodes. This result can
be interpreted as "Clyde is an elephant" and "Clyde has some
color".)
*/