Task 2.sagews

import numpy as np
G_sage = DiGraph()
G_sage.add_edges((
('A', 'D'), ('A', 'C'), ('N', 'A'), ('A', 'G'), ('D', 'B'), ('B', 'K'),
('K', 'D'), ('C', 'D'), ('C', 'E'), ('E', 'N'), ('N', 'G'), ('E', 'F'),
('E', 'H'), ('H', 'G'), ('F', 'I'), ('J', 'I'), ('M', 'F'), ('M', 'L'), ('L', 'M')))
E = G_sage.edges()
V = G_sage.vertices()

def clip(m):
    return matrix(np.clip(m.numpy(), 0, 1))

G = G_sage.adjacency_matrix()
print G
H = DiGraph(G).plot(layout='circular')
H.show()
H.save('T2_G.pdf')
with open('T2_G.tex', 'w') as f: f.write(latex(G))
print

G2 = clip(G*G)
print G2
H = DiGraph(G2).plot(layout='circular')
H.show()
H.save('T2_G2.pdf')
with open('T2_G2.tex', 'w') as f: f.write(latex(G2))
print

G3 = clip(G*G*G)
print G3
H = DiGraph(G3).plot(layout='circular')
H.show()
H.save('T2_G3.pdf')
with open('T2_G3.tex', 'w') as f: f.write(latex(G3))

[0 0 1 1 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 1 0 0 0] [0 0 0 1 1 0 0 0 0 0 0 0 0 0] [0 1 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 1 0 0 0 0 0 1] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 0 0 1 0 0] [1 0 0 0 0 0 1 0 0 0 0 0 0 0]

[0 1 0 1 1 0 0 0 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 0] [0 1 0 0 0 1 0 1 0 0 0 0 0 1] [0 0 0 0 0 0 0 0 0 0 1 0 0 0] [1 0 0 0 0 0 1 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 1 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 1 0] [0 0 1 1 0 0 1 0 0 0 0 0 0 0]

[0 1 0 0 0 1 0 1 0 0 1 0 0 1] [0 1 0 0 0 0 0 0 0 0 0 0 0 0] [1 0 0 0 0 0 1 0 1 0 1 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 1 1 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 1 0] [0 0 0 0 0 1 0 0 0 0 0 1 0 0] [0 1 0 1 1 0 0 0 0 0 0 0 0 0]

# Transitive closure
G = G_sage.adjacency_matrix() + matrix.identity(len(V))

prev_G = G
A = clip(G*G)
i = 1
while prev_G != A:
    prev_G = A
    A = clip(A*A)
    i += 1
A -= matrix.identity(len(V))

print A
print "The transitive closure matrix converged after %d iterations" % i
H = DiGraph(A).plot(layout='circular')
H.show()
H.save('T2_tc.pdf')
with open('T2_tc.tex', 'w') as f: f.write(latex(G3))

[0 1 1 1 1 1 1 1 1 0 1 0 0 1] [0 0 0 1 0 0 0 0 0 0 1 0 0 0] [1 1 0 1 1 1 1 1 1 0 1 0 0 1] [0 1 0 0 0 0 0 0 0 0 1 0 0 0] [1 1 1 1 0 1 1 1 1 0 1 0 0 1] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 1 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 1 0 0 0 1 0] [0 0 0 0 0 1 0 0 1 0 0 1 0 0] [1 1 1 1 1 1 1 1 1 0 1 0 0 0] The transitive closure matrix converged after 4 iterations

G = G_sage.adjacency_matrix() + matrix.identity(len(V))
G2=G*G ; G4=G2*G2 ; G8=G4*G4 ; G16=G8*G8
A = clip(G16) - matrix.identity(len(V))
print A
H = DiGraph(A).plot(layout='circular')
H.show()

[0 1 1 1 1 1 1 1 1 0 1 0 0 1] [0 0 0 1 0 0 0 0 0 0 1 0 0 0] [1 1 0 1 1 1 1 1 1 0 1 0 0 1] [0 1 0 0 0 0 0 0 0 0 1 0 0 0] [1 1 1 1 0 1 1 1 1 0 1 0 0 1] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 1 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 1 0 0 0 1 0] [0 0 0 0 0 1 0 0 1 0 0 1 0 0] [1 1 1 1 1 1 1 1 1 0 1 0 0 0]

A = G_sage.adjacency_matrix()
for k in range(len(V)):
    for i in range(len(V)):
        if not A[i, k]: continue
        for j in range(len(V)):
            if A[k, j]:
                A[i, j] = True
print A
H = DiGraph(A).plot(layout='circular')
H.show()

[1 1 1 1 1 1 1 1 1 0 1 0 0 1] [0 1 0 1 0 0 0 0 0 0 1 0 0 0] [1 1 1 1 1 1 1 1 1 0 1 0 0 1] [0 1 0 1 0 0 0 0 0 0 1 0 0 0] [1 1 1 1 1 1 1 1 1 0 1 0 0 1] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 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 1 0 0 1 1 0] [0 0 0 0 0 1 0 0 1 0 0 1 1 0] [1 1 1 1 1 1 1 1 1 0 1 0 0 1]