MaximalCliquesListing

Listing all the maximal cliques of a graph is an old, widely studied problem and a lot of algorithms have been proposed so far. One of the fastest algorithms is the one of Bron-Kerbosh. Its implementation is freely available in the igraph C library, starting from version 0.6.

Is there something ready to list maximal cliques?

Yes. We created a simple c program which uses the Bron-Kerbosh algorithm implementation available in igraph. Be sure to have igraph-0.6 or above installed, otherwise you can download it from here. The sources are available in the file extras/maximal_cliques.c. To compile it, cd to the directory where you downloaded the sources of COS, then cd to the extras directory and run make. This will create the executable maximal_cliques in the same folder. The file with extension .mcliques that maximal_cliques delivers as output can directly be used as input for COS (see its [UserGuide]).

Usage

./maximal_cliques <input_edgelist_file>

Where:

• <input_edgeslist_file> is a generic symbolic unweighted edgelist file. It is a simple text file with one edge per line. An edge is defined by two symbolic vertex names separated by whitespace. The symbolic vertex names themselves cannot contain whitespace.

Output

The first output file, with extension .mcliques, lists the extracted maximal cliques, one for each row. Each maximal clique is expressed as a whitespace-separated list of its nodes and ends with a virtual node -1. Prior to be output, each node is converted in a positive integer ranging from 0 to (N-1), where N is the number of nodes in the graph. The association between symbolic node names and integers is output in the second file. The second output file, with extension .map, lists for each node its associated integer.

An Example

An example edgelist file of a fully-connected graph with 4 nodes (with symbolic vertex names node1, node2, N3 and myFourthNode) is the following:

node1 node2
node1 N3
node1 myFourthNode
node2 N3
node2 myFourthNode
N3 myFourthNode

By providing as input the previous edgelist file, the program produces the
following two files.

File .map:

node1 0
node2 1
N3 2
myFourthNode 3

File .mcliques:

0 1 2 3 -1