Problem 4

The relationship "friend" is often symmetric, meaning that if I am your friend, you are my friend. Implement a MapReduce algorithm to check whether this property holds. Generate a list of all non-symmetric friend relationships.

Map Input

Each input record is a 2 element list [personA, personB] where personA is a string representing the name of a person and personB is a string representing the name of one of personA's friends. Note that it may or may not be the case that the personA is a friend of personB.

Reduce Output

The output should be all pairs (friend, person) such that (person, friend) appears in the dataset but (friend, person) does not.

You can test your solution to this problem using friends.json:

Answer:

import MapReduce

import json

import sys

# Part 1

mr = MapReduce.MapReduce()

people = ["Myriel","Geborand", "Champtercier", "Count", "OldMan", "Valjean", "Napoleon", "MlleBaptistine", "MmeMagloire", "Labarre", "Marguerite", "MmeDeR", "Isabeau", "Fantine", "Cosette", "Simplice", "Woman1", "Judge", "Woman2", "Gillenormand", "MlleGillenormand", "Babet", "Montparnasse"]

persons = []

# Part 2

def mapper(record):

    for friend1 in people:

        for friend2 in people:

          if friend1 == friend2:

             continue

          if friend1 == record[0] and friend2 == record[1]:

             mr.emit_intermediate((friend1,friend2), 1)

          else:

             mr.emit_intermediate((friend1,friend2), 0)

# Part 3

def reducer(key, list_of_values):

    #print(repr((key, list_of_values)))

    if 1 in list_of_values:

         pass

    else:

        mr.emit(key)

# Part 4

inputdata = open(sys.argv[1])

mr.execute(inputdata, mapper, reducer)

Sample output:

["MlleBaptistine", "Myriel"]

["MlleBaptistine", "MmeMagloire"]

["MlleBaptistine", "Valjean"]

["Fantine", "Valjean"]

["Cosette", "Valjean"]