In this problem you’ll implement a version of Facebook’s friend suggestions (“pe

Question

In this problem you’ll implement a version of Facebook’s friend suggestions (“people you may know”). Write a Python function suggest_friends(adj, s, k) where adj is the adjacency 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-friendsof-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(n + m).

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 I
• Subjects

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