Skip to content

Instantly share code, notes, and snippets.

@psaitu

psaitu/Adjacency Matrix Implemented With Nested Lists

Last active September 12, 2015 06:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save psaitu/33403a67bc7cc4bceada to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save psaitu/33403a67bc7cc4bceada to your computer and use it in GitHub Desktop.
Download ZIP
Representing Graphs As Adjacency Matrices
Raw
Adjacency Matrix Implemented With Nested Lists
a, b, c, d, e, f, g, h = range(8)
N = [
[0, 1, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 1, 0]
]
N[a][b] # Neighbour membership
sum(N[f]) # Degree
Raw
Adjacency Matrix With Weights
a, b, c, d, e, f, g, h = range(8)
inf = float('inf')
N = [
[0, 2, 1, 3, 9, 4, inf, inf],
[inf, 0, 4, inf, 3, inf, inf, inf],
[inf, inf, 0, 8, inf, inf, inf, inf],
[inf, inf, inf, 0, 7, inf, inf, inf],
[inf, inf, inf, inf, 0, 5, inf, inf],
[inf, inf, 2, inf, inf, 0, 2, 2],
[inf, inf, inf, inf, inf, 1, 0, 6],
[inf, inf, inf, inf, inf, 9, 8, 0]
]
W[a][b] < inf # Neighbour membership
sum(1 for w in W[a] if w < inf) - 1 # Degree
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment