Skip to content

Instantly share code, notes, and snippets.

@mynameisvinn
Last active May 30, 2020 21:06
Show Gist options
  • Save mynameisvinn/9cea7f6d1dc41ef94c0867e8291dbda1 to your computer and use it in GitHub Desktop.
Save mynameisvinn/9cea7f6d1dc41ef94c0867e8291dbda1 to your computer and use it in GitHub Desktop.
test acyclicity by evaluating whether adjacency matrix is nilpontent
"""
graph examples collected from https://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/acyclic/
in the first example, we have an acylic graph. there exists k such its adjacency
matrix m^k == 0. because we cant produce a path of arbitrarily high length (eg
greater than k), the graph does not have a cycle.
in the second example, we have a cyclic graph. there is no k where its adjacency
matrix m^k == 0.
so, we can test for acyclicity by evaluating whether m^k == 0.
"""
# example 1 - acylic graph
m = np.array([[0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0]])
for _ in range(len(m)):
print(m)
print("-" * 15)
m = m.dot(m)
if np.sum(m) == 0:
print("finished")
break
# example 2- cyclic graph (it is directed but has cycles)
m = np.array([[0,1,0,0,0,0],
[0,0,1,1,0,0],
[0,0,0,0,0,0],
[0,0,0,0,1,0],
[0,0,0,0,0,1],
[0,0,1,1,0,0]])
for _ in range(len(m)):
print(m)
print("-" * 15)
m = m.dot(m)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment