Easy prolog queries

Question

I am very new to prolog and although I’ve read some books I can definitely tell that my programming brain can’t think the Prolog way. The problem I would like to solve is pretty simple (I believe). I will describe it via an example.

Let’s say that I have a graph that contains 4 “types” of nodes and 3 edges that connect the nodes. The types can be A, B, C or D and as you can see from the image below (see Figure 1), A can be connected with B and C (A_To_B and A_To_C edges respectively), while C can be connected to D (C_To_D edge). There’s also an additional rule not shown on the picture: A can be connected to at most 1 C.

I would like to express these simple rules in Prolog to solve the problem shown in the second picture. There are 3 nodes which type is missing (labeled X?, Y? and Z?). By applying the above rules in my mind I can easily find that X? and Z? are of B type (as A can connect to no more than 1 Cs) and Y? is of type D as C can only connect to D.

Could please provide me any help on that? I am not writing just to pick the solution. I would like to learn Prolog as well so any suggestion on a book that explains Prolog to people who have never worked on such concepts before like me would be very welcome.

EDIT: Example that fails

I came up with the following two examples:

For example 1, the rules are

can_connect(a,b,_).
can_connect(a,c,1).

link(1,2).

type(1,a).
type(2,_).

The possible solutions returned are [b,c] which is correct as we request at most 1 link from A to C meaning that 0 links is also acceptable.

In example 2 the rules change 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 wrong. b is also an acceptable solution as we require again at most 2 A to C links which means that having only 1 is OK.

I spent this weekend trying to figure out the solution. First of all, I believe that it works as intended in Example 1 simply because there's no link from A to C instantiated in the proposed solution (where checking if 2 can be b), so the can_connect(a,c,1) is not checked so the proposed solution is getting accepted. In Example 2, there's one A to C link already there so the can_connect(a,c,2) is checked and the solution where node 2 has type b is rejected as the rule checks if there are exactly 2 and not at most 2 links from A to C.

I find a solution which works at these scenarios but fails at some others. Here it is:

% value #3 is the lower bound and #4 is the upper bound.
can_connect(a,b,0,500).
% A C 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.

This solution fails in this example

In this example, X? must be always b, Y? must always be C and Z? must always be D. It finds X? and Y? correctly but not Z?. I believe after some debugging that this is due the fact that in the current implementation I only check the can_connect rules that are related with links that start from a node and not that end to a node. However, I am not sure at all about that.

Any help is appreciated.

Answer 1

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

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

So, a first snippet

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 the problem.

Facts can_connect/3 then can be read like

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

Where we don't know the node type, a complex rule is needed, that infers the type of source node from the type of target node, and accounts for the counting constraint, 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 doesn't have library(aggregate), from where aggregate/3 has been loaded, 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 graph, marked with types where known:

my previous code worked only under very restricted assumptions. Here is something more general, that checks the constraints over the full graph (as was suggested by @false comment), with a '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). fails...