wolffd@0: function b = acyclic(adj_mat, directed)
wolffd@0: % ACYCLIC Returns true iff the graph has no (directed) cycles.
wolffd@0: % b = acyclic(adj_mat, directed)
wolffd@0: 
wolffd@0: adj_mat = double(adj_mat);
wolffd@0: if nargin < 2, directed = 1; end
wolffd@0: 
wolffd@0: % e.g., G =
wolffd@0: % 1 -> 3
wolffd@0: %      |
wolffd@0: %      v
wolffd@0: % 2 <- 4   
wolffd@0: % In this case, 1->2 in the transitive closure, but 1 cannot get to itself.
wolffd@0: % If G was undirected, 1 could get to itself, but this graph is not cyclic.
wolffd@0: % So we cannot use the closure test in the undirected case.
wolffd@0: 
wolffd@0: if directed
wolffd@0:   R = reachability_graph(adj_mat);
wolffd@0:   b = ~any(diag(R)==1);
wolffd@0: else
wolffd@0:   [d, pre, post, cycle] = dfs(adj_mat,[],directed);
wolffd@0:   b = ~cycle;    
wolffd@0: end