3. 25 points In this problem you\'ll implement a version of Facebook\'s friend s

Question

3. 25 points In this problem you'll implement a version of Facebook's friend suggestions ("peo- ple you may know"). Write a Python function suggest friends (adj, s, k) where adj is the adjaceney lists for an undirected graph where nodes are people and edges represent friendships, s is the index of a person, and k is a positive integer. It should return a list of exactly k people (indices) who are not s or s's friends but are as close as possible to s in the graph. You may assume there are always at least k such people. You may break ties arbitrarily;e.g., if k 10 and s has 5 friends, 6 friends-of-friends, and 7 friends-of-friends- of-friends, then the return list should include all 6 friends-of-friends followed by any 4 of the friends-of-friends-of-friends. Your program should be a modification of BFS and run in time O(nm)

Explanation / Answer

Python code:

def suggest_friends(adj, s, k):
suggest = []
visited = [False for i in range(len(adj) + 1)]
que = [s]
visited[s] = True
current_level = 0
# Typical bfs algorithm
while len(que) > 0:
next_level = []
while len(que) > 0:
popped = que.pop()
for i in range(1, len(adj)):
if adj[popped][i] == 1 and not visited[i]:
visited[i] = True
next_level.append(i)
current_level += 1

# This is the only modification of bfs
# Checking if this level people are friends of friends or not
if current_level >= 2:
for friend_of_friend in next_level:
suggest.append(friend_of_friend)
if len(suggest) == k:
return suggest
que = next_level[:]

if _name_ == '__main__':
n = int(input("Enter number of people: "))
adjMat = [[0 for i in range(n + 1)] for j in range(n + 1)]
edges = int(input("Enter number of friendships: "))
for i in range(edges):
a, b = [int(number) for number in input("Enter source and destination separated by space: ").split()]
# Graph is bidirectional
adjMat[a][b] = 1
adjMat[b][a] = 1
k = int(input("Enter number of suggestions: "))
s = int(input("Enter the source number: "))
suggestions = suggest_friends(adjMat, s, k)
print("Suggestions for", s, "are", *suggestions)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.