Ask Your Question

Multiprocessing Maximal Cliques Enumeration

asked 2015-07-15 09:12:02 -0600

AlexJ gravatar image

updated 2015-08-11 11:48:10 -0600

FrédéricC gravatar image


Is it a multiproccesor way to obtain a Maximal Cliques Enumeration (MCE) ? I test maximal_cliques() (networkX and native) and maximum_cliques() but all of them use a one-cored algorythme too solve the Graph MCE.

Is it implemented? or am I looking for a dream?

edit retag flag offensive close merge delete

3 answers

Sort by » oldest newest most voted

answered 2015-07-15 10:02:06 -0600

Nathann gravatar image

If networkx's implementation did not change since last I read it, then yes both are mono-core indeed, and those two are the only ones available in Sage.

What is your reason for wanting a mutithreaded version? Do you have one big graph in which you want to know all cliques? Or do you have many graphs in which you want to compute all cliques? In the latter case, you can much more easily parallelize the computations by running the same mono-threaded implementation on several instances at once.


edit flag offensive delete link more


Thanks, sadly it's the first problem! I want solve some massive graphs (minimum 300 nodes, no maximum for the moment)

For exemple, I see the pbitMCE algorithme, is it a way to implement it sage?

AlexJ gravatar imageAlexJ ( 2015-07-15 14:10:35 -0600 )edit

If you say that you have "some massive graphs", then to me your problem is of the second kind. And it would be much easier for you to parallelize it by solving several graphs at once. As per your pbitMCE algorithm, there are many ways to implement it in Sage, be it directly in Python code or in anything that can be compiled to a C library. You can then call it from Sage with

Nathann gravatar imageNathann ( 2015-07-16 03:58:05 -0600 )edit

I have multiple graphs, but often only one per time. I will take a look to implement pbitMCE. Thks

AlexJ gravatar imageAlexJ ( 2015-07-16 05:46:57 -0600 )edit

answered 2015-08-03 08:51:56 -0600

tmonteil gravatar image

The authors of the paper about pbitMCE claim they implemented their algorithm. However i could not find the source code on their webpage. I may be worth sending them an e-mail to ask for it and try to interface it with Sage.

edit flag offensive delete link more


In the paper their is only a Algorithmic process. Like you can see my English is not perfect, but I can test send a mail to the authors. Perhaps it will be a new implement to Sagemath!

AlexJ gravatar imageAlexJ ( 2015-08-03 15:49:43 -0600 )edit

answered 2015-08-03 07:32:37 -0600

AlexJ gravatar image

Hy, I've test several options:

Implement the pbitMCE algorithme : FAILED (I'm not enought skilled...)

Subdivise the primary graph in as many ego_graph as nodes (without previous nodes to prevent duplicate cliques), and solve MCE for each one simultanatly ; WORKS but isn't a good parallel way (some subgraph have many cliques and some none, so firts calls use all cores and lasts use only two or one.

As the second way : Subdivise the primary graph in as many ego_graph as nodes, test if they can contain a max_clique ; subdivise good one in as many ego_graph as nodes they contain, test if they can contain a max_clique ; subdivise each good one in as many ego_graph as nodes, test if they can contain a max_clique ; and finally solve MCE for each "good case"; WORKS in theory but i've issues... I think the node ordering is not the same each time i solve ego_graph, result : I've some duplicates cases and some accendently erased... so it's a FAIL...

So I'm still looking for a good way to enumarate max clique on multiple cores... Someone is skilled enought for the first way?

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools



Asked: 2015-07-15 09:12:02 -0600

Seen: 597 times

Last updated: Aug 03 '15