Merge pull request #1 from ziejd2/octave_php_separate

Octave php separate

1 files changed, 23 insertions, 0 deletions

diff --git a/sourcecodes/bnt-master/graph/acyclic.m b/sourcecodes/bnt-master/graph/acyclic.m
new file mode 100644
index 00000000..0b497d73
--- /dev/null
+++ b/sourcecodes/bnt-master/graph/acyclic.m
@@ -0,0 +1,23 @@
+function b = acyclic(adj_mat, directed)
+% ACYCLIC Returns true iff the graph has no (directed) cycles.
+% b = acyclic(adj_mat, directed)
+
+adj_mat = double(adj_mat);
+if nargin < 2, directed = 1; end
+
+% e.g., G =
+% 1 -> 3
+%      |
+%      v
+% 2 <- 4   
+% In this case, 1->2 in the transitive closure, but 1 cannot get to itself.
+% If G was undirected, 1 could get to itself, but this graph is not cyclic.
+% So we cannot use the closure test in the undirected case.
+
+if directed
+  R = reachability_graph(adj_mat);
+  b = ~any(diag(R)==1);
+else
+  [d, pre, post, cycle] = dfs(adj_mat,[],directed);
+  b = ~cycle;    
+end