Recursively find friends of friends

friend_of_a_friend.py

import itertools
from collections import defaultdict

d = {
  1: ["a", "b"],
  2: ["b", "c"],
  3: ["c", "d"]
}

def find_friend_of_friends(d):
  """Read in a dictionary with cluster keys and cluster
  member values, and return a dictionary in which
  all friends of friends have been clustered in the
  dictionary values"""

  # first create the inverse of the input d, such that
  # the values of d are keys in the new dictionary and
  # the values of the new dictionary are the clusters to which
  # the points belong

  # store the clusters to which a point belongs in a list
  value_to_clusters = defaultdict(list)
  for cluster in d.iterkeys():
    for value in d[cluster]:
      value_to_clusters[value].append(cluster)

  # now for each point, find that point's friends, where
  # a friend is defined by the fact that two points belong
  # to the same cluster
  friends = defaultdict(list)
  for value in value_to_clusters.iterkeys():
    linked_friends = []
    for cluster in value_to_clusters[value]:
      for friend in d[cluster]:
        linked_friends.append(friend)
    for linked_friend in linked_friends:
      friends[cluster].append(linked_friend)

  # remove duplicate entries from each value in the friends dict
  for cluster in friends.iterkeys():
    friends[cluster] = list(set(friends[cluster]))

  # remove any clusters whose values are subsets of other clusters
  clusters = friends.keys()
  for cluster_pair in itertools.combinations(clusters, 2):
    cluster_a_values = set(friends[cluster_pair[0]])
    cluster_b_values = set(friends[cluster_pair[1]])

    if cluster_a_values.issubset(cluster_b_values):
      friends.pop(cluster_pair[0], 0)
    elif cluster_b_values.issubset(cluster_a_values):
      friends.pop(cluster_pair[1], 0)

  # if the resulting dictionary is identical to the input
  # then we're done, else recurse
  if friends == d:
    print friends
    return friends

  else:
    return find_friend_of_friends(friends)

if __name__ == "__main__":
  find_friend_of_friends(d)