isValidGraph function

Check for a DAG, CPDAG or a maximally oriented PDAG

Check whether the adjacency matrix amat matches the specified type.

isValidGraph(amat, type = c("pdag", "cpdag", "dag"), verbose = FALSE)

Arguments

• amat: adjacency matrix of type amat.cpdag (see amatType)
• type: string specifying the type of graph of the adjacency matrix amat. It can be a DAG (type="dag"), a CPDAG (type="cpdag") or a maximally oriented PDAG (type="pdag") from Meek (1995).
• verbose: If TRUE, detailed output on why the graph might not be valid is provided.

Details

For a given adjacency matrix amat and graph type, this function checks whether the two match.

For type = "dag" we require that amat does NOT contain directed cycles.

For type = "cpdag" we require that amat does NOT contain directed or partially directed cycles. We also require that the undirected part of the CPDAG (represented by amat) is made up of chordal components and that our graph is maximally oriented according to rules from Meek (1995).

For type = "pdag" we require that amat does NOT contain directed cycles. We also require that the PDAG is maximally oriented according to rules from Meek (1995). Additionally, we require that the adjacency matrix amat1 of the CPDAG corresponding to our PDAG (represented by amat), satisfies isValidGraph(amat = amat1,type = "cpdag") == TRUE and that there is no mismatch in the orientations implied by amat and amat1. We obtain amat1 by extracting the skeleton and v-structures from amat and then closing the orientation rules from Meek (1995).

Returns

TRUE, if the adjacency matrix amat is of the type specified and FALSE, otherwise.

References

C. Meek (1995). Causal inference and causal explanation with background knowledge, In Proceedings of UAI 1995, 403-410.

Author(s)

Emilija Perkovic and Markus Kalisch

Examples

## a -> b -> c
amat <- matrix(c(0,1,0, 0,0,1, 0,0,0), 3,3)
colnames(amat) <- rownames(amat) <- letters[1:3]
## graph::plot(as(t(amat), "graphNEL"))             
isValidGraph(amat = amat, type = "dag") ## is a valid DAG
isValidGraph(amat = amat, type = "cpdag") ## not a valid CPDAG 
isValidGraph(amat = amat, type = "pdag") ## is a valid PDAG

## a -- b -- c
amat <- matrix(c(0,1,0, 1,0,1, 0,1,0), 3,3)
colnames(amat) <- rownames(amat) <- letters[1:3]
## plot(as(t(amat), "graphNEL"))             
isValidGraph(amat = amat, type = "dag") ## not a valid DAG
isValidGraph(amat = amat, type = "cpdag") ## is a valid CPDAG
isValidGraph(amat = amat, type = "pdag") ## is a valid PDAG

## a -- b -- c -- d -- a
amat <- matrix(c(0,1,0,1, 1,0,1,0, 0,1,0,1, 1,0,1,0), 4,4)
colnames(amat) <- rownames(amat) <- letters[1:4]
## plot(as(t(amat), "graphNEL"))             
isValidGraph(amat = amat, type = "dag") ## not a valid DAG
isValidGraph(amat = amat, type = "cpdag") ## not a valid CPDAG
isValidGraph(amat = amat, type = "pdag") ## not a valid PDAG