RBGL (version 1.48.1)

maxClique: Find all the cliques in a graph

Description

Find all the cliques in a graph

Usage

maxClique(g, nodes=NULL, edgeMat=NULL)

Arguments

g

an instance of the graph class

nodes

vector of node names, to be supplied if g is not

edgeMat

2 x p matrix with indices of edges in nodes, one-based, only to be supplied if codeg is not

Value

maxClique

list of all cliques in g

Details

Notice the maximum clique problem is NP-complete, which means it cannot be solved by any known polynomial algorithm.

We implemented the algorithm by C. Bron and J. Kerbosch,

It is an error to supply both g and either of the other arguments.

If g is not supplied, no checking of the consistency of nodes and edgeMat is performed.

References

Finding all cliques of an undirected graph, by C. Bron and J. Kerbosch, Communication of ACM, Sept 1973, Vol 16, No. 9.

Examples

con1 <- file(system.file("XML/conn.gxl",package="RBGL"), open="r")
coex <- fromGXL(con1)
close(con1)

maxClique(coex)

con2 <- file(system.file("XML/hcs.gxl",package="RBGL"), open="r")
coex <- fromGXL(con2)
close(con2)

maxClique(coex)