#13917: IndependentSets class
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: ahmorales
Authors: Nathann Cohen | Merged in:
Dependencies: #14589 | Stopgaps:
---------------------------------+------------------------------------------
Changes (by ncohen):
* status: needs_work => needs_info
Comment:
Hellooooooooo !!
> 0) Nobody would access the documentation in `__iter__` or
`__contains__`. I modified the documentation accordingly.
Oh. Right.
> 1) you should move `bitset_are_disjoint` to `sage.misc.bitset` as
somebody else may want to use it.
Hmmmm... I did not move it there for the function does not take bitsets as
input, but `unsigned long *` pointers... So I felt that it did not belong
there. If you are convinced that it should be there, no problem and I will
move it. I really had no idea.
> 2) your example to iterate over the independent set of given cardinality
is nice to learn Python but not to learn a good algorithm... If I want the
independent sets of cardinality 1 of a grid graph 12x12 it will take an
hour just to obtain my 144 independent sets.
Hmmm.. `-_-`
Right.
Do you want me to add options to list independent sets with a special
filter according to the number of vertices ?
> 3)
> {{{
> sage: G = graphs.CubeGraph(5)
> sage: I = IndependentSets(G)
> sage: [0,1,2,3] in I
> BOOOOOOOOOOOOOOOOOOOOOOOOOOOOM!!!
> }}}
>
> 4)
> {{{
> sage: IndependentSets(graphs.EmptyGraph())
> REBOOOOOOOOOOOOOOOOOOOOOOOOOOM!!
> }}}
Oh. I saw your `ProgrammerError` in the patch, but there is no segfault on
my side. When I run your commands, here is what I get :
{{{
sage: from sage.graphs.independent_sets import IndependentSets
sage: from sage.graphs.independent_sets
sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.CubeGraph(5)
sage: I = IndependentSets(G)
sage: [0,1,2,3] in I
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
<ipython-input-9-a8f48211b650> in <module>()
----> 1 [Integer(0),Integer(1),Integer(2),Integer(3)] in I
/home/ncohen/.Sage/local/lib/python2.7/site-
packages/sage/graphs/independent_sets.so in
sage.graphs.independent_sets.IndependentSets.__contains__
(build/cythonized/sage/graphs/independent_sets.c:5633)()
ValueError: An element of the set being tested does not belong to
}}}
Admittedly the error message has to be fixed, but no segfault. `O_o`
The empty graph produces a segfault allright. But of course the empty
graph is not really a graph `:-P`
Tell me what you think, and I will write an additional patch. And thank
you for your review !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:13>
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.
