MCS: Maximum cardinality search

In gRapHD: Efficient Selection of Undirected Graphical Models for High-Dimensional Datasets

Description

Returns a perfect ordering of the edges.

Usage

MCS(model=NULL,edges=NULL,v=0,p=NULL)

Arguments

model	gRapHD object.
edges	matrix with 2 columns, each row representing one edge, and each column one of the vertices in the edge.
v	initial vertex (0<=v<=p). If v=0, the algorithm starts from vertex 1.
p	number of vertices.

Details

Returns a perfect ordering of the vertices. For mixed graphs, the discrete vertices appear before the continuous vertices, in each connected component.

Value

Zero if the graph is not triangulated, or a vector with the number of each vertex in the perfect ordering.

Author(s)

Gabriel Coelho Goncalves de Abreu ([e-mail])

References

Tarjan, R.E., Yannakakis, M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput., Vol 13, 3:566-79.

Leimer, H. Triangulated graphs with marked vertices. Ann. Discr. Maths., Vol 41, 311-324.

Examples

set.seed(7,kind="Mersenne-Twister")
dataset <- matrix(rnorm(1000),nrow=100,ncol=10)
m <- minForest(dataset,stat="BIC")

MCS(edges=m@edges,v=1,p=10)

gRapHD documentation built on Feb. 9, 2018, 6:05 a.m.