• Home Page
• Documentation
• Examples
• Research Notes
• Small Simulation Studies
• Bayesian Network Repository

• About the Author

info & code

data & R code

data & R code

Counting and enumerating graphs

Graphical enumeration deals with the enumeration of graphs with specific characteristics. bnlearn implements some enumeration results that are specific to directed acyclic graphs and that are relevant for studying Bayesian networks. To this end, it provides:

• count.graphs() (documented here), which returns the number of specific types of graphs.
• cextend.all() (documented here), which returns all DAGs beloging to an equivalence class.

Counting directed acyclic graphs

count.graphs() takes a string identifying what type of DAGs to count as its main argument, and returns a bigz arbitrary-precision integer from package gmp. Additonally, it takes type-specific arguments further specifying the DAGs' size and topology. Available options are:

• Counting all DAGs with a number of nodes specified by the nodes argument.

  > count.graphs(type = "all-dags", nodes = 5)
  

  Loading required namespace: gmp
  

  Big Integer ('bigz') :
  [1] 29281
  

• Counting all DAGs with a number of nodes specified by the nodes argument that have the same topological ordering.

  > count.graphs(type = "dags-given-ordering", nodes = 7)
  

  Big Integer ('bigz') :
  [1] 2097152
  

• Counting all DAGs with nodes nodes and a number of root nodes specified by the k argument.

  > count.graphs(type = "dags-with-k-roots", nodes = 6, k = 2)
  

  Big Integer ('bigz') :
  [1] 1384335
  

• Counting all DAGs with nodes nodes and r arcs.

  > count.graphs(type = "dags-with-k-roots", nodes = 6, k = 2)
  

  Big Integer ('bigz') :
  [1] 1384335
  

• Counting all DAGs in an equivalence class, specified as a bn object describing a CPDAG with the eqclass argument.

  > count.graphs(type = "dags-in-equivalence-class", eqclass = cpdag(random.graph(LETTERS[1:6])))
  

  Loading required namespace: igraph
  

  Big Integer ('bigz') :
  [1] 6
  

The argument nodes, when available, can be a vector of values. count.graphs() then returns one count for each number of nodes.

> count.graphs(type = "dags-with-k-roots", nodes = 2:10, k = 2)

Big Integer ('bigz') object of length 9:
[1] 1                   9                   198                
[4] 10710               1384335             416990763          
[7] 286992935964        444374705175516     1528973599758889005

Listing all score-equivalent directed acyclic graphs

cextend.all() takes a bn or bn.fit object encoding a CPDAG and returns a list of bn objects encoding all the DAGs that belong to the corresponding equivalence class. For instance, take the ALARM network:

> modelstring = paste0("[HIST|LVF][CVP|LVV][PCWP|LVV][HYP][LVV|HYP:LVF][LVF]",
+   "[STKV|HYP:LVF][ERLO][HRBP|ERLO:HR][HREK|ERCA:HR][ERCA][HRSA|ERCA:HR][ANES]",
+   "[APL][TPR|APL][ECO2|ACO2:VLNG][KINK][MINV|INT:VLNG][FIO2][PVS|FIO2:VALV]",
+   "[SAO2|PVS:SHNT][PAP|PMB][PMB][SHNT|INT:PMB][INT][PRSS|INT:KINK:VTUB][DISC]",
+   "[MVS][VMCH|MVS][VTUB|DISC:VMCH][VLNG|INT:KINK:VTUB][VALV|INT:VLNG]",
+   "[ACO2|VALV][CCHL|ACO2:ANES:SAO2:TPR][HR|CCHL][CO|HR:STKV][BP|CO:TPR]")
> eqclass = cpdag(model2network(modelstring))

The CPDAG for its equivalence class has four undirected arcs, highlighted in green below.

>   graphviz.plot(eqclass, highlight = list(arcs = undirected.arcs(eqclass),
+   col = "limegreen", lwd = 2))

Loading required namespace: Rgraphviz

Considering where those undirected arcs are located in the graphs, all 2⁴ = 16 combinations of their directions (highlighted in red) produce equivalent DAGs.

> all.equivalent.dags = cextend.all(eqclass)
> par(mfrow = c(2, 2))
> for (dag in all.equivalent.dags)
+   graphviz.plot(dag, highlight = list(arcs = reversible.arcs(eqclass), lwd = 2))