GraphAlgo-mcs: Maximum cardinality search on undirected graph.

In gRbase: A package for graphical modelling in R

Description

Returns (if it exists) a perfect ordering of the vertices in an undirected graph.

Usage

mcs(object, root = NULL, index = FALSE)
## S3 method for class 'graphNEL'
mcs(object, root = NULL, index = FALSE)
## S3 method for class 'matrix'
mcs(object, root = NULL, index = FALSE)
mcsMAT(amat, vn = colnames(amat), root = NULL, index = FALSE) 

mcsmarked(object, discrete = NULL, index = FALSE)
## S3 method for class 'graphNEL'
mcsmarked(object, discrete = NULL, index = FALSE)
## S3 method for class 'matrix'
mcsmarked(object, discrete = NULL, index = FALSE)
mcsmarkedMAT(amat, vn = colnames(amat), discrete = NULL, index = FALSE) 

Arguments

object	An undirected graph represented either as a 'graphNEL', a 'matrix' or a sparse matrix (a 'dgCMatrix').
root	A vector of variables. The first variable in the perfect ordering will be the first variable on 'root'. The ordering of the variables given in 'root' will be followed as far as possible.
discrete	A vector indicating which of the nodes are discrete. See 'details' for more information.
index	If TRUE, then a permutation is returned
amat	Adjacency matrix
vn	Nodes in the graph given by adjacency matrix

Details

An undirected graph is decomposable iff there exists a perfect ordering of the vertices. The maximum cardinality search algorithm returns a perfect ordering of the vertices if it exists and hence this algorithm provides a check for decomposability. The mcs() functions finds such an ordering if it exists.

The notion of strong decomposability is used in connection with e.g. mixed interaction models where some vertices represent discrete variables and some represent continuous variables. Such graphs are said to be marked. The mcsmarked() function will return a perfect ordering iff the graph is strongly decomposable. As graphs do not know about whether vertices represent discrete or continuous variables, this information is supplied in the discrete argument.

Value

A vector with a linear ordering (obtained by maximum cardinality search) of the variables or character(0) if such an ordering can not be created.

Note

The workhorse is the mcsMAT function.

Author(s)

S<f8>ren H<f8>jsgaard, [e-mail]

See Also

moralize jTree rip ug, dag

Examples

uG <- ug(~me+ve,~me+al,~ve+al,~al+an,~al+st,~an+st)
mcs(uG)
mcsMAT(as.adjMAT(uG))
## Same as
uG <- ug(~me+ve,~me+al,~ve+al,~al+an,~al+st,~an+st,result="matrix")
mcsMAT(uG)

## Marked graphs
uG1 <- ug(~a:b+b:c+c:d)
uG2 <- ug(~a:b+a:d+c:d)
## Not strongly decomposable:
mcsmarked(uG1, discrete=c("a","d"))
## Strongly decomposable:
mcsmarked(uG2, discrete=c("a","d"))

gRbase documentation built on May 2, 2019, 4:51 p.m.