Hi,

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

For example,

Thanks!

Hi,

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

For example,

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.