Daniel@0: function Gs = mk_all_dags(N, order)
Daniel@0: % MK_ALL_DAGS generate all DAGs on N variables
Daniel@0: % G = mk_all_dags(N)
Daniel@0: %
Daniel@0: % G = mk_all_dags(N, order) only generates DAGs in which node i has parents from 
Daniel@0: % nodes in order(1:i-1). Default: order=[] (no constraints).
Daniel@0: %
Daniel@0: % G{i} is the i'th dag
Daniel@0: %
Daniel@0: % Note: the number of DAGs is super-exponential in N, so don't call this with N > 4.
Daniel@0: 
Daniel@0: if nargin < 2, order = []; end
Daniel@0: 
Daniel@0: use_file = 0;
Daniel@0: 
Daniel@0: global BNT_HOME
Daniel@0: fname = sprintf('%s/DAGS%d.mat', BNT_HOME, N);
Daniel@0: if use_file & exist(fname, 'file')
Daniel@0:   S = load(fname, '-mat');
Daniel@0:   fprintf('loading %s\n', fname);
Daniel@0:   Gs = S.Gs;
Daniel@0:   return;
Daniel@0: end
Daniel@0: 
Daniel@0: m = 2^(N*N);
Daniel@0: ind = ind2subv(2*ones(1,N^2), 1:m);
Daniel@0: Gs = {};
Daniel@0: j = 1;
Daniel@0: directed = 1;
Daniel@0: for i=1:m
Daniel@0:   dag = reshape(ind(i,:)-1, N, N);
Daniel@0:   if acyclic(dag, directed)
Daniel@0:     out_of_order = 0;
Daniel@0:     if ~isempty(order)
Daniel@0:       for k=1:N-1
Daniel@0: 	if any(dag(order(k+1:end), k))
Daniel@0: 	  out_of_order = 1;
Daniel@0: 	  break;
Daniel@0: 	end
Daniel@0:       end
Daniel@0:     end
Daniel@0:     if ~out_of_order
Daniel@0:       Gs{j} = dag;
Daniel@0:       j = j + 1;
Daniel@0:     end
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: if use_file
Daniel@0:   disp(['mk_all_dags: saving to ' fname '!']);
Daniel@0:   save(fname, 'Gs');
Daniel@0: end