Easy prolog queries -

i new prolog , although i’ve read books can tell programming brain can’t think prolog way. problem solve pretty simple (i believe). describe via example.

let’s have graph contains 4 “types” of nodes , 3 edges connect nodes. types can a, b, c or d , can see image below (see figure 1), can connected b , c (a_to_b , a_to_c edges respectively), while c can connected d (c_to_d edge). there’s additional rule not shown on picture: can connected @ 1 c.

i express these simple rules in prolog solve problem shown in second picture. there 3 nodes type missing (labeled x?, y? , z?). applying above rules in mind can find x? , z? of b type (as can connect no more 1 cs) , y? of type d c can connect d.

could please provide me on that? not writing pick solution. learn prolog suggestion on book explains prolog people have never worked on such concepts before me welcome.

edit: example fails

i came following 2 examples:

for example 1, rules are

can_connect(a,b,_). can_connect(a,c,1).  link(1,2).  type(1,a). type(2,_). 

the possible solutions returned [b,c] correct request at most 1 link c meaning 0 links acceptable.

in example 2 rules change following:

can_connect(a,b,_). can_connect(a,c,**2**).  link(1,2). link(1,3).  type(1,a). type(2,_). type(3,c). 

running code here returns [c] wrong. b acceptable solution require again at most 2 c links means having 1 ok.

i spent weekend trying figure out solution. first of all, believe works intended in example 1 because there's no link c instantiated in proposed solution (where checking if 2 can b), can_connect(a,c,1) not checked proposed solution getting accepted. in example 2, there's 1 c link there can_connect(a,c,2) checked , solution node 2 has type b rejected rule checks if there exactly 2 , not at most 2 links c.

i find solution works @ these scenarios fails @ others. here is:

% value #3 lower bound , #4 upper bound. can_connect(a,b,0,500). % c node can connected 0, 1 or 2 nodes can_connect(a,c,0,2). can_connect(d,c,1,1). can_connect(c,e,0,1).  %the same previous solution link(1,2). link(1,3).  % no change here type(1,a). type(2,_). type(3,c).  % no change here node_type(n, nt) :-      type(n, nt),      nonvar(nt),      !. % assume node has 1 type  % no change here node_type(n, nt) :-     assoc_types(typed),     maplist(check_connections(typed), typed),     memberchk(n:nt, typed).  % no change here assoc_types(typed) :-     findall(n, type(n, _), l),     maplist(typed, l, typed).  % no change here typed(n, n:t) :-      type(n, t),     member(t, [a,b,c]).  % changes here check_connections(graph, n:nt) :-     forall(link(n, m), (         memberchk(m:mt, graph),         can_connect(nt, mt, l, u),         findall(x, (link(n, x), memberchk(x:mt, graph)), ts),         mybetween(l, u, ts),         forall(can_connect(nt, y, lm, um), (             findall(p, (link(n,p),memberchk(p:y, graph)), ss),             length(ss, sssize ),             sssize>=lm,             sssize=<um         ))     )).  % used find if length of list between 2 limits. mybetween(lower, upper, mylist) :-     length(mylist, mysize),     mysize=<upper,     mysize>=lower. 

this solution fails in example

in example, x? must b, y? must c , z? must d. finds x? , y? correctly not z?. believe after debugging due fact in current implementation check can_connect rules related links start node , not end node. however, not sure @ that.

any appreciated.

the representation of problem needs disambiguate nodes names, can express links appropriately

now can write

can_connect(a,b,_). can_connect(a,c,1). can_connect(c,d,_).  link(1,2). link(1,3). link(1,4). link(4,5). link(4,6). link(7,4). link(7,8).  type(1,a). type(2,b). type(3,_). type(4,c). type(5,d). type(6,_). type(7,a). type(8,_). 

the underscore (anonymous variable) in prolog plays role similar null in sql, can assume value.

so, first snippet

node_type(n, nt) :- type(n, nt), nonvar(nt), !. % assume node has 1 type 

can used express know problem.

facts can_connect/3 can read

a can connect number of b can connect 1 c etc 

where don't know node type, complex rule needed, infers type of source node type of target node, , accounts counting constraint, like

node_type(n, nt) :-     link(m, n),     type(m, mt),     can_connect(mt, nt, c),     aggregate(count, y^(link(m, y), type(y, nt)), c).  ?- forall(between(1,8,n), (node_type(n,t),writeln(n:t))). 1:a 2:b 3:b 4:c 5:d 6:d 7:a 8:b true. 

edit if prolog doesn't have library(aggregate), aggregate/3 has been loaded, can try

node_type(n, nt) :-     link(m, n),     type(m, mt),     can_connect(mt, nt, c),     findall(t, (link(m, y), type(y, nt)), ts), length(ts, c). 

edit first of all, updated graph, marked types known:

my previous code worked under restricted assumptions. here more general, checks constraints on full graph (as suggested @false comment), 'generate , test' approach.

node_type(n, nt) :-     assoc_types(typed),     maplist(check_connections(typed), typed),     memberchk(n:nt, typed).  assoc_types(typed) :-     findall(n, type(n, _), l),     maplist(typed, l, typed).  typed(n, n:t) :- type(n, t), member(t, [a,b,c,d]).  check_connections(graph, n:nt) :-     forall(link(n, m), (         memberchk(m:mt, graph),         can_connect(nt, mt, c),         aggregate(count, x^(link(n, x), memberchk(x:mt, graph)), c)     )). 

now ?- node_type(4,x). fails...