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.

- Markov_equivalent_dags.m
-- Finds all Markov equivalent DAGs for a given DAG. This builds
on pdag_to_all_dags.m, but also uses
function dag_to_cpdag of the Structure
Learning Package (bnt-slp), so
you'll need that to run the function.

- pdag_unsigned_to_signed.m
-- Auxiliary function to convert pdag from one notation to another.

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

EXAMPLES:

- 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

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

% 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

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

- 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

Questions or comments? Found a bug?

PLEASE drop me an e-mail with any comments you may have!

Imme Ebert-Uphoff