Prolog : eliminating cycles from indirect relation

Question

I have a list of user facts defined as:

user(@michael).
user(@ana).
user(@bob).
user(@george).
user(@john).

and so on. Furthermore, I have a set of facts as:

follows(@michael,@ana).
follows(@ana,@bob).
follows(@bob,@michael).

I am trying to write a relation indirect(user1,user1) which will tell me if user1 indirectly follows user2. However, I am not able to do away with cyclic relations.

Like in the given example, michael -> ana -> bob -> michael will cause a cycle.

What is the best way to eliminate these cycles from the result of indirect(user1,user2)?

@false, I am trying to create twitter using prolog and one of the rules given to me is that user name starts with @. — na899, Dec 03 '14 at 04:16
Try `write_canonical(@abx).` it gives `@(abx)`. That is, `@` is a prefix-operator (of SWI). If you really want `@` in names write `'@name'` — false, Dec 03 '14 at 09:18
I would try that. Thanks @false. I have posted another problem here http://stackoverflow.com/questions/27275378/list-processing-in-prolog . Any help or hint would work for me. — na899, Dec 03 '14 at 15:27

Sergey Kalinichenko · Accepted Answer · 2014-12-03T04:15:09.993

2

You can make a rule that passes an extra list of users that you have "seen" so far, and ignore follows originating from these users: follows(A, B, Seen).

To do that, define a "follow transitive" rule that wraps the actual rule, like this:

follows_tx(A, B) :- follows(A, B, []).

Now you can define follows/3 rule this way:

follows(A, B, Seen) :-
    not_member(B, Seen),
    follows(A, B).
follows(A, B, Seen) :-
    follows(A, X),
    not_member(X, Seen),
    follows(X, B, [A|Seen]).

The base clause says that if there is a fact about A following B, we consider the predicate proven as long as we have not seen B before.

Otherwise, we find someone who follows A, check that we have not seen that user yet by checking not_member/2, and finally see if that user follows B, directly or indirectly.

Finally, here is how you can define not_member:

not_member(_, []).
not_member(X, [H|T]) :- dif(X, H), not_member(X, T).

Demo.

edited Dec 03 '14 at 04:15

answered Dec 02 '14 at 21:24

Sergey Kalinichenko

714,442
84
1,110
1,523

Now, `follows(A,B)` has three solutions only. That's why `(\=)/2` in `not_member/2` is not a good idea. – false Dec 02 '14 at 23:59
@na899 You are welcome! Take a look at the last edit in response to the last comment by false (replacing `=\` with `dif/2`). – Sergey Kalinichenko Dec 03 '14 at 04:17
@false Thanks again, I have forgotten how tricky Prolog can be at times (I last programmed in Prolog 20 years ago). – Sergey Kalinichenko Dec 03 '14 at 04:21

score 1 · Answer 2 · edited May 23 '17 at 11:51

1

indirect( A0,A) :-
   closure(follows, A0,A).

See for a definition of closure/3.

edited May 23 '17 at 11:51

Community

1
1

answered Dec 02 '14 at 21:59

false

10,264
13
101
209

Prolog : eliminating cycles from indirect relation

2 Answers2

Linked