#Tyler Moore
#CS2123
#Code used in graphtsp.pdf lecture slides
#Portions of code written by Magnus Hietland

#Graph Representation
#Option 1: Adjacency Sets (vertices as numbers)
a, b, c, d, e, f, g, h = range(8)
N = [
    {b, c, d, e, f},    # a
    {c, e},             # b
    {d},                # c
    {e},                # d
    {f},                # e
    {c, g, h},          # f
    {f, h},             # g
    {f, g}              # h
]

b in N[a]
len(N[f])

#Option 2: Adjacency Lists (vertices as numbers)
a, b, c, d, e, f, g, h = range(8)
N = [
    [b, c, d, e, f],    # a
    [c, e],             # b
    [d],                # c
    [e],                # d
    [f],                # e
    [c, g, h],          # f
    [f, h],             # g
    [f, g]              # h
]

b in N[a]
len(N[f])

#Option 3: Adjacency Dictionaries with Edge Weights
a, b, c, d, e, f, g, h = range(8)
N = [
    {b:2, c:1, d:3, e:9, f:4},#a
    {c:4, e:3},               #b
    {d:8},                    #c
    {e:7},                    #d
    {f:5},                    #e
    {c:2, g:2, h:2},          #f
    {f:1, h:6},               #g
    {f:9, g:8}                #h
]

b in N[a]
N[a][b]]

#Option 4: Dictionaries with Adjacency Sets
N = {
    'a': set('bcdef'),
    'b': set('ce'),
    'c': set('d'),
    'd': set('e'),
    'e': set('f'),
    'f': set('cgh'),
    'g': set('fh'),
    'h': set('fg')
}

b in N[a]
len(N[f])

#Option 5: Adjacency Matrix (nested lists)

a, b, c, d, e, f, g, h = range(8)
#     a b c d e f g h
N = [[0,1,1,1,1,1,0,0], # a
     [0,0,1,0,1,0,0,0], # b
     [0,0,0,1,0,0,0,0], # c
     [0,0,0,0,1,0,0,0], # d
     [0,0,0,0,0,1,0,0], # e
     [0,0,1,0,0,0,1,1], # f
     [0,0,0,0,0,1,0,1], # g
     [0,0,0,0,0,1,1,0]] # h

b in N[a]
len(N[f])

#Option 6: Weighted Adjacency Matrix (nested lists)
a, b, c, d, e, f, g, h = range(8)
_ = float('inf')

#     a b c d e f g h

W = [[0,2,1,3,9,4,_,_], # a
     [_,0,4,_,3,_,_,_], # b
     [_,_,0,8,_,_,_,_], # c
     [_,_,_,0,7,_,_,_], # d
     [_,_,_,_,0,5,_,_], # e
     [_,_,2,_,_,0,2,2], # f
     [_,_,_,_,_,1,0,6], # g
     [_,_,_,_,_,9,8,0]] # h
    
inf = float('inf')
#>>> W[a][b] < inf   # Neighborhood membership
True
#>>> W[c][e] < inf   # Neighborhood membership
False
#>>> sum(1 for w in W[a] if w < inf) - 1  # Degree


#Topological Sort (induction-based iterative algorithm)
def topsort(G):
    count = dict((u, 0) for u in G)#The in-degree for each node
    for u in G:
        for v in G[u]:
            count[v] += 1    #Count every in-edge
    Q = [u for u in G if count[u] == 0] # Valid initial nodes
    S = []                   #The result
    while Q:                 #While we have start nodes...
        u = Q.pop()          #Pick one
        S.append(u)          #Use it as first of the rest
        for v in G[u]:
            count[v] -= 1    #"Uncount" its out-edges
            if count[v] == 0:#New valid start nodes?
                Q.append(v)  #Deal with them next
    return S

G = {'a': set('bf'), 'b': set('cdf'), 'c': set('d'), 'd': set('ef'), 'e': set('f'), 'f': set()}
topsort(G)