Easy prologue requests

Question

I am very new to the prologue, and although I have read some books, I can definitely say that my programming brain cannot think of a prologue. The problem that I would like to solve is quite simple (I think). I will describe it with an example.

Suppose I have a graph that contains 4 "types" of nodes and 3 edges that connect the nodes. Types can be A, B, C or D and, as you can see from the image below (see Fig. 1), A can be connected to B and C (respectively A_To_B and A_To_C), and C can be connected to D ( C_To_D). There is also an additional rule, not shown in the picture: A can be connected no more than 1 C.

I would like to express these simple rules in Prolog to solve the problem shown in the second figure. There are 3 nodes whose type is missing (marked X ?, Y? And Z?). By applying the above rules, I can easily find that X? and z? are of type B (since A can connect no more than 1 Cs) and Y? has type D, since C can only connect to D.

Could you please provide me any help? I am not writing to choose a solution. I would also like to study Prolog in such a way that any suggestion on the book explaining Prolog to people who have never worked on such concepts earlier than me would be very happy.

EDIT: an example of a failed

I came up with the following two examples:

For example, 1, the rules

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

Possible solutions: [b, c], which are correct, since we request no more than 1 link from A to C, which means that 0 links are also acceptable.

In example 2, the rules are changed to the 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 the code here returns [c], which is incorrect. b is also an acceptable solution, since again we need no more than 2 from A to C, which means that only 1 is in order.

I spent this weekend trying to figure out a solution. First of all, I believe that it works as intended in Example 1, simply because there is no link from A to C created in the proposed solution (where is the check if 2 can be b), therefore can_connect (a, c, 1) it is not verified that the proposed decision is made. In Example 2, there is one connection from A to C, so the can_connect (a, c, 2) check is checked, and the solution in which node 2 is of type b is rejected, because the rule checks if there are exactly 2 and no more than 2 links from A to C.

I find a solution that works in these scenarios but does not work on some others. Here he is:

 % value #3 is the lower bound and #4 is the upper bound. can_connect(a,b,0,500). % AC node can be connected by 0, 1 or 2 A nodes can_connect(a,c,0,2). can_connect(d,c,1,1). can_connect(c,e,0,1). %The same as 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 a node has only one 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 )) )). % It is used to find if the length of a list is between two limits. mybetween(Lower, Upper, MyList) :- length(MyList, MySize), MySize=<Upper, MySize>=Lower. 

In this example, this solution fails.

In this example, X? should always be b, y? should always be C and Z? should always be D. Does he find X? and y? right, but not Z ?. I believe that after some debugging this is due to the fact that in the current implementation I only check the can_connect rules associated with links that run from node, not end to node. However, I am not at all sure of this.

Any help is appreciated.

Answer 1

the presentation of the problem should eliminate the ambiguity of the node names, so we can express the links accordingly

now we 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 underlined (anonymous variable) in Prolog plays a role similar to NULL in SQL, it can take any value.

So, the first fragment

 node_type(N, NT) :- type(N, NT), nonvar(NT), !. % assume a node has only one type 

can be used to express what we know about a problem.

Can_connect / 3 facts can then be read as

 a can connect to any number of b a can connect to just 1 c etc 

Where we do not know the type of node, a complex rule is required that indicates the type of the source of the node to the type of the target node and takes into account the counting restriction, something 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 your Prolog does not have a library ( aggregate ) where the / 3 aggregate is loaded from, you 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, the updated chart marked with known types:

my previous code only worked under very limited assumptions. Here's something more general that checks for limitations on the full schedule (as suggested by the @false comment), with the “generate and 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). out of order ...