Hy,
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?
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.
Nathann
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? http://www.cs.odu.edu/~ndasari/pBitMC...
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 http://doc.sagemath.org/html/en/thema...
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?
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.
Asked: 2015-07-15 16:12:02 +0200
Seen: 1,191 times
Last updated: Aug 03 '15
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
