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.
cliques(graph, min = NULL, max = NULL)
max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)
- The input graph, directed graphs will be considered as undirected ones, multiple edges and loops are ignored.
- Numeric constant, lower limit on the size of the cliques to find.
NULLmeans no limit, ie. it is the same as 0.
- Numeric constant, upper limit on the size of the cliques to find.
NULLmeans no limit.
- 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
- 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
cliques find all complete subgraphs in the input graph, obeying the
size limitations given in the
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
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
clique_numreturn a list containing numeric vectors of vertex ids. Each list element is a clique.
NULL, invisibly, if its
fileargument is not
NULL. The output is written to the specified file in this case.
count_max_cliquesreturn an integer scalar.
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.
# 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)