ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 03 Aug 2015 22:49:43 +0200Multiprocessing Maximal Cliques Enumerationhttps://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/ 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?Wed, 15 Jul 2015 16:12:02 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/Answer by Nathann for <p>Hy,</p>
<p>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.</p>
<p>Is it implemented? or am I looking for a dream?</p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?answer=27387#post-id-27387If 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 Wed, 15 Jul 2015 17:02:06 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?answer=27387#post-id-27387Comment by AlexJ for <p>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.</p>
<p>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.</p>
<p>Nathann </p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=27388#post-id-27388Thanks, 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/pBitMCE.pdfWed, 15 Jul 2015 21:10:35 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=27388#post-id-27388Comment by Nathann for <p>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.</p>
<p>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.</p>
<p>Nathann </p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=27471#post-id-27471If 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/thematic_tutorials/cython_interface.html#calling-code-from-a-compiled-libraryThu, 16 Jul 2015 10:58:05 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=27471#post-id-27471Comment by AlexJ for <p>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.</p>
<p>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.</p>
<p>Nathann </p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=27472#post-id-27472I have multiple graphs, but often only one per time. I will take a look to implement pbitMCE. ThksThu, 16 Jul 2015 12:46:57 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=27472#post-id-27472Answer by AlexJ for <p>Hy,</p>
<p>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.</p>
<p>Is it implemented? or am I looking for a dream?</p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?answer=28748#post-id-28748Hy, 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?Mon, 03 Aug 2015 14:32:37 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?answer=28748#post-id-28748Answer by tmonteil for <p>Hy,</p>
<p>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.</p>
<p>Is it implemented? or am I looking for a dream?</p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?answer=28749#post-id-28749The 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.
Mon, 03 Aug 2015 15:51:56 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?answer=28749#post-id-28749Comment by AlexJ for <p>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.</p>
https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=28752#post-id-28752In 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!Mon, 03 Aug 2015 22:49:43 +0200https://ask.sagemath.org/question/27386/multiprocessing-maximal-cliques-enumeration/?comment=28752#post-id-28752