Coverage for src/causalspyne/utils_closure.py: 100%

1import numpy as np 

2 

3 

4def transitive_closure(adj_matrix): 

5 """ 

6 Floyd-Warshall algorithm, note that this algorithm is agnostic w.r.t. 

7 the edge convention: (i,j) implies either i<-j or i->j is the same 

8 for the algorithm 

9 """ 

10 num_vertex = len(adj_matrix) 

11 closure = np.array(adj_matrix, dtype=bool) 

12 

13 for k in range(num_vertex): # intermiediate connection 

14 for i in range(num_vertex): 

15 for j in range(num_vertex): 

16 # as long as one of the three cases result in connection, then 

17 # i, j should be connected 

18 closure[i][j] = closure[i][j] or \ 

19 (closure[i][k] and closure[k][j]) 

20 # i-k, k-j implies i-j 

21 # here the mathematical relation i-j or i~j, can mean 

22 # both i->j or j<-i 

23 return closure 

24 

25 

26def ancestor_matrix(adj_matrix): 

27 num_vertex = len(adj_matrix) 

28 closure = transitive_closure(adj_matrix) 

29 ancestor = np.zeros((num_vertex, num_vertex), dtype=bool) 

30 

31 for i in range(num_vertex): 

32 for j in range(num_vertex): 

33 if i != j: 

34 ancestor[i][j] = closure[i][j] 

35 return ancestor