TransitiveReduction.py

__author__ = "maxsu"
__version__ = "2019.09.21"
"""Compute the Transitive Reduction of a DAG via powers of its adjacency matrix.
This is a naive algorithm that implicitly computes all paths in the graph.
See [1] for more efficient methods.

Reference:
1. https://en.wikipedia.org/wiki/Transitive_reduction
"""

from Rhino.Geometry import Matrix

if not x.IsSquare:
  raise ValueError('Component requires square matrix')
  
n = x.ColumnCount

for i in range(n):
  for j in range(n):
    if not x[i,j] in [0,1]:
      raise ValueError('Component requires 0-1 matrix')
    if i == j and x[i,j] != 0:
      raise ValueError('Component requires loop-free graph')

p = x
q = Matrix(n,n)    # nxn zero-matrix

# Compute q = x^2 + x^3 ... + x^n
# Key idea: x^k[i,j] counts all length k paths from i to j
for i in range(n - 1):
    p = x * p
    q = q + p

# Normalize output (and catch cycles)
for i in range(n):
    for j in range(n):
        q[i,j] = min(q[i,j], 1)
        if i == j and q[i,j] != 0:
          raise ValueError('Component requires DAG')
    
# Negative identity matrix 
# Use this because q.Scale(-1) returns 'None'
j = Matrix(n,n)
for i in range(n):
    j[i,i] = -1

a = x + j * q