Generating Markov-Equivalent DAGs in BNT

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.
• pdag_to_all_dags.m -- This is the main function.  It finds all DAGs for a partially directed DAG.  The algorithm is based on Meek's algorithm [Meek, UAI 95] to find a single DAG given a PDAG (see file for a complete description of the algorithm).
• complete_pattern.m -- This function implements Rules 1-4 of [Meek, UAI 95] to complete the orientations of a partially oriented graph as far as possible.  This function is used by pdag_to_all_dags, but can also be used as a stand-alone.
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.

EXAMPLES:
1. To generate all DAGs based on a DAG PATTERN, use function pdag_to_all_dags(pdag).
Comments:
• You do NOT need the Structure Learning Package to run this function.
• pdag does NOT have to be complete, since the algorithm completes the input pattern as a first step.
• pdag must have the following format:
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

Example:

% 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);
n_dags

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 ...
end

Feedback:
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: www.DataOnStage.com

Page last updated: November 2011