Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 reportsnetwork.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (22 lines)
0
x
3
Zed
6
Ana
Ana
6
Ana
Ben
6
Ana1
Ben
7
Ana
Fay
7
5
8
basic
interpreter: byte-equal== 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.
What was typed (29 lines)
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
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (network.py)
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