How do add degree of separation?

Question

In Prolog, how would I make a rule that checks how many people come in one persons network and then query it on degree of separation?

For example, if in Facebook my name is John; and I have one friend Tom, and Tom has one friend Lucy, and Lucy has one friend Ben, and Ben has one friend Josh, and Josh has one friend Nancy.

I want to create a rule in Prolog that tests how many people are in my network and also tell Prolog to return names up to a given number of degree of separation.

e.g. if I query something like;

?- mynetwork(josh,2).

Prolog should return

John
Tom
Lucy

or

John is friends with Tom
Tom is friends with Lucy

Daniel Lyons Daniel Lyons · Accepted Answer · 2014-01-09T23:36:51

Welcome to Prolog!

First you're going to need some facts:

friend(john, tom).
friend(tom, lucy).
friend(lucy, ben).
...

For simplicity, let's consider the case where friendships are directed: I can friend you, but that doesn't mean you friend me.

Let's say we're friends of degree 1 if I have friended you. That would look like this:

network(Person, 1, Friend) :- friend(Person, Friend).

Now the inductive case is one in which we've found a friend through a friend. That's going to look like this:

network(Person, N1, FoaF) :-
  N1 > 1, 
  N0 is N1-1,
  network(Person, N0, Friend),
  network(Friend, 1, FoaF).

Using is/2 you can be sure the predicate will be ill-behaved. For instance, if you omit the > 1 constraint, you will be able to ask questions and get N back that you won't if you include it. But you'll also get errors about being out of local stack. So if you can afford to, bring in clpfd now:

:- use_module(library(clpfd)).

network(Person, 1, Friend) :- friend(Person, Friend).
network(Person, N1, FoaF) :-
  N1 #> 0,
  N0 #= N1-1,
  network(Person, N0, Friend),
  network(Friend, 1, FoaF).

This should work for all input cases you care to try, though it still has no way to know when you're out of friendship levels.

?- network(john, N, X).
N = 1,
X = tom ;
N = 2,
X = lucy ;
N = 3,
X = ben ;
^CAction (h for help) ? abort
% Execution Aborted

?- network(john, 3, X).
X = ben ;
false.

?- network(john, 2, X).
X = lucy ;
false.

Edit Let me answer your questions out of order.

Where is the print statement?

By design, I haven't used one. Until here, we're just using the Prolog REPL (read-eval-print loop) to do our I/O. This is the natural way to work with Prolog. You'll save yourself a lot of heartache later if you go to some trouble to separate predicates that do I/O and user presentation from predicates concerned with meaning. This is just a petite application of model-view separation. You also benefit from keeping side-effects quarantined in their own predicates. As long as the pure logical part of your program is self-contained, you will always be able to build and compose with it.

How would you print upto a given number of people. e.g. if you type in network(john, 3, X). then it should print out upto N=3 X=ben

I would be inclined to call this predicate show_network/2 instead and keep the separation going. You could do it on the cheap with a failure-driven loop like so:

show_network(Person, Max) :-
  between(1, Max, N),
  network(Person, N, Friend),
  format('~w is friends with ~w\n', [Person, Friend]),
  fail.
show_network(_, _).

This will work like so:

?- show_network(john, 3).
john is friends with tom.
john is friends with lucy.
john is friends with ben.
true.

There are other approaches too, for instance, you could use forall/2:

show_network(Person, Max) :-
   forall(
     (between(1, Max, N), network(Person, N, Friend)),
     format('~w is friends with ~w\n', [Person, Friend])).

The relationship between the failure-driven loop and that one should be pretty clear. You could also manually get the list and then process it with maplist/2 or something:

show_network(Person, Max) :-
  findall(friend(Person,Friend), 
          (between(1, Max, N), network(Person, N, Friend)), 
          Friends),
  maplist(show_friend, Friends).

show_friend(friend(Person, Friend)) :-
  format('~w is friends with ~w\n', [Person, Friend]).

How do add degree of separation?

1 Answers