Create RIP ordering of the cliques of an undirected graph; create junction tree.

A RIP (running intersection property) ordering of the cliques is also called a perfect ordering. If the graph is not chordal, then no such ordering exists.

rip(object, ...)

# Default S3 method
rip(object, root = NULL, nLevels = NULL, ...)

ripMAT(amat, root = NULL, nLevels = rep(2, ncol(amat)))

junction_tree(object, ...)

# Default S3 method
junction_tree(object, nLevels = NULL, ...)

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

jTree(object, ...)

Arguments

object

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

...

Additional arguments; currently not used

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.

nLevels

Typically, 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'.

amat

Adjacency matrix

Value

rip returns a list (an object of class ripOrder. A print method exists for such objects.)

Details

The RIP ordering of the cliques of a decomposable (i.e. chordal) graph is obtained by first ordering the variables linearly with maximum cardinality search (by mcs). The root argument is transfered to mcs as a way of controlling which clique will be the first in the RIP ordering. The junction_tree() (and junction_tree()) (for "junction tree") is just a wrapper for a call of triangulate() followed by a call of rip().

Note

The workhorse is the ripMAT() function. The nLevels argument to the rip functions has no meaning.

Synonymous functions

For backward compatibility with downstream packages we have the following synonymous functions:

  • jTree = junction_tree (Used in rags2ridges)

  • junctionTree = junction_tree

See also

mcs, triangulate, moralize, ug, dag

Author

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

Examples


## graphNEL
uG <- ug(~me:ve + me:al + ve:al + al:an + al:st + an:st)
mcs(uG)
#> [1] "me" "ve" "al" "an" "st"
rip(uG)
#> cliques
#>   1 : me ve al 
#>   2 : al an st 
#> separators
#>   1 :  
#>   2 : al 
#> parents
#>   1 : 0 
#>   2 : 1 
junction_tree(uG)
#> cliques
#>   1 : me ve al 
#>   2 : al an st 
#> separators
#>   1 :  
#>   2 : al 
#> parents
#>   1 : 0 
#>   2 : 1 

## Adjacency matrix
uG <- ug(~me:ve:al + al:an:st, result="matrix")
mcs(uG)
#> [1] "me" "ve" "al" "an" "st"
rip(uG)
#> cliques
#>   1 : me ve al 
#>   2 : al an st 
#> separators
#>   1 :  
#>   2 : al 
#> parents
#>   1 : 0 
#>   2 : 1 
junction_tree(uG)
#> cliques
#>   1 : me ve al 
#>   2 : al an st 
#> separators
#>   1 :  
#>   2 : al 
#> parents
#>   1 : 0 
#>   2 : 1 

## Sparse adjacency matrix
uG <- ug(c("me", "ve", "al"), c("al", "an", "st"), result="dgCMatrix")
mcs(uG)
#> [1] "me" "ve" "al" "an" "st"
rip(uG)
#> cliques
#>   1 : me ve al 
#>   2 : al an st 
#> separators
#>   1 :  
#>   2 : al 
#> parents
#>   1 : 0 
#>   2 : 1 
junction_tree(uG)
#> cliques
#>   1 : me ve al 
#>   2 : al an st 
#> separators
#>   1 :  
#>   2 : al 
#> parents
#>   1 : 0 
#>   2 : 1 

## Non--decomposable graph
uG <- ug(~1:2 + 2:3 + 3:4 + 4:5 + 5:1)
mcs(uG)
#> character(0)
rip(uG)
#> NULL
junction_tree(uG)
#> cliques
#>   1 : 1 2 5 
#>   2 : 2 3 5 
#>   3 : 3 4 5 
#> separators
#>   1 :  
#>   2 : 2 5 
#>   3 : 3 5 
#> parents
#>   1 : 0 
#>   2 : 1 
#>   3 : 2