Maximal Cliques

Finds all the maximal complete sub-graphs (maximal cliques) in a graph

Description

The graph passed must be an upper rectangular square matrix. Each row of a matrix denotes the presence of an edge with 1, and an absence of it with 0. The row and col no. of an edge denotes the connecting nodes. Given this matrix, this function finds all the maximal complete sub-graph (a set of nodes amongst all the nodes which form a complete sub-graph i.e. every node connects to every other) also known as cliques. A maximal graph is returned since every complete sub-graph will also have smaller complete sub-graphs inside itself. NOTE: this function would not return single node sub-graphs, although every isolated node, in concept, also forms a complete sub-graph.

The function returns all the sub-graphs in a cell-array, where each row denotes a new sub-graph

• Acknowledgements: This submission has inspired the following:; Bron-Kerbosch maximal clique finding algorithm
• MATLAB release: MATLAB 7.9 (2009b)

[Henry Wolkowicz]

I have only tested the file a few times. It works well, but there should be a warning that it slows down quickly, i.e. 40 nodes can already be too much. Of course, finding all the cliques is an NP-hard problem so that is not a surprise. But, ... a warning would help.

[Ahmad]

@Henry
Warning added and the no. of nodes can be set by WARNING_CONNECTING_NODES_LENGTH .... which defaults to 20.

I have done this since an NP-hard problem's actual computability would vary from machine to machine

[Yonit Marcus]