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

wG = {
      "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] ]
     }

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



# Print all the nodes, one by one
def printNodes(g):
    for node in g:
        print(node)

print("Nodes of uG:")
printNodes(uG)





# Return list of neighbors of node (g is unweighted)
def getNeighbors(g, node):
    return g[node]

print("Neighbors of node G in uG:", getNeighbors(uG, "G"))






# Return list of neighbors of node (g is weighted)
def getNeighborsWeighted(g, node):
    neighbors = []
    for pair in g[node]: # example pair = ["A", 5]
        neighbors.append(pair[0])
    return neighbors

print("Neighbors of node H in wG:",\
      getNeighborsWeighted(wG, "H"))




# Print all edges in g, as node-node
#  e.g. "A-B" to indicate an edge between A and B
def printEdges(g):
    for node in g:
        neighbors = g[node]
        for neighbor in neighbors:
            print(node + "-" + neighbor)

print("Edges in uG:")
printEdges(uG)





# Return weight of edge between node1 and node2
#  May assume that the edge does actually exist
def getEdgeWeight(g, node1, node2):
    for pair in g[node1]: # list of [neighbor, weight] lists
        if pair[0] == node2:
            return pair[1]

print("Weight of edge H-E in wG:",\
      getEdgeWeight(wG, "H", "E"))





# Return the person with the most friends in g
def findMostPopular(g):
    mostFriends = -1
    mostPopular = None
    for node in g:
        if len(g[node]) > mostFriends:
            mostFriends = len(g[node])
            mostPopular = node
    return mostPopular

print("Most popular person in people:",\
      findMostPopular(people))






# Return a list of all the friends of person,
#  as well as all the friends of those people
def makeInviteList(g, person):
    invite = g[person] + [] # Break alias!!
    for friend in g[person]:
        for friendOfFriend in g[friend]:
            if friendOfFriend != person and friendOfFriend not in invite:
                invite.append(friendOfFriend)
    return invite
    

print("Invite list for Tyrion:",\
      makeInviteList(people, "Tyrion"))





# Return a list of people who are friends with BOTH p1 and p2
def friendsInCommon(g, p1, p2):
    common = []
    for friend in g[p1]:
        if friend in g[p2]:
            common.append(friend)
    return common

assert(friendsInCommon(people, "Jon", "Jaime") == ["Tyrion"])