# 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 argum - 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 o

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

##### See Also

##### Examples

```
# 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.0, License: GPL (>= 2)*