Triangulation of an undirected graph

This function will triangulate an undirected graph by adding fill-ins.

triangulate(object, ...)

# Default S3 method
triangulate(object, nLevels = NULL, result = NULL, check = TRUE, ...)

triang_mcwh(object, ...)

triang_elo(object, ...)

triang(object, ...)

# Default S3 method
triang(object, control = list(), ...)

# Default S3 method
triang_mcwh(object, nLevels = NULL, result = NULL, check = TRUE, ...)

# Default S3 method
triang_elo(object, order = NULL, result = NULL, check = TRUE, ...)

triangulateMAT(amat, nLevels = rep(2, ncol(amat)), ...)

triang_mcwhMAT_(amat, nLevels = rep(2, ncol(amat)), ...)

triang_eloMAT_(amat, order)

triang_eloMAT(amat, order = NULL)

Arguments

object

An undirected graph represented either as a graphNEL object, an igraph, a (dense) matrix, a (sparse) dgCMatrix.

...

Additional arguments, currently not used.

nLevels

The number of levels of the variables (nodes) when these are discrete. Used in determining the triangulation using a "minimum clique weight heuristic". See section 'details'.

result

The type (representation) of the result. Possible values are "graphNEL", "igraph", "matrix", "dgCMatrix". Default is the same as the type of object.

check

If TRUE (the default) it is checked whether the graph is triangulated before doing the triangulation; gives a speed up if FALSE

control

A list controlling the triangulation; see 'examples'.

order

Elimation order; a character vector or numeric vector.

amat

Adjacency matrix; a (dense) matrix, or a (sparse) dgCMatrix.

Value

A triangulated graph represented either as a graphNEL, a (dense) matrix or a (sparse) dgCMatrix.

Details

There are two type of functions: triang and triangulate

The workhorse is the triangulateMAT function.

The triangulation is made so as the total state space is kept low by applying a minimum clique weight heuristic: When a fill-in is necessary, the algorithm will search for an edge to add such that the complete set to be formed will have as small a state-space as possible. It is in this connection that the nLevels values are used.

Default (when nLevels=NULL) is to take nLevels=2 for all nodes. If nLevels is the same for all nodes then the heuristic aims at keeping the clique sizes small.

Note

Care should be taken when specifying nLevels for other representations than adjacency matrices: Since the triangulateMAT function is the workhorse, any other representation is transformed to an adjacency matrix and the order of values in nLevels most come in the order of the nodes in the adjacency matrix representation.

Currently there is no check for that the graph is undirected.

See also

ug, dag, mcs, mcsMAT, rip, ripMAT, moralize, moralizeMAT

Author

Søren Højsgaard, sorenh@math.aau.dk

Examples

## graphNEL
uG1 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a)
uG2 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a, result="matrix")
uG3 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a, result="dgCMatrix")

## Default triangulation: minimum clique weight heuristic
# (default is that each node is given the same weight):

tuG1 <- triang(uG1)
## Same as
triang_mcwh(uG1)
#> IGRAPH a3ffae8 UN-- 6 9 -- 
#> + attr: name (v/c), label (v/c)
#> + edges from a3ffae8 (vertex names):
#> [1] a--b a--f b--c b--f c--d c--f d--e d--f e--f

## Alternative: Triangulation from a desired elimination order
# (default is that the order is order of the nodes in the graph):

triang(uG1, control=list(method="elo"))
#> IGRAPH f9a0be2 UN-- 6 9 -- 
#> + attr: name (v/c), label (v/c)
#> + edges from f9a0be2 (vertex names):
#> [1] a--b a--f b--c b--f c--d c--f d--e d--f e--f
## Same as:
triang_elo(uG1)
#> IGRAPH 17d9c28 UN-- 6 9 -- 
#> + attr: name (v/c), label (v/c)
#> + edges from 17d9c28 (vertex names):
#> [1] a--b a--f b--c b--f c--d c--f d--e d--f e--f

## More control: Define the number of levels for each node:
tuG1 <- triang(uG1, control=list(method="mcwh", nLevels=c(2, 3, 2, 6, 4, 9))) 
tuG1 <- triang_mcwh(uG1, nLevels=c(2, 3, 2, 6, 4, 9))

tuG1 <- triang(uG1, control=list(method="elo", order=c("a", "e", "f")))
tuG1 <- triang_elo(uG1, order=c("a", "e", "f"))

## graphNEL
uG1 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a)
tuG1 <- triangulate(uG1)

## adjacency matrix
uG2 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a, result="matrix")
tuG2 <- triangulate(uG2)

## adjacency matrix (sparse)
uG2 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a, result="dgCMatrix")
tuG2 <- triangulate(uG2)