#13917: IndependentSets class
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: | Work issues: design, documentation
Report Upstream: N/A | Reviewers: ahmorales
Authors: Nathann Cohen | Merged in:
Dependencies: #14589 | Stopgaps:
---------------------------------+------------------------------------------
Changes (by ncohen):
* status: needs_work => needs_review
* dependencies: => #14589
Comment:
Newwwwwwww patch !!!!
* It now deals with graphs of arbitrary size (using the binary matrices
from #14589)
* I spent quite some time complaining to myself (and to Florent) about
creating an empty `IndependentSets` class which would call an
`IndependentSetsIterator` class. He also agreed with you Vincent, and even
though I did not like this problem with double loops either, I still
refused to write an empty class.
Because I hate empty classes.
Turns out that there is a nice way out, that I stupidly did not notice :
instead of writing a `.next()` method, I moved the code to `.__iter__()`,
and replaced the `return` by `yield`. And many global variables are now
local to `.__iter__()`, and everything goes well under the sun `:-P`
{{{
sage: g = graphs.PetersenGraph()
sage: from sage.graphs.independent_sets import IndependentSets
sage: IS = IndependentSets(g)
sage: IS2 = [(x,y) for x in IS for y in IS]
sage: len(IS2)
5776
sage: IS.cardinality()**2
5776
}}}
* I added a comment about the difference in speed between this
implementation and NetworkX
* Annnnnnd I added some links toward Wikipedia.
Tell me if you like it `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:11>
Sage <http://www.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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
