I have created a program but I feel the def common(friendships, person1, person2) function can be more efficient, if anyone has any good idea how I can improve it I would appreciate it.
from My_graph import Graph
def friends_of_friends(friendships, person):
"""Return the set of friends of the person's friends.
Don't return people that are already friends of person.
"""
assert person in friendships.nodes()
result = set()
people = friendships.nodes()
for person1 in people:
for person2 in people:
# the () around the whole condition are necessary to
# break the condition over multiple lines
if (friendships.has_edge(person1, person2) and
friendships.has_edge(person2, person) and
not friendships.has_edge(person1, person) and
person1 != person):
result.add(person1)
return result
def common(friendships, person1, person2):
"""Return the number of common friends of person1 and person2."""
assert person1 != person2
assert person1 in friendships.nodes()
assert person2 in friendships.nodes()
mutual = 0
for person in friendships.nodes():
if (friendships.has_edge(person, person1) and
friendships.has_edge(person, person2)):
mutual = mutual + 1
return mutual
def suggested_friends(friendships, person):
"""Return a list of suggested people for person to befriend.
Each suggestion is a friend of a friend of person but isn't person's friend.
The suggestions are ordered from most to fewest mutual friends with person.
"""
assert person in friendships.nodes()
scored_suggestions = []
for friend_of_friend in friends_of_friends(friendships, person):
score = common(friendships, person, friend_of_friend)
scored_suggestions.append((score, friend_of_friend))
scored_suggestions.sort(reverse=True)
suggestions = []
for (score, suggestion) in scored_suggestions:
suggestions.append(suggestion)
return suggestions
class Graph:
# Representation
# --------------
# We use the adjacency list representation, but with sets instead of lists.
# The graph is a dictionary where each key is a node and
# the corresponding value is the set of the node's neighbours.
# The graph being undirected, each edge is represented twice.
# For example, the dictionary {1: {2, 3}, 2: {1}, 3: {1}} represents a
# graph with three nodes and two edges connecting node 1 with the other two.
# Creator
# -------
def __init__(self):
"""Initialise the empty graph."""
self.graph = dict()
# Inspectors
# ----------
def has_node(self, node):
"""Return True if the graph contains the node, otherwise False."""
return node in self.graph
def has_edge(self, node1, node2):
"""Check if there's an edge between the two nodes.
Return False if the edge or either node don't exist, otherwise True.
"""
return self.has_node(node1) and node2 in self.graph[node1]
def neighbours(self, node):
"""Return the set of neighbours of node.
Assume the graph has the node.
"""
assert self.has_node(node)
# copy the set of neighbours, to prevent clients modifying it directly
result = set()
for neighbour in self.graph[node]:
result.add(neighbour)
return result
def nodes(self):
"""Return the set of all nodes in the graph."""
result = set()
for node in self.graph:
result.add(node)
return result
def edges(self):
"""Return the set of all edges in the graph.
An edge is a tuple (node1, node2).
Only one of (node1, node2) and (node2, node1) is included in the set.
"""
result = set()
for node1 in self.nodes():
for node2 in self.nodes():
if self.has_edge(node1, node2):
if (node2, node1) not in result:
result.add((node1, node2))
return result
def __eq__(self, other):
"""Implement == to check two graphs have the same nodes and edges."""
nodes = self.nodes()
if nodes != other.nodes():
return False
for node1 in nodes:
for node2 in nodes:
if self.has_edge(node1, node2) != other.has_edge(node1, node2):
return False
return True
# Breadth-first search
# --------------------
def bfs(self, start):
"""Do a breadth-first search of the graph, from the start node.
Return a list of nodes in visited order, the first being start.
Assume the start node exists.
"""
assert self.has_node(start)
# Initialise the list to be returned.
visited = []
# Keep the nodes yet to visit in another list, used as a queue.
# Initially, only the start node is to be visited.
to_visit = [start]
# While there are nodes to be visited:
while to_visit != []:
# Visit the next node at the front of the queue.
next_node = to_visit.pop(0)
visited.append(next_node)
# Look at its neighbours.
for neighbour in self.neighbours(next_node):
# Add node to the back of the queue if not already
# visited or not already in the queue to be visited.
if neighbour not in visited and neighbour not in to_visit:
to_visit.append(neighbour)
return visited
# Depth-first search
# ------------------
def dfs(self, start):
"""Do a depth-first search of the graph, from the start node.
Return a list of nodes in visited order, the first being start.
Assume the start node exists.
"""
assert self.has_node(start)
# Use the BFS algorithm, but keep nodes to visit in a stack.
visited = []
to_visit = [start]
while to_visit != []:
next_node = to_visit.pop()
visited.append(next_node)
for neighbour in self.neighbours(next_node):
if neighbour not in visited and neighbour not in to_visit:
to_visit.append(neighbour)
return visited
# Modifiers
# ---------
def add_node(self, node):
"""Add the node to the graph.
Do nothing if the graph already has the node.
Assume the node is of an immutable type.
"""
if not self.has_node(node):
self.graph[node] = set()
def add_edge(self, node1, node2):
"""Add to the graph an edge between the two nodes.
Add any node that doesn't exist.
Assume the two nodes are different and of an immutable type.
"""
assert node1 != node2
self.add_node(node1)
self.add_node(node2)
self.graph[node1].add(node2)
self.graph[node2].add(node1)
friendshipsgraph and callcommon(). \$\endgroup\$