#5793: [with patch, needs review] New algorithm for Max Clique in Graph class
using Cython
---------------------------+------------------------------------------------
Reporter: ncohen | Owner: rlm
Type: enhancement | Status: reopened
Priority: minor | Milestone: sage-4.1.1
Component: graph theory | Resolution:
Keywords: | Reviewer: Robert Miller
Author: Nathann Cohen | Merged:
---------------------------+------------------------------------------------
Comment(by ncohen):
I do not really know how to read patch files, but it seems to me you
replaced :
m = max([len(c) for c in G.cliques()])
by
m = max([len(c) for c in G.cliques_maximum()])
If right, I have two remarks :
- The syntax of max([len(c) for c in G.cliques()]) makes me think that
G.cliques() was meant to return the list of the maximAL cliques, and m is
then meant to be the clique number of G. The expression max([len(c) for c
in G.cliques_maximum()]) is syntaxically correct, thought as
cliques_maximum returns only the maxiMUM cliques we may as well return the
length of the first one as they all have the same size.
- In the end, and if I make no mistake, why about just setting
m=G.clique_number() ?
I expect it to be way faster than an enumeration of all the cliques ! ;-)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5793#comment:36>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
