camir-aes2014: toolboxes/FullBNT-1.0.7/graph/acyclic.m annotate

first hg version after svn

rev	line source
wolffd@0	1 function b = acyclic(adj_mat, directed)
wolffd@0	2 % ACYCLIC Returns true iff the graph has no (directed) cycles.
wolffd@0	3 % b = acyclic(adj_mat, directed)
wolffd@0	4
wolffd@0	5 adj_mat = double(adj_mat);
wolffd@0	6 if nargin < 2, directed = 1; end
wolffd@0	7
wolffd@0	8 % e.g., G =
wolffd@0	9 % 1 -> 3
wolffd@0	10 % \|
wolffd@0	11 % v
wolffd@0	12 % 2 <- 4
wolffd@0	13 % In this case, 1->2 in the transitive closure, but 1 cannot get to itself.
wolffd@0	14 % If G was undirected, 1 could get to itself, but this graph is not cyclic.
wolffd@0	15 % So we cannot use the closure test in the undirected case.
wolffd@0	16
wolffd@0	17 if directed
wolffd@0	18 R = reachability_graph(adj_mat);
wolffd@0	19 b = ~any(diag(R)==1);
wolffd@0	20 else
wolffd@0	21 [d, pre, post, cycle] = dfs(adj_mat,[],directed);
wolffd@0	22 b = ~cycle;
wolffd@0	23 end

Mercurial > hg > camir-aes2014