gRbase (version 1.8-3.4)

graph-cliques: Get cliques of an undirected graph

Description

Return a list of (maximal) cliques of an undirected graph.

Usage

getCliques(object)
# S3 method for graphNEL
getCliques(object)
# S3 method for default
getCliques(object)
maxCliqueMAT(amat)

Arguments

object

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

amat

An adjacency matrix.

Value

A list.

Details

In graph theory, a clique is often a complete subset of a graph. A maximal clique is a clique which can not be enlarged. In statistics (and that is the convention we follow here) a clique is usually understood to be a maximal clique.

Finding the cliques of a general graph is an NP complete problem. Finding the cliques of triangualted graph is linear in the number of cliques.

The workhorse is the maxCliqueMAT function which calls the maxClique function in the RBGL package.

See Also

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

Examples

# NOT RUN {
## graphNEL
uG1 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a)
getCliques(uG1)

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

## adjacency matrix (sparse)
uG3 <- ug(~a:b + b:c + c:d + d:e + e:f + f:a, result="Matrix")
getCliques(uG3)


# }