Clique Number and Maximal Cliques on Undirected Graphs with Self-Loops

[Dimitris Diochnos]

Might be related to this bug: https://bugs.launchpad.net/igraph/+bug/1073800

- igraph version: 0.6

Summary
We load an undirected graph with self-loops. There is a very dense subgraph where there are many cliques (I do not know the exact number; I obtained this from a much larger dataset). Somehow, the self-loops trigger a bug. In the attached example I check one by one for the existence of all the edges among 12 nodes and all of them are part of the input (I have verified this by hand as well). However, the built-in functions for the size of the largest clique or the maximal cliques return different numbers when we include self-loops or not in the input. This is true both in C and in Python; I believe it is also true in R.

Example: Input Description
- 18 nodes, 133 edges, 8 self loops.
- Has a clique of size at least 12 among the nodes:
  [0, 3, 5, 6, 7, 9, 10, 11, 14, 15, 16, 17]
- I do not know how many maximal cliques there are.

Example: Attachment
One source file in Python and two different input files with lists of edges. One of the files with the lists of edges includes self-loops, the other one does not.

Example: Output
$ ./cliques.py edgesSmall.txt
IGRAPH U--- 18 133 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 11
-------------------------------------------------------
There are 12 maximal cliques
$ ./cliques.py edgesSmallNoLoops.txt
IGRAPH U--- 18 125 --
-------------------------------------------------------
Checked 66 pairs among 12 nodes and 66 are neighbors
-------------------------------------------------------
The size of the largest clique is 12
-------------------------------------------------------
There are 10 maximal cliques
$

[Tamás Nepusz (ntamas)]

Fixed in #3001 in 0.6-main and #3044 in trunk. You can check out the latest nightly from http://code.google.com/p/igraph and compile it yourself if you need the fix, or alternatively, you can patch src/cliques.c according to the diff in #3001 of 0.6-main. Contact me if you need help with re-building igraph.

[Tamás Nepusz (ntamas)]

Also, thanks for the detailed bug report and the example that made it super easy to reproduce the issue.

[Dimitris Diochnos (diochnos)]

Thank you for fixing this Tamás and for all your help!

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/123