unweightedGraph = { 
      "A" : [ "B", "G" ],
      "B" : [ "A", "C" ],
      "C" : [ "B", "H" ],
      "D" : [ "F" ],
      "E" : [ "G", "H" ],
      "F" : [ "D" ],
      "G" : [ "A", "E", "H" ],
      "H" : [ "C", "E", "G" ]
     }

weightedGraph = { 
      "A" : [ ["B", 5], ["G", 2] ],
      "B" : [ ["A", 5], ["C", 3] ],
      "C" : [ ["B", 3], ["H", 9] ],
      "D" : [ ["F", 4] ],
      "E" : [ ["G", 1], ["H", 7] ],
      "F" : [ ["D", 4] ],
      "G" : [ ["A", 2], ["E", 1], ["H", 2] ],
      "H" : [ ["C", 9], ["E", 7], ["G", 2] ]
     }

###

# nodes
def printNodes(g):
    for node in g:
        print(node)

# edges
def printEdges(g):
    for node in g:
        for neighbor in g[node]:
            print(node, "-", neighbor)

# neighbors
def printNeighbors(g, node):
    for neighbor in g[node]:
        print(neighbor)

# a particular edge
def printEdge(g, start, end):
    for neighbor in g[start]:
        neighborNode = neighbor[0]
        edgeWeight = neighbor[1]
        if neighborNode == end:
            print(edgeWeight)

###
            
g = { "Jon" : [ "Arya", "Tyrion" ],
      "Tyrion" : [ "Jaime", "Pod", "Jon" ],
      "Arya" : [ "Jon" ],
      "Jaime" : [ "Tyrion", "Brienne" ],
      "Brienne" : [ "Jaime", "Pod" ],
      "Pod" : [ "Tyrion", "Brienne", "Jaime" ],
      "Ramsay" : [ ]
    }

def mostPopularPerson(g):
    mostPopPerson = None
    mostFriends = -1
    for person in g:
        friendList = g[person]
        if len(friendList) > mostFriends:
            mostPopPerson = person
            mostFriends = len(friendList)
    return mostPopPerson

###

def makeInviteList(g, host):
    invite = g[host] + []
    for friend in g[host]:
        for friendOfFriend in g[friend]:
            if friendOfFriend != host and friendOfFriend not in invite:
                invite.append(friendOfFriend)
    return invite

###

"""
Given an unweighted graph of a social network (like in the previous two examples)
and two nodes (people) in the graph, return a list of the friends that those two
people have in common.
"""

def friendsInCommon(g, p1, p2):
    result = []
    for friend in g[p1]:
        if friend in g[p2]:
            result.append(friend)
    return result