diff toolboxes/FullBNT-1.0.7/graph/topological_sort.m @ 0:e9a9cd732c1e tip

first hg version after svn

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/toolboxes/FullBNT-1.0.7/graph/topological_sort.m	Tue Feb 10 15:05:51 2015 +0000
@@ -0,0 +1,30 @@
+function order = topological_sort(A)
+% TOPOLOGICAL_SORT Return the nodes in topological order (parents before children).
+% order = topological_sort(adj_mat)
+
+n = length(A);
+indeg = zeros(1,n);
+zero_indeg = []; % a stack of nodes with no parents
+for i=1:n
+  indeg(i) = length(parents(A,i));
+  if indeg(i)==0
+    zero_indeg = [i zero_indeg];
+  end
+end
+
+t=1;
+order = zeros(1,n);
+while ~isempty(zero_indeg)
+  v = zero_indeg(1); % pop v
+  zero_indeg = zero_indeg(2:end);
+  order(t) = v;
+  t = t + 1;
+  cs = children(A, v);
+  for j=1:length(cs)
+    c = cs(j);
+    indeg(c) = indeg(c) - 1;
+    if indeg(c) == 0
+      zero_indeg = [c zero_indeg]; % push c 
+    end
+  end
+end