Coverage for causalspyne/is_dag.py: 86%

1""" 

2DFS to check if is DAG, use python inner function to access global variable 

3""" 

4 

5 

6def is_dag(adjacency_matrix): 

7 """ 

8 adjaceny_matrx[u][v] \\neq 0 \\iff u <- v 

9 """ 

10 n = len(adjacency_matrix) 

11 set_visited = set() 

12 set_path = set() # A->[B]->[C]->A 

13 

14 def dfs(ind_node): 

15 set_visited.add(ind_node) 

16 set_path.add(ind_node) 

17 

18 for arrow_head in range(n): 

19 if adjacency_matrix[arrow_head][ind_node] != 0: # arrow head 

20 if arrow_head in set_path: # # A->B->C->A 

21 return False # not a DAG, bottom level return 

22 if arrow_head not in set_visited: 

23 if not dfs(arrow_head): # recursion 

24 return False # recursive return 

25 # exit of recursion: if arrow_head is visited 

26 set_path.remove(ind_node) 

27 return True 

28 

29 for ind_node in range(n): 

30 if ind_node not in set_visited: 

31 if not dfs(ind_node): 

32 return False 

33 

34 return True