gRbase: graph-min-triangulate – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

graph-min-triangulate

Minimal triangulation of an undirected graph

Description

An undirected graph uG is triangulated (or chordal) if it has no cycles of length >= 4 without a chord which is equivalent to that the vertices can be given a perfect ordering. Any undirected graph can be triangulated by adding edges to the graph, so called fill-ins which gives the graph TuG. A triangulation TuG is minimal if no fill-ins can be removed without breaking the property that TuG is triangulated.

Usage

minimal_triang(
  object,
  tobject = triangulate(object),
  result = NULL,
  details = 0
)

minimal_triangMAT(amat, tamat = triangulateMAT(amat), details = 0)

Arguments

`object`	An undirected graph represented either as a `graphNEL` object, a (dense) `matrix`, a (sparse) `dgCMatrix`.
`tobject`	Any triangulation of `object`; must be of the same representation.
`result`	The type (representation) of the result. Possible values are `"graphNEL"`, `"matrix"`, `"dgCMatrix"`. Default is the same as the type of `object`.
`details`	The amount of details to be printed.
`amat`	The undirected graph which is to be triangulated; a symmetric adjacency matrix.
`tamat`	Any triangulation of `object`; a symmetric adjacency matrix.

Details

For a given triangulation tobject it may be so that some of the fill-ins are superflous in the sense that they can be removed from tobject without breaking the property that tobject is triangulated. The graph obtained by doing so is a minimal triangulation.

Notice: A related concept is the minimum triangulation, which is the the graph with the smallest number of fill-ins. The minimum triangulation is unique. Finding the minimum triangulation is NP-hard.

Value

minimal_triang() returns a graphNEL object while minimal_triangMAT() returns an adjacency matrix.

Author(s)

Clive Bowsher <C.Bowsher@statslab.cam.ac.uk> with modifications by Søren Højsgaard, sorenh@math.aau.dk

References

Kristian G. Olesen and Anders L. Madsen (2002): Maximal Prime Subgraph Decomposition of Bayesian Networks. IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, PART B: CYBERNETICS, VOL. 32, NO. 1, FEBRUARY 2002

Examples

## A graphNEL object
g1 <- ug(~a:b + b:c + c:d + d:e + e:f + a:f + b:e)
x <- minimal_triang(g1)

## g2 is a triangulation of g1 but it is not minimal
g2 <- ug(~a:b:e:f + b:c:d:e)
x <- minimal_triang(g1, tobject=g2)

## An adjacency matrix
g1m <- ug(~a:b + b:c + c:d + d:e + e:f + a:f + b:e, result="matrix")
x <- minimal_triangMAT(g1m)

gRbase

A Package for Graphical Modelling in R

v1.8-6.7

GPL (>= 2)

Authors

Søren Højsgaard <sorenh@math.aau.dk>

Initial release