Daniel@0: function order = topological_sort(A)
Daniel@0: % TOPOLOGICAL_SORT Return the nodes in topological order (parents before children).
Daniel@0: % order = topological_sort(adj_mat)
Daniel@0: 
Daniel@0: n = length(A);
Daniel@0: indeg = zeros(1,n);
Daniel@0: zero_indeg = []; % a stack of nodes with no parents
Daniel@0: for i=1:n
Daniel@0:   indeg(i) = length(parents(A,i));
Daniel@0:   if indeg(i)==0
Daniel@0:     zero_indeg = [i zero_indeg];
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: t=1;
Daniel@0: order = zeros(1,n);
Daniel@0: while ~isempty(zero_indeg)
Daniel@0:   v = zero_indeg(1); % pop v
Daniel@0:   zero_indeg = zero_indeg(2:end);
Daniel@0:   order(t) = v;
Daniel@0:   t = t + 1;
Daniel@0:   cs = children(A, v);
Daniel@0:   for j=1:length(cs)
Daniel@0:     c = cs(j);
Daniel@0:     indeg(c) = indeg(c) - 1;
Daniel@0:     if indeg(c) == 0
Daniel@0:       zero_indeg = [c zero_indeg]; % push c 
Daniel@0:     end
Daniel@0:   end
Daniel@0: end