A graph, G, is a set of vertices (nodes) V and a set of edges (arcs) E that connect pairs of distinct nodes.
Ex.
from IPython.display import Image
Image('/home/cobalt/melvincabatuan.github.io/images/graph_ex.png')
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
]
N
b in N[a]
g in N[a]
len(N[f])
a, b, c, d, e, f, g, h = range(8)
M = [
[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
]
M
b in M[a]
g in M[a]
len(M[a])
M[a][b]
P = {
'a': set('bcdef'),
'b': set('ce'),
'c': set('d'),
'd': set('e'),
'e': set('f'),
'f': set('cgh'),
'g': set('fh'),
'h': set('fg')
}
P
a, b, c, d, e, f, g, h = range(8)
# a b c d e f g h
Q = [[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
Q
Q[a][b]
sum(Q[f])
a, b, c, d, e, f, g, h = range(8)
inf = float('inf')
# a b c d e f g h
W = [[ 0, 2, 1, 3, 9, 4, inf, inf], # a
[inf, 0, 4, inf, 3, inf, inf, inf], # b
[inf, inf, 0, 8, inf, inf, inf, inf], # c
[inf, inf, inf, 0, 7, inf, inf, inf], # d
[inf, inf, inf, inf, 0, 5, inf, inf], # e
[inf, inf, 2, inf, inf, 0, 2, 2], # f
[inf, inf, inf, inf, inf, 1, 0, 6], # g
[inf, inf, inf, inf, inf, 9, 8, 0]] # h
W
W[a][b] < inf
W[c][e] < inf
sum(1 for w in W[a] if w < inf) - 1