clique-finding algorithm

Hi,

Are there any maximal clique-finding algorithms implemented in graph tool?

For example,

https://networkx.readthedocs.io/en/stable/reference/generated/networkx.algorithms.clique.find_cliques.html

Thanks!

I don't think any such function exists. But if you can use gt.motifs to do
this. For example, the following code gives simple implementation for
finding the size of the maximum clique:

G = gt.price_network(100, 3, directed = False)

tot = 1

for i in range(1, G.num_vertices() + 1):
    g = gt.complete_graph(i)
    tot = gt.motifs(G, k = i, motif_list = [g, ])[1][0]
    print(i, tot)
    if tot == 0:
        break

Regards
Snehal

attachment.html (1.98 KB)

How do you know if the clique is maximal ( not contained in a larger clique)?

Though the snippet that I provided is not the best possible that one could
write, it breaks the loop if the bigger clique than the last one is not
found (if tot ==0; break). Perhaps you should use `while` and do the same
thing.

Regards
Snehal

attachment.html (3.43 KB)

No, this is not yet implemented. Please open an issue in the website with a
feature request, so I can keep track of it.

Best,
Tiago

That would really be great. However, is there something wrong in using
gt.motifs that I suggested in the previous email?

Regards
Snehal

attachment.html (1.78 KB)

As Reckoner pointed out, what you proposed finds cliques, not maximal
cliques. At the end of your loop, you find the size of the largest clique,
but you don't know if the smaller ones you found in the meantime were maximal.

Furthermore, it is much slower than the proper algorithms for finding
maximal cliques.