test acyclicity by evaluating whether adjacency matrix is nilpontent

test_acyclicity.py

"""
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)