# cliques

##### The functions find cliques, ie. complete subgraphs in a graph

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.

- Keywords
- graphs

##### Usage

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

##### Arguments

- 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.

##### Details

`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.

##### Value

`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.

##### References

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

##### See Also

##### Examples

```
# 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)
# }
```

*Documentation reproduced from package igraph, version 1.0.1, License: GPL (>= 2)*