Generating Markov-Equivalent DAGs in BNT

By Imme Ebert-Uphoff

This page describes how to generate Markov-equivalent DAGs in Matlab's Bayes Net Toolbox BNT.

First the supporting files:

You can download all four files using this ZIP-FILE.
Thanks to Daniel Eaton for extensive testing of these files and detailed bug reports.

Please see the comments at the beginning of each file for a full description of functionality, including input and output parameters.

  1. To generate all DAGs based on a DAG PATTERN, use function pdag_to_all_dags(pdag). 
To indicate an undirected edge, use    pdag(a,b) = 1   pdag(b,a) =1  
To indicate a directed edge, use          pdag(a,b) = -1  pdag(b,a) =0


   % Use output of PC algorithm
   dag = mk_rnd_dag(4);   % create random DAG
   % Generate pdag through PC algorithm
   pdag = learn_struct_pdag_pc('dsep', length(dag), 3, dag)
   [n_dags,dag_list] = pdag_to_all_dags(pdag);

  1. To generate all Markov equivalent DAGs for a given DAG, use function Markov_equivalent_dags(dag).  
You need to have the BNT Structure Learning Package in place to run this function.  In newer versions of BNT that package is already included with BNT.

Example 1:  

  % Find all DAGs equivalent to DAG of Asia Network
  BN = mk_asia_bnet();
  dag = BN.dag;
  [n_dags, dag_list] = Markov_equivalent_dags(dag);
  n_dags         % Answer should be: 6
  dag_list{1}  % displays the first DAG, etc.

Example 2:  

  % Find all DAGs equivalent to random DAG
  dag = mk_rnd_dag(4);
  [n_dags, dag_list] = Markov_equivalent_dags(dag);

  1. Topological sorting of the output:
In all cases above dag_list is a list of DAGs, but that those are generally not topologically sorted.  Sorting each DAG topologically is very easy with the existing BNT functions, e.g. you can use something like this:

for i=1:length(dag_list)
   dag = dag_list{i};
   order = topological_sort(dag)
   sorted_dag = dag(order,order);
   % Now do something with it ...

Questions or comments? Found a bug?
PLEASE drop me an e-mail with any comments you may have!
Imme Ebert-Uphoff

Return to main page:

Page last updated: November 2011