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