These functions find all, the largest or all the maximal cliques in an undirected graph. The size of the largest clique can also be calculated.

`cliques(graph, min = NULL, max = NULL)`max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)

graph

The input graph, directed graphs will be considered as undirected ones, multiple edges and loops are ignored.

min

Numeric constant, lower limit on the size of the cliques to find.
`NULL`

means no limit, ie. it is the same as 0.

max

Numeric constant, upper limit on the size of the cliques to find.
`NULL`

means no limit.

subset

If not `NULL`

, then it must be a vector of vertex ids,
numeric or symbolic if the graph is named. The algorithm is run from these
vertices only, so only a subset of all maximal cliques is returned. See the
Eppstein paper for details. This argument makes it possible to easily
parallelize the finding of maximal cliques.

file

If not `NULL`

, then it must be a file name, i.e. a
character scalar. The output of the algorithm is written to this file. (If
it exists, then it will be overwritten.) Each clique will be a separate line
in the file, given with the numeric ids of its vertices, separated by
whitespace.

`cliques`

, `largest_cliques`

and `clique_num`

return a list containing numeric vectors of vertex ids. Each list element is
a clique.

`max_cliques`

returns `NULL`

, invisibly, if its `file`

argument is not `NULL`

. The output is written to the specified file in
this case.

`clique_num`

and `count_max_cliques`

return an integer
scalar.

`cliques`

find all complete subgraphs in the input graph, obeying the
size limitations given in the `min`

and `max`

arguments.

`largest_cliques`

finds all largest cliques in the input graph. A
clique is largest if there is no other clique including more vertices.

`max_cliques`

finds all maximal cliques in the input graph. A
clique in maximal if it cannot be extended to a larger clique. The largest
cliques are always maximal, but a maximal clique is not neccessarily the
largest.

`count_max_cliques`

counts the maximal cliques.

`clique_num`

calculates the size of the largest clique(s).

The current implementation of these functions searches for maximal
independent vertex sets (see `ivs`

) in the
complementer graph.

For maximal cliques the following algorithm is implemented: David Eppstein, Maarten Loffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time. http://arxiv.org/abs/1006.5440

```
# NOT RUN {
# this usually contains cliques of size six
g <- sample_gnp(100, 0.3)
clique_num(g)
cliques(g, min=6)
largest_cliques(g)
# To have a bit less maximal cliques, about 100-200 usually
g <- sample_gnp(100, 0.03)
max_cliques(g)
# }
```

Run the code above in your browser using DataLab