<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P092-friend-network/ | updated: 2026-10-15 -->

# P092 Friend network

Who is friends with whom: the groups that hang together by depth-first search, degrees of separation by breadth-first search, whether everyone fits in two teams with no friends together (or an odd ring that prevents it), and friend suggestions.

EML-P project `projects/friend-network` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/friend-network` runs it and `eml project verify projects/friend-network` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: graph-dfs-recursive (https://efficientnewlanguage.org/cases/086-graph-dfs-recursive/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
3
Zed

6
Ana
Ana
6
Ana
Ben
6
Ana1
Ben
7
Ana
Fay
7

5

8
```

Screen:

```text
== Friend network ==
Who is friends with whom: groups, degrees of separation, two teams, suggestions.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 0
Pick a number from 1 to 8.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> x
Pick a number from 1 to 8.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 3
from> Zed
Nobody called Zed is in the network.
from> 
Cancelled.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 6
first person> Ana
second person> Ana
Someone cannot be their own friend here.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 6
first person> Ana
second person> Ben
Ana and Ben are friends already.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 6
first person> Ana1
second person> Ben
Names are letters, up to 10.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 7
first person> Ana
second person> Fay
Ana and Fay are not friends.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 7
first person> 
Cancelled.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 5
person> 
Cancelled.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 8
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
2
3
Ana
Fay
3
Ana
Ana
3
Ana
Gus
4
5
Ana
5
Jo
7
Ivo
Gus
4
6
Fay
Gus
2
6
Jo
Kim
1
8
```

Screen:

```text
== Friend network ==
Who is friends with whom: groups, degrees of separation, two teams, suggestions.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 1
  Ana: Ben and Chloe
  Ben: Ana and Dev
  Chloe: Ana and Dev
  Dev: Ben, Chloe and Eli
  Eli: Dev and Fay
  Fay: Eli
  Gus: Hana and Ivo
  Hana: Gus and Ivo
  Ivo: Gus and Hana
  Jo: no friends here

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 2
  Ana, Ben, Dev, Chloe, Eli and Fay
  Gus, Hana and Ivo
  Jo
3 groups: each holds everyone its members can reach through friends, and nobody else.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 3
from> Ana
to> Fay
  Ana - Ben - Dev - Eli - Fay
4 steps apart: no shorter chain of friends exists.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 3
from> Ana
to> Ana
  Ana
That is the same person.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 3
from> Ana
to> Gus
Ana and Gus are not connected, however far you go.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 4
No: Ivo - Gus - Hana - Ivo is a ring of 3, an odd number, and going round it the teams would have to swap an odd number of times.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 5
person> Ana
  Dev: 2 friends in common

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 5
person> Jo
No suggestions for Jo: nobody is a friend of a friend who is not a friend already.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 7
first person> Ivo
second person> Gus
Ivo and Gus are no longer friends.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 4
  team 1: Ana, Dev, Fay, Gus, Ivo and Jo
  team 2: Ben, Chloe, Eli and Hana
No two friends are in the same team: the network is two-sided.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 6
first person> Fay
second person> Gus
Fay and Gus are now friends.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 2
  Ana, Ben, Dev, Chloe, Eli, Fay, Gus, Hana and Ivo
  Jo
2 groups: each holds everyone its members can reach through friends, and nobody else.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 6
first person> Jo
second person> Kim
Kim joins the network.
Jo and Kim are now friends.

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 1
  Ana: Ben and Chloe
  Ben: Ana and Dev
  Chloe: Ana and Dev
  Dev: Ben, Chloe and Eli
  Eli: Dev and Fay
  Fay: Eli and Gus
  Gus: Fay and Hana
  Hana: Gus and Ivo
  Ivo: Hana
  Jo: Kim
  Kim: Jo

1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit
choice> 8
Bye.
```

## Modules

### main.eml

```eml
# P092 friend network: who is friends with whom, the groups that hang
# together, degrees of separation, whether everyone fits in two teams with
# no friends together, and friend suggestions.
import network

def plain(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def is_name(s):
    if len(s) == 0 or len(s) > 10:
        return False
    for c in s:
        if not ((c >= "a" and c <= "z") or (c >= "A" and c <= "Z")):
            return False
    return True

def names_text(names, xs):
    "" => s
    for i in [0:len(xs) - 1]:
        if i > 0 and i == len(xs) - 1:
            s + " and " => s
        elif i > 0:
            s + ", " => s
        s + names[xs[i]] => s
    return s

def ask_person(net, prompt):
    while True:
        plain(input(prompt)) => s
        if s == "":
            return -1
        network.index_of(net[0], s) => i
        if i >= 0:
            return i
        ("Nobody called " + s + " is in the network.") ^0

def show(net):
    net[0] => names
    net[1] => fr
    for i in [0:len(names) - 1]:
        if len(fr[i]) == 0:
            ("  " + names[i] + ": no friends here") ^0
        else:
            ("  " + names[i] + ": " + names_text(names, fr[i])) ^0

def show_groups(net):
    network.groups(net) => gs
    for g in gs:
        ("  " + names_text(net[0], g)) ^0
    (str(len(gs)) + " groups: each holds everyone its members can reach through friends, and nobody else.") ^0

def separation(net):
    ask_person(net, "from> ") => a
    if a == -1:
        "Cancelled." ^0
        return
    ask_person(net, "to> ") => b
    if b == -1:
        "Cancelled." ^0
        return
    network.path(net, a, b) => p
    if len(p) == 0:
        (net[0][a] + " and " + net[0][b] + " are not connected, however far you go.") ^0
        return
    "" => chain
    for i in p:
        if chain != "":
            chain + " - " => chain
        chain + net[0][i] => chain
    ("  " + chain) ^0
    if len(p) == 1:
        "That is the same person." ^0
    else:
        "steps" => w
        if len(p) == 2:
            "step" => w
        (str(len(p) - 1) + " " + w + " apart: no shorter chain of friends exists.") ^0

def teams(net):
    network.two_teams(net) => r
    if r[0]:
        [] => one
        [] => two
        for i in [0:len(r[1]) - 1]:
            if r[1][i] == 0:
                one + [i] => one
            else:
                two + [i] => two
        ("  team 1: " + names_text(net[0], one)) ^0
        ("  team 2: " + names_text(net[0], two)) ^0
        "No two friends are in the same team: the network is two-sided." ^0
    else:
        "" => chain
        for i in r[1]:
            if chain != "":
                chain + " - " => chain
            chain + net[0][i] => chain
        ("No: " + chain + " - " + net[0][r[1][0]] + " is a ring of " + str(len(r[1])) + ", an odd number, and going round it the teams would have to swap an odd number of times.") ^0

def suggest(net):
    ask_person(net, "person> ") => a
    if a == -1:
        "Cancelled." ^0
        return
    network.suggestions(net, a) => s
    if len(s) == 0:
        ("No suggestions for " + net[0][a] + ": nobody is a friend of a friend who is not a friend already.") ^0
        return
    for x in s:
        "friends" => w
        if x[1] == 1:
            "friend" => w
        ("  " + net[0][x[0]] + ": " + str(x[1]) + " " + w + " in common") ^0

def change(net, adding):
    plain(input("first person> ")) => a
    if a == "":
        "Cancelled." ^0
        return net
    plain(input("second person> ")) => b
    if b == "":
        "Cancelled." ^0
        return net
    if not is_name(a) or not is_name(b):
        "Names are letters, up to 10." ^0
        return net
    if a == b:
        "Someone cannot be their own friend here." ^0
        return net
    network.index_of(net[0], a) => i
    network.index_of(net[0], b) => j
    if not adding:
        if i == -1 or j == -1 or not network.has(net[1][i], j):
            (a + " and " + b + " are not friends.") ^0
            return net
        (a + " and " + b + " are no longer friends.") ^0
        return network.unfriend(net, i, j)
    net[0] => names
    net[1] => fr
    for nm in [a, b]:
        if network.index_of(names, nm) == -1:
            if len(names) == 15:
                "The network holds 15 people at most." ^0
                return net
            names + [nm] => names
            fr + [[]] => fr
            (nm + " joins the network.") ^0
    [names, fr] => net
    network.index_of(names, a) => i
    network.index_of(names, b) => j
    if network.has(fr[i], j):
        (a + " and " + b + " are friends already.") ^0
        return net
    (a + " and " + b + " are now friends.") ^0
    return network.befriend(net, i, j)

["Ana", "Ben", "Chloe", "Dev", "Eli", "Fay", "Gus", "Hana", "Ivo", "Jo"] => names
[[], [], [], [], [], [], [], [], [], []] => fr
[names, fr] => net
for pair in [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5], [6, 7], [7, 8], [8, 6]]:
    network.befriend(net, pair[0], pair[1]) => net

"== Friend network ==" ^0
"Who is friends with whom: groups, degrees of separation, two teams, suggestions." ^0
True => running
while running:
    "" ^0
    "1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit" ^0
    plain(input("choice> ")) => choice
    if choice == "1":
        show(net)
    elif choice == "2":
        show_groups(net)
    elif choice == "3":
        separation(net)
    elif choice == "4":
        teams(net)
    elif choice == "5":
        suggest(net)
    elif choice == "6":
        change(net, True) => net
    elif choice == "7":
        change(net, False) => net
    elif choice == "8":
        False => running
    else:
        "Pick a number from 1 to 8." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import network

def plain(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def is_name(s):
    if len(s) == 0 or len(s) > 10:
        return False
    for c in s:
        if not (c >= "a" and c <= "z" or c >= "A" and c <= "Z"):
            return False
    return True

def names_text(names, xs):
    s = ""
    for i in range(0, len(xs)):
        if i > 0 and i == len(xs) - 1:
            s = s + " and "
        elif i > 0:
            s = s + ", "
        s = s + names[xs[i]]
    return s

def ask_person(net, prompt):
    while True:
        s = plain(input(prompt))
        if s == "":
            return -1
        i = network.index_of(net[0], s)
        if i >= 0:
            return i
        print("Nobody called " + s + " is in the network.")

def show(net):
    names = net[0]
    fr = net[1]
    for i in range(0, len(names)):
        if len(fr[i]) == 0:
            print("  " + names[i] + ": no friends here")
        else:
            print("  " + names[i] + ": " + names_text(names, fr[i]))

def show_groups(net):
    gs = network.groups(net)
    for g in gs:
        print("  " + names_text(net[0], g))
    print(str(len(gs)) + " groups: each holds everyone its members can reach through friends, and nobody else.")

def separation(net):
    a = ask_person(net, "from> ")
    if a == -1:
        print("Cancelled.")
        return
    b = ask_person(net, "to> ")
    if b == -1:
        print("Cancelled.")
        return
    p = network.path(net, a, b)
    if len(p) == 0:
        print(net[0][a] + " and " + net[0][b] + " are not connected, however far you go.")
        return
    chain = ""
    for i in p:
        if chain != "":
            chain = chain + " - "
        chain = chain + net[0][i]
    print("  " + chain)
    if len(p) == 1:
        print("That is the same person.")
    else:
        w = "steps"
        if len(p) == 2:
            w = "step"
        print(str(len(p) - 1) + " " + w + " apart: no shorter chain of friends exists.")

def teams(net):
    r = network.two_teams(net)
    if r[0]:
        one = []
        two = []
        for i in range(0, len(r[1])):
            if r[1][i] == 0:
                one = one + [i]
            else:
                two = two + [i]
        print("  team 1: " + names_text(net[0], one))
        print("  team 2: " + names_text(net[0], two))
        print("No two friends are in the same team: the network is two-sided.")
    else:
        chain = ""
        for i in r[1]:
            if chain != "":
                chain = chain + " - "
            chain = chain + net[0][i]
        print("No: " + chain + " - " + net[0][r[1][0]] + " is a ring of " + str(len(r[1])) + ", an odd number, and going round it the teams would have to swap an odd number of times.")

def suggest(net):
    a = ask_person(net, "person> ")
    if a == -1:
        print("Cancelled.")
        return
    s = network.suggestions(net, a)
    if len(s) == 0:
        print("No suggestions for " + net[0][a] + ": nobody is a friend of a friend who is not a friend already.")
        return
    for x in s:
        w = "friends"
        if x[1] == 1:
            w = "friend"
        print("  " + net[0][x[0]] + ": " + str(x[1]) + " " + w + " in common")

def change(net, adding):
    a = plain(input("first person> "))
    if a == "":
        print("Cancelled.")
        return net
    b = plain(input("second person> "))
    if b == "":
        print("Cancelled.")
        return net
    if not is_name(a) or not is_name(b):
        print("Names are letters, up to 10.")
        return net
    if a == b:
        print("Someone cannot be their own friend here.")
        return net
    i = network.index_of(net[0], a)
    j = network.index_of(net[0], b)
    if not adding:
        if i == -1 or j == -1 or not network.has(net[1][i], j):
            print(a + " and " + b + " are not friends.")
            return net
        print(a + " and " + b + " are no longer friends.")
        return network.unfriend(net, i, j)
    names = net[0]
    fr = net[1]
    for nm in [a, b]:
        if network.index_of(names, nm) == -1:
            if len(names) == 15:
                print("The network holds 15 people at most.")
                return net
            names = names + [nm]
            fr = fr + [[]]
            print(nm + " joins the network.")
    net = [names, fr]
    i = network.index_of(names, a)
    j = network.index_of(names, b)
    if network.has(fr[i], j):
        print(a + " and " + b + " are friends already.")
        return net
    print(a + " and " + b + " are now friends.")
    return network.befriend(net, i, j)

names = ["Ana", "Ben", "Chloe", "Dev", "Eli", "Fay", "Gus", "Hana", "Ivo", "Jo"]
fr = [[], [], [], [], [], [], [], [], [], []]
net = [names, fr]
for pair in [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5], [6, 7], [7, 8], [8, 6]]:
    net = network.befriend(net, pair[0], pair[1])
print("== Friend network ==")
print("Who is friends with whom: groups, degrees of separation, two teams, suggestions.")
running = True
while running:
    print("")
    print("1) network  2) groups  3) degrees of separation  4) two teams  5) suggestions  6) add a friendship  7) remove one  8) quit")
    choice = plain(input("choice> "))
    if choice == "1":
        show(net)
    elif choice == "2":
        show_groups(net)
    elif choice == "3":
        separation(net)
    elif choice == "4":
        teams(net)
    elif choice == "5":
        suggest(net)
    elif choice == "6":
        net = change(net, True)
    elif choice == "7":
        net = change(net, False)
    elif choice == "8":
        running = False
    else:
        print("Pick a number from 1 to 8.")
print("Bye.")
```

### network.eml

```eml
# P092 friend network - people and who is friends with whom (both ways).
# A network is [names, friends], friends[i] the sorted list of i's
# friends' indices.

def index_of(names, name):
    for i in [0:len(names) - 1]:
        if names[i] == name:
            return i
    return -1

def has(xs, x):
    for y in xs:
        if y == x:
            return True
    return False

def insert_sorted(xs, x):
    [] => out
    False => done
    for y in xs:
        if not done and x < y:
            out + [x] => out
            True => done
        out + [y] => out
    if not done:
        out + [x] => out
    return out

def befriend(net, a, b):
    net[1] => fr
    if a == b or has(fr[a], b):
        return net
    insert_sorted(fr[a], b) => fr[a]
    insert_sorted(fr[b], a) => fr[b]
    return [net[0], fr]

def unfriend(net, a, b):
    net[1] => fr
    [] => xa
    for y in fr[a]:
        if y != b:
            xa + [y] => xa
    [] => xb
    for y in fr[b]:
        if y != a:
            xb + [y] => xb
    xa => fr[a]
    xb => fr[b]
    return [net[0], fr]

def visit(fr, i, group, seen):
    # The corpus case graph-dfs-recursive: mark i, then go into each friend
    # not yet seen. `seen` is changed in place; the group is returned.
    1 => seen[i]
    group + [i] => group
    for j in fr[i]:
        if seen[j] == 0:
            visit(fr, j, group, seen) => group
    return group

def groups(net):
    # The connected groups: everyone reachable from someone, by depth-first
    # search, starting from each person not yet reached.
    net[1] => fr
    [0] * len(fr) => seen
    [] => out
    for i in [0:len(fr) - 1]:
        if seen[i] == 0:
            out + [visit(fr, i, [], seen)] => out
    return out

def path(net, a, b):
    # A shortest chain of friends from a to b by breadth-first search, or []
    # if they are not connected: the degrees of separation are its length
    # minus one.
    net[1] => fr
    [-1] * len(fr) => came
    [0] * len(fr) => seen
    [a] => queue
    1 => seen[a]
    0 => head
    while head < len(queue):
        queue[head] => i
        head + 1 => head
        if i == b:
            [b] => out
            while out[0] != a:
                [came[out[0]]] + out => out
            return out
        for j in fr[i]:
            if seen[j] == 0:
                1 => seen[j]
                i => came[j]
                queue + [j] => queue
    return []

def two_teams(net):
    # Can everyone be put in one of two teams with no friends in the same
    # team? Colour by depth-first search, alternating; a friend already
    # coloured the same closes an odd cycle. Returns [True, colours] or
    # [False, the odd cycle].
    net[1] => fr
    [-1] * len(fr) => colour
    [-1] * len(fr) => parent
    for s in [0:len(fr) - 1]:
        if colour[s] == -1:
            0 => colour[s]
            [s] => stack
            while len(stack) > 0:
                stack[len(stack) - 1] => i
                stack[0:len(stack) - 1] => stack
                for j in fr[i]:
                    if colour[j] == -1:
                        1 - colour[i] => colour[j]
                        i => parent[j]
                        stack + [j] => stack
                    elif colour[j] == colour[i]:
                        return [False, odd_cycle(parent, i, j)]
    return [True, colour]

def odd_cycle(parent, i, j):
    # i and j are friends with the same colour: their paths up the search
    # tree meet, and the two paths with the edge i-j make an odd cycle.
    [i] => up_i
    while parent[up_i[len(up_i) - 1]] != -1:
        up_i + [parent[up_i[len(up_i) - 1]]] => up_i
    [j] => up_j
    while parent[up_j[len(up_j) - 1]] != -1:
        up_j + [parent[up_j[len(up_j) - 1]]] => up_j
    # drop the shared part above the meeting point
    while len(up_i) > 1 and len(up_j) > 1 and up_i[len(up_i) - 2] == up_j[len(up_j) - 2]:
        up_i[0:len(up_i) - 1] => up_i
        up_j[0:len(up_j) - 1] => up_j
    [] => back
    len(up_j) - 2 => k
    while k >= 0:
        back + [up_j[k]] => back
        k - 1 => k
    return up_i + back

def suggestions(net, a):
    # People a is not friends with, ranked by how many friends they share
    # with a: [[person, shared], ...], most shared first, then by name order.
    net[1] => fr
    [0] * len(fr) => shared
    for f in fr[a]:
        for g in fr[f]:
            if g != a and not has(fr[a], g):
                shared[g] + 1 => shared[g]
    [] => out
    for i in [0:len(fr) - 1]:
        if shared[i] > 0:
            out + [[i, shared[i]]] => out
    for i in [1:len(out) - 1]:
        out[i] => x
        i - 1 => j
        while j >= 0 and out[j][1] < x[1]:
            out[j] => out[j + 1]
            j - 1 => j
        x => out[j + 1]
    return out
```

Python projection of network.eml:

```python
def index_of(names, name):
    for i in range(0, len(names)):
        if names[i] == name:
            return i
    return -1

def has(xs, x):
    for y in xs:
        if y == x:
            return True
    return False

def insert_sorted(xs, x):
    out = []
    done = False
    for y in xs:
        if not done and x < y:
            out = out + [x]
            done = True
        out = out + [y]
    if not done:
        out = out + [x]
    return out

def befriend(net, a, b):
    fr = net[1]
    if a == b or has(fr[a], b):
        return net
    fr[a] = insert_sorted(fr[a], b)
    fr[b] = insert_sorted(fr[b], a)
    return [net[0], fr]

def unfriend(net, a, b):
    fr = net[1]
    xa = []
    for y in fr[a]:
        if y != b:
            xa = xa + [y]
    xb = []
    for y in fr[b]:
        if y != a:
            xb = xb + [y]
    fr[a] = xa
    fr[b] = xb
    return [net[0], fr]

def visit(fr, i, group, seen):
    seen[i] = 1
    group = group + [i]
    for j in fr[i]:
        if seen[j] == 0:
            group = visit(fr, j, group, seen)
    return group

def groups(net):
    fr = net[1]
    seen = [0] * len(fr)
    out = []
    for i in range(0, len(fr)):
        if seen[i] == 0:
            out = out + [visit(fr, i, [], seen)]
    return out

def path(net, a, b):
    fr = net[1]
    came = [-1] * len(fr)
    seen = [0] * len(fr)
    queue = [a]
    seen[a] = 1
    head = 0
    while head < len(queue):
        i = queue[head]
        head = head + 1
        if i == b:
            out = [b]
            while out[0] != a:
                out = [came[out[0]]] + out
            return out
        for j in fr[i]:
            if seen[j] == 0:
                seen[j] = 1
                came[j] = i
                queue = queue + [j]
    return []

def two_teams(net):
    fr = net[1]
    colour = [-1] * len(fr)
    parent = [-1] * len(fr)
    for s in range(0, len(fr)):
        if colour[s] == -1:
            colour[s] = 0
            stack = [s]
            while len(stack) > 0:
                i = stack[len(stack) - 1]
                stack = stack[0:len(stack) - 1]
                for j in fr[i]:
                    if colour[j] == -1:
                        colour[j] = 1 - colour[i]
                        parent[j] = i
                        stack = stack + [j]
                    elif colour[j] == colour[i]:
                        return [False, odd_cycle(parent, i, j)]
    return [True, colour]

def odd_cycle(parent, i, j):
    up_i = [i]
    while parent[up_i[len(up_i) - 1]] != -1:
        up_i = up_i + [parent[up_i[len(up_i) - 1]]]
    up_j = [j]
    while parent[up_j[len(up_j) - 1]] != -1:
        up_j = up_j + [parent[up_j[len(up_j) - 1]]]
    while len(up_i) > 1 and len(up_j) > 1 and up_i[len(up_i) - 2] == up_j[len(up_j) - 2]:
        up_i = up_i[0:len(up_i) - 1]
        up_j = up_j[0:len(up_j) - 1]
    back = []
    k = len(up_j) - 2
    while k >= 0:
        back = back + [up_j[k]]
        k = k - 1
    return up_i + back

def suggestions(net, a):
    fr = net[1]
    shared = [0] * len(fr)
    for f in fr[a]:
        for g in fr[f]:
            if g != a and not has(fr[a], g):
                shared[g] = shared[g] + 1
    out = []
    for i in range(0, len(fr)):
        if shared[i] > 0:
            out = out + [[i, shared[i]]]
    for i in range(1, len(out)):
        x = out[i]
        j = i - 1
        while j >= 0 and out[j][1] < x[1]:
            out[j + 1] = out[j]
            j = j - 1
        out[j + 1] = x
    return out
```

## README

# P092 - Friend network

Who is friends with whom. The program finds the groups that hang together,
the degrees of separation between two people, whether everyone fits in two
teams with no two friends together, and friend suggestions. It starts with
ten people: a group of six, a triangle of three, and Jo on their own.

- `main.eml` - the menu, reading names, and the reports
- `network.eml` - adding and removing friendships, depth-first groups,
  breadth-first paths, two-colouring, odd rings, and suggestions

How each part works:

- Friendships go both ways; each person keeps a sorted list of friends.
- Groups, by depth-first search as in the corpus case
  `graph-dfs-recursive`: mark a person, then go into each friend not yet
  marked, recursively. Starting again from each unmarked person gives the
  groups - everyone reachable through friends, and nobody else.
- Degrees of separation, by breadth-first search: everyone one step away,
  then two, and so on. The first time the other person is reached, the
  chain found is as short as any.
- Two teams: colour people as the search reaches them, each in the other
  team from the friend it came by. If two friends end up in the same team,
  the paths from them back up the search meet, and with their own
  friendship they make a ring of odd length. Going round an odd ring, the
  teams would have to swap an odd number of times, which cannot end where
  it began. With no odd ring, the colouring is the two teams.
- Suggestions: people who are not your friends, ranked by how many friends
  you share.

What is checked: menu choices 1 to 8; names of letters, up to 10, of
people in the network (adding a friendship may bring in a new person, up
to 15 in all); nobody befriending themselves; removing only a friendship
that exists. An empty answer cancels.

Sessions: `sessions/basic.in` gives:
- the network and its three groups;
- Ana to Fay (4 steps), Ana to herself, and Ana to Gus (not connected);
- two teams refused because of the ring Ivo - Gus - Hana;
- suggestions for Ana (Dev, 2 in common) and for Jo (none);
- Ivo and Gus no longer friends, after which two teams work; Fay and Gus
  joining the two groups; and Kim joining as Jo's friend.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- Zed, who is not in the network;
- Ana with herself, Ana and Ben again, the name "Ana1", and removing a
  friendship that does not exist, then cancels.

Built on the verified corpus case `graph-dfs-recursive` (recursive
depth-first search, marking as it goes).