Get connection degree in a graph using BFS.

get_connection_degree.py

from collections import deque

# When you open LinkedIn profile, it displays a number that shows how closely
# you're connected to that person.
# 1st degree connection are people you're directly connected with
# 2nd degree connections are people who are connected to your first degree connections
# 3rd degree connections are people who are connected to your 2nd degree connections
# etc.


# Let's assume you're given a list of pairs, where each pair the
# names of two LinkedIn profiles who are directly connected
# Given a list of connected profiles
# and source and target profiles
# return the connection degree between those two profiles


connections = [
    ("Bosco", "Clement"),
    ("Clement", "Geogreen"),
    ("Bosco", "Samuel"),
    ("Samuel", "Smith"),
    ("Smith", "James"),
    ("Geogreen", "James")
]

# example of how to find the neighbors
# of a node. This works, but it's O(n).
# This would make this expensive
# if we had to call it for each node
# we visit in the graph.
# For that reason, we don't use this.
def neighbors(connections, name):
    result = []
    for conn in connections:
        if conn[0] == name:
            result.append(conn[1])
        elif conn[1] == name:
            result.append(conn[0])
    return result

def get_connection_degree(connections, source_profile, target_profile):
    # build graph as dictionary to make it fast to find neighbors
    # of a node.
    # Building the graph is O(m) where m is the number of edges
    # but it will make it fast to find neighbors of a node O(1)
    # This is an example of using more memory to speed up things
    # later on, i.e. caching.
    graph = {}
    for connection in connections:
        left, right = connection
        if left not in graph:
            graph[left] = [right]
        else:
            neighbors = graph[left]
            neighbors.append(right)
        
        if right not in graph:
            graph[right] = [left]
        else:
            neighbors = graph[right]
            neighbors.append(left)
    
    # we should have a graph populated
    # such that for each node in graph,
    # graph[node] will return the nighbors of node in O(1)


    # search through the graph to find the number of edges between them
    # search using BFS
    # go through vertices starting from the root
    # we have a queue
    queue = deque()
    # we have a visited set
    visited = set()
    # start with root
    # append root to the queue
    queue.append((source_profile, 0))
    visited.add(source_profile)
    while len(queue) > 0:
        node, distance = queue.popleft()
        if node == target_profile:
            print("distance", node, distance)
            return distance
            
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    
    # There's no path between the source and target
    return -1
    # add root to visited list
    # while queue is not empty:
    #  remove the next node from the queue
    #   find neighbors of the node
    #       if node is in visited list:
    #           add neighbor to visited lis
    ##          append neighbor to the queue
    ##          if the neighbor target:
    ###             return distance



assert(get_connection_degree(connections, "Bosco", "Clement") == 1)
assert(get_connection_degree(connections, "Clement", "Smith") == 3)
assert(get_connection_degree(connections, "Geogreen", "Samuel") == 3)