[Question]
  [
### Note this is a question primarily focusing on [data-structures](/questions/tagged/data-structures "show questions tagged 'data-structures'")
## Introduction
Bacefook wants people to be friendlier! As such, they are implementing a new system to suggest friends! Your task is to help Bacefook to implement their new suggesting system.
### Specifications:
Your program must be a REPL (read-eval-print loop) supporting 3 types of command: `FRIEND`, `SUGGEST` and `KNOW`.
`FRIEND X Y` - Specifies that `X` and `Y` are friends in the social network.
* If X is friends with Y, then Y is friends with X
* Can, but doesn't have to have output
* X is always friends with X
`KNOW X Y` - Output a truthy value if X and Y are friends, falsy otherwise
* `KNOW X X` will always output a truthy value
`SUGGEST X Y` - Output a truthy value if X and Y should be friends, falsy otherwise. X and Y should be friends if:
* X and Y are not friends
* X and Y have at least 1 friend in common
You are allowed to replace `FRIEND`, `SUGGEST` and `KNOW` with your own strings, but you must mention what string you have replaced each command with.
Your program can take in input/produce output in any way desirable, as long as it is reasonably easy to recognize how it works.
The number of people in the social network `N` is between 1 and 100,000, but there may be any number of "friend links" (edges).
> 
>  If you haven't noticed yet, this is a graph searching problem. The (likely) easiest (and possibly fastest) data structure to implement this in would be an adjacency matrix.
> 
> 
> 
### Test cases
```
FRIEND A B
FRIEND A C
FRIEND B D
SUGGEST A B -> Falsy, as they are friends
SUGGEST A D -> Truthy, as they share B as a common friend
SUGGEST C D -> Falsy, they do not share a common friend
KNOW D B -> Truthy, they are friends
KNOW B C -> Falsy, not friends
=============
FRIEND Tom Tim
KNOW Tom Tim -> Truthy
KNOW Tim Tom -> Truthy
KNOW Tom Kit -> Falsy
=============
KNOW Tim Kit -> Falsy
FRIEND Tim Tom
KNOW Tim Kit -> Falsy
FRIEND Tom Kit
SUGGEST Tim Kit -> Truthy
=============
FRIEND X Y
SUGGEST X Y -> Falsy since X is friends with X
```
[Here's some more test cases in image form](http://prntscr.com/epqrpe)
### Win condition
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), shortest code wins!
  
[Answer]
# SWI-Prolog, 62 47 41 bytes
```
X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.
```
Prolog isn't too often useful, but when it is it's just beautiful. We'll use `a+b` to notate that `a` is friends with `b`, `a*b` that `a` knows `b` and `a?b` that `b` should be suggested to `a` or not. The first line simply says that `X*Y` is true if either `X+Y`, `Y+X` or `X == Y` is true. This implements the symmetry of knowing eachother. Asking if there should be a suggestion is incredibly simple. We just ask if there is a `Z` such that `X*Y` is false and `X*Z` and `Y*Z` is true. Exactly as described in the challenge.
If you save this as a file (e.g. `friends.pl`) and open SWI-Prolog with this file (`prolog -l friends.pl`) you get dropped into a REPL.
You can assert friendships like this:
```
assert('a' + 'b').
assert('a' + 'c').
assert('b' + 'd').
```
You can check if people know eachother or suggestion should be made:
```
'a'*'b'.
'a'?'d'.
```
[Answer]
# PHP, ~~138 133~~ 129 bytes
PHP beats Mathematica - a rare occurence.
```
for(;$s=fgets(STDIN);$s>G?print$$a[$b]?$s<L:$s>L&&@array_intersect_key($$a,$$b):$$a[$b]=$$b[$a]=1)[,$a,$b]=explode(" ",trim($s));
```
prints `1` for truthy, empty string for falsy. Run with `-nr` or [test it online](http://sandbox.onlinephpfunctions.com/code/8df62923b5dcce0b442117e6b89c2013aa50cfb2).  
needs PHP 7.1 for the list assignment; user names are case sensitive and should exclude `a`, `b`, `s`.
**breakdown**
```
for(;$s=fgets(STDIN);                       # loop through input
    $s>G                                        # 2. evaluate command
        ?print$$a[$b]
            # command KNOW: true if $$a[$b]
            ?$s<L
            # command SUGGEST: true if !$$a[$b] and array_intersect_key returns truthy
            :$s>L&&@array_intersect_key($$a,$$b)
        # command FRIEND: set keys in $$a and $$b
        :$$a[$b]=$$b[$a]=1
)
    [,$a,$b]=explode(" ",trim($s));             # 1. parse user names to $a and $b
```
* `$s` has to be trimmed because it includes the newline character.
* [`array_intersect_key`](http://php.net/array_intersect_key) has to be muted or it would yield warnings for empty `$$a` or `$$b`.
* ~~+18~~ +15 bytes for all user names: Replace `$$a` with `$f[$a]` and `$$b` with `$f[$b]`.
[Answer]
## CMD (Batch), 50 + 20 + 135 = 205 bytes
* FRIEND.CMD
```
@for %%f in (%1.%1 %1.%2 %2.%2 %2.%1)do @set %%f=1
```
* KNOW.CMD
```
@call echo(%%%1.%2%%
```
Prints `1` for friends, a blank line for strangers.
* SUGGEST.CMD
```
@call set k=0%%%1.%2%%
@set k=1&if %k%==0 for /f "tokens=2 delims=.=" %%f in ('set %1.')do @call set k=%%k%%%%%%f.%2%%
@echo(%k:~1,1%
```
Prints `1` or a blank line. I think six consecutive `%`s might be a new personal best.
[Answer]
# Python 3, 122 118+2=120 bytes
```
l={}
def f(*r):l[r]=l[r[::-1]]=1
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:1-k(a,b)and any(k(a,z)&k(b,z)for z,_ in l)
```
Usage is exactly the same as ovs's answer.
[Answer]
# Python 3, ~~163~~ ~~149~~ 143+2=145 bytes
-6 bytes thanks to @FelipeNardiBatista
```
l=[]
def f(a,b):l.extend([(a,b),(b,a)])
k=lambda a,b:a==b or(a,b)in l
s=lambda a,b:k(a,b)-1and{c for c,d in l if d==a}&{c for c,d in l if d==b}
```
Save it to a file and run it as `python3 -i file.py`  
Use  
 - `f("a", "b")` instead of `FRIENDS a b`  
 - `k("a", "b")` instead of `KNOW a b`  
 - `s("a", "b")` instead of `SUGGEST a b`
Falsey output : 0, set(), False  
Truthy output : non-empty set, True
[Try it online](https://repl.it/Gjz0/8)
---
164 bytes when not using python interpreter as REPL:
```
f=[]
while 1:c,a,b=input().split();i=(a,b)in f;f+=c=="f"and[(a,b),(b,a)]or[(i+(a==b),-i+1and{c for c,d in f if d==a}&{c for c,d in f if d==b})];print(f[-1][c=="s"])
```
Uses  
 - `f` for `FRIEND`  
 - `s` for `SUGGEST`  
 - anything else for `KNOW`
[Try it online](https://repl.it/GjtK/4)
[Answer]
# Mathematica, 164 bytes
```
f={}
p:=Union@@f
i=Position[p,#][[1,1]]&
m:=Outer[Boole@MemberQ[f,{##}]&,p,p]
a=(#[[i@#2,i@#3]]/._@__->0)>0&
F=(f=#~Tuples~2~Join~f;)&
K=m~a~##&
S=a[m.m,##]&&!K@##&
```
Defines three main functions `F`, `S`, and `K` with the desired behavior. For example, the sequence of commands
```
F@{David, Bob}
F@{Bob, Alex}
F@{Alex, Kitty}
F@{Daniel, David}
F@{David, Kit}
S[David, Alex]
S[Bob, Kitty]
S[David, Kitty]
S[David, Bob]
K[David, Bob]
F@{Kit, Kitty}
S[David, Kitty]
```
is the last test case from the image linked in the OP; the `F` commands yield no output (the single semicolon seems a small price to pay for this), while the six `S` and `K` commands yield
```
True
True
False
False
True
True
```
as desired.
At any moment, `f` is the list of ordered pairs of the form `{A, B}` where `A` knows `B`, while `p` is the list of people appearing in some element of `f`. Calling `F@{A, B}` adds the four ordered pairs `{A, B}`, `{B, A}`, `{A, A}`, and `{B, B}` to `f`.
Also, at any moment, `m` is the adjacency matrix of the underlying graph (a person is adjacent to themselves and to all their `F`riends); the rows and columns are indexed by `p`, and `i` converts a person to the corresponding row/column number. The helper function `a` takes a matrix and two people as inputs and looks up the entry of the matrix whose "coordinates" are the two people, returning `True` if the number is positive and `False` if it's zero. (It's also possible to call `a` when one of the input people isn't yet recognized—for example, making a KNOW or SUGGEST query before any FRIEND declarations, or asking about some poor person who has no friends; this throws errors, but the rule `/._@__->0` forces the output to be `False` anyway.)
Calling `K[A, B]` therefore looks up whether `m[A, B]` is positive, which implements the `K`now verb. The matrix product `m.m` is the length-2-path matrix, containing the number of ways to go from one person to another along a path of length 2; this allows `S[A, B]` to implement the `S`uggest verb, as long as we additionally check by hand (`&&!K@##`) that the input people don't already know each other.
Fun fact: for free, this implementation allows us to declare cliques of friends—the command `F@{A, B, C, D}` is equivalent to all of `F@{A, B}`, `F@{A, C}`, `F@{A, D}`, `F@{B, C}`, `F@{B, D}`, and `F@{C, D}` combined.
[Answer]
# [Python 2](https://docs.python.org/2/), 118 bytes
```
F=[]
def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r
```
[Try it online!](https://tio.run/nexus/python2#hcxBC4IwGMbxu5/ivYQbSJR0MgxSCcJDH0AsZL2jgcyxrfLQd7elxerUbT@e/7thl1Z1cEYOhvCI0YSlBi1hdK1TBkLCbq3RXrV7zBulUJ7dJjjwWQzYGgTZWdBHsnJt1aIk/YNR3mnox@N6bKcy3rx2Rt2oh/tFtEiWNAlAaSEt4K1piW7uJyHV1RJKB0OWURVuwyjMwpoGnrln5lhMjH/jD7/W3HPhWPj4w6@fD457v/5n6Vm@@QQ "Python 2 – TIO Nexus")
Since I couldnt find repl online tool for python 2, I've added the TIO Nexus(in REPL format).
**Query for option and its possible output**
0 for Known - None
1 for Friends - True or False
2 for Suggest - True or False
**Example of usage and sample output in an repl python interpreter.**
```
>>> F=[]
>>> def s(f,c):c=set(c);r=c in F;return F.append(c)if f%2 else not r^(4 in[len(x|c)for x in F])if f else 2>len(c)or r
...
>>> s(1,['A','B'])
>>> s(1,['A','C'])
>>> s(1,['B','D'])
>>> s(2,['A','B'])
False
>>> s(2,['A','D'])
True
>>> s(2,['C','D'])
False
>>> s(0,['D','B'])
True
>>> s(0,['D','C'])
False
```
[Answer]
## [GNU sed](https://www.gnu.org/software/sed/), 158 + 2(rn flags) = 160 bytes
Since sed is a regex based language, there are no primitive types, not to mention abstract data structures. The network data is stored as free format text, in this case as redundant friend links like `A-B;B-A;`etc., which is then matched against various regex patterns.
```
G
/^F/{s:. (.+) (.+)\n:\1-\1;\1-\2;\2-\1;\2-\2;:;h}
/^K |^S /{s:(.) (.+) (.+)\n.*\2-\3.*:\1:;/^K$/p}
/^S /s:(.) (.+) (.+)\n.*(.+)-(\2.*\4-\3|\3.*\4-\2).*:\1:p
```
**[Try it online!](https://tio.run/nexus/sed#bYyxDoMgFEV3voKhA9gAkXaCXQdGHYlzGQRS3bS/XnwP06RNutx3cnPPKz1RU6e2xUjK5JXX8NH4VvjWYmrrdWWNbOzjBYaj@zRQ1Jjk36JscHeTDXwwFoYXlVGA8Z8tXsG8BusO1o4ikubng1yKo2OYqQsr6SqNaSY/XTpp@HTvlNeQ4lLEMx4)**
By design, sed runs the whole script for each input line. I recommend testing in interactive mode, to see the output of a command immediately after typing.
**Usage:** there are no truthy / falsy values in sed, so the output convention I use is borrowed from bash, whereby a non-empty string is considered as truthy, and an empty string as falsy.
* `F X Y` for `FRIEND X Y`. It has no output.
* `K X Y` for `KNOW X Y`. Outputs 'K' as truthy, and nothing as falsy.
* `S X Y` for `SUGGEST X Y`. Outputs 'S' as truthy, and nothing as falsy.
**Explanation:**
```
G
# append stored network data, if any, to the current input line
/^F/{
# if command is 'F' (FRIEND), for ex. 'F X Y'
   s:. (.+) (.+)\n:\1-\1;\1-\2;\2-\1;\2-\2;:
   # generate friend links, for ex. 'X-X;X-Y;Y-X;Y-Y'
   h
   # store updated network data
}
/^K |^S /{
# if command is either 'K' (KNOW) or 'S' (SUGGEST), for ex. 'K X Y'
   s:(.) (.+) (.+)\n.*\2-\3.*:\1:
   # search friend link 'X-Y'. If found, delete pattern except the command letter.
   /^K$/p
   # if only letter K left, print it (command is 'K', 'X' and 'Y' are friends)
}
/^S /
# if command is 'S', for ex. 'S X Y', but 'X' and 'Y' aren't friends
   s:(.) (.+) (.+)\n.*(.+)-(\2.*\4-\3|\3.*\4-\2).*:\1:p
   # search if 'X' and 'Y' have a friend in common (for ex. 'C'), and if so print
   #letter S. The search is for ex. 'C-X.*C-Y' and 'C-Y.*C-X'.
```
]