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.algor... 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 On Wed, Oct 26, 2016 at 6:42 PM, Reckoner <reckoner@gmail.com> wrote:
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! _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
-- Snehal Madhukar Shekatkar Pune India
How do you know if the clique is maximal ( not contained in a larger clique)? On Wed, Oct 26, 2016 at 8:13 AM, Snehal Shekatkar <snehalshekatkar@gmail.com> wrote:
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
On Wed, Oct 26, 2016 at 6:42 PM, Reckoner <reckoner@gmail.com> wrote:
Hi,
Are there any maximal clique-finding algorithms implemented in graph tool?
For example,
https://networkx.readthedocs.io/en/stable/reference/generated/networkx.algor...
Thanks! _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
--
Snehal Madhukar Shekatkar Pune India
_______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
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 On Thu, Oct 27, 2016 at 7:53 PM, Reckoner <reckoner@gmail.com> wrote:
How do you know if the clique is maximal ( not contained in a larger clique)?
On Wed, Oct 26, 2016 at 8:13 AM, Snehal Shekatkar <snehalshekatkar@gmail.com> wrote:
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
On Wed, Oct 26, 2016 at 6:42 PM, Reckoner <reckoner@gmail.com> wrote:
Hi,
Are there any maximal clique-finding algorithms implemented in graph
tool?
For example,
generated/networkx.algorithms.clique.find_cliques.html
Thanks! _______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
--
Snehal Madhukar Shekatkar Pune India
_______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
_______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
-- Snehal Madhukar Shekatkar Pune India
On 26.10.2016 14:12, Reckoner wrote:
Are there any maximal clique-finding algorithms implemented in graph tool?
For example,
https://networkx.readthedocs.io/en/stable/reference/generated/networkx.algor...
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
That would really be great. However, is there something wrong in using gt.motifs that I suggested in the previous email? Regards Snehal On Thu, Oct 27, 2016 at 8:40 PM, Tiago de Paula Peixoto <tiago@skewed.de> wrote:
On 26.10.2016 14:12, Reckoner wrote:
Are there any maximal clique-finding algorithms implemented in graph
tool?
For example,
generated/networkx.algorithms.clique.find_cliques.html
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
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
-- Snehal Madhukar Shekatkar Pune India
On 27.10.2016 16:30, Snehal Shekatkar wrote:
That would really be great. However, is there something wrong in using gt.motifs that I suggested in the previous email?
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. -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
Reckoner -
Snehal Shekatkar -
Tiago de Paula Peixoto