Six Degrees of Separation

It is based on the idea that all human beings in the world are six or fewer steps away from each other so that a chain of “a friend of a friend” statements can be made to connect any two people in a maximum of six steps.

Using a Graph:

The connections between the nodes will represent the friendship relationships between two members.

We will then ask the end-user to enter 2 names and use an algorithm to find out the shortest friendship chain between these two members (if it exists).

Using Graphs in Python

• Method 1: Adjacency Matrix: Using a 2D array (or list of lists in Pyhon)
• Method 2: Us: Using a hash table (dictionary) of lists

Let’s investigate both approaches.

Method #1: Implementing a graph using an adjacency matrix

An adjacency matrix is a 2D array that has the same number of rows and columns: 1 row and 1 column per node of the graph.

Here is how we could implement this adjacency matrix in Python:

members =    ["Eshan","Sonia","Jackson","Naomi","Zheng","Kamal","Oliver","May"]

#Adjacency Matrix: (2D array to store friendship data)
friendship = [[False , True  , False   , False , False , False , False  , True ], #Eshan
              [True  , False , True    , False , False , False , False  , False], #Sonia
              [False , True  , False   , True  , False , False , False  , False], #Jackson
              [False , False , True    , False , False , True  , False  , True ], #Naomi
              [False , False , False   , False , False , False , False  , False], #Zheng
              [False , False , False   , True  , True  , False , True   , False], #Kamal
              [False , False , False   , False , True  , True  , False  , False], #Oliver
              [True  , False , False   , True  , False , False , False  , False]  #May
             ]

Now that we have saved this data into our code, we can create a small program to query this data. For instance, let’s write a program that asks the user to enter the names of two members of our social network and output whether these two members are friends or not.

Note that using an adjacency matrix is not recommended for very large graphs where you have two many nodes. This is because, for a graph of n nodes the resulting 2D array would contain n² values. This is can quickly be too demanding in terms of memory requirements (O(n²) Big O Notation)

Method #2: Implementing a graph using a hash table

An alternative approach to implement a graph is to use a hash table where each node of the graph is a key, and the value for each key is the list of adjacent nodes of this node. For instance, here is the Python code to represent the connections from our friendship graph:

members = {'Naomi': ['Jackson', 'May', 'Kamal'],
'May': ['Eshan', 'Naomi'],
'Jackson': ['Naomi', 'Sonia'],
'Kamal': ['Oliver', 'Naomi', 'Zheng'],
'Eshan': ['Sonia','May'],
'Sonia': ['Eshan','Jackson'],
'Zheng': ['Kamal','Oliver'],
'Oliver': ['Zheng','Kamal']
}

This graph is a hash table (a.k.a dictionary) where the keys are the nodes of the graph. For each key, the corresponding value is a list containing the nodes that are connected by a direct arc from this node.

Let’s see how we can use this graph to complete our friendship checker program:

Shortest Path Algorithm

Our shortest path algorithm will be based on a recursive function used to find all the friendship chains/paths that can been found between two members and identify which one is the shortest path (The path that has the smallest number of nodes).

To make this algorithm more effective we also have a stopping condition to stop exploring a path that would be longer than the shortest path found so far.

def find_shortest_path(graph, start, end, shortestLength=-1, path=[]):
  path = path + [start]
  if start == end:
    return path
  if not start in graph:
    return None
  shortest = None
  for node in graph[start]:
    if node not in path:
      if shortestLength==-1 or len(path)<(shortestLength-1):
        newpath = find_shortest_path(graph, node, end, shortestLength, path)
        if newpath:
          if not shortest or len(newpath) < len(shortest):
            shortest = newpath
            shortestLength = len(newpath)  
  return shortest

Python Code

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area