#13917: IndependentSets class
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
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: | Stopgaps:
---------------------------------+------------------------------------------
Comment (by vdelecroix):
Replying to [comment:7 ncohen]:
Hey!
> > (it should inherit from `Parent` :P)
>
> Over my dead body.
>
(-: you should love your parents :-)
> > and a Cython iterator `IndependentSetIterator`. What do you think?
>
> I will not create an empty class if I can avoid it.
And what about
{{{
sage: from sage.graphs.independent_sets import IndependentSets
sage: I = IndependentSets(g,complement=True, maximal = True)
sage: I.next()
[0, 1, 2, 9, 19, 35, 40, 43, 47]
sage: I.cardinality()
4457
sage: I.next()
Traceback (most recent call last):
...
StopIteration:
}}}
Your class is in between:
- an iterator
- an object that modelises the set of independent sets (the methods
`cardinality` and `__contains__`)
Doing both purposes at the same time implies many unsatisfactory
behaviors. What I suggest is an iterator that iterates and a class that
answers to `__contains__` and `cardinality`. But this is not satisfactory
either because you still have to hack the iterator to get the cardinality.
It might be your choice to have a multiple purposes class. If so, specify
it in the documentation as : "you can either use the class to iterate
(though only once) or compute the cardinality, but do not think that you
can do both in a clean way".
> > 2) Could you provide a method to graph (independent_set_iterator
or/and independent_sets)?
>
> Actually I avoided it on purpose. I felt like this thing was not
interesting for everybody, and that it should belong to a module one would
load when needed, rather than add a new function to Graph.... What do you
think ? It's not like one wants to enumerate independent sets every other
day.
I agree!
> > 3) The flag count_only allows to count the number of independent set
in only one call to `__next__` (if you do replace "return []" by "if not
self.count_only: return []"). Your solution is a bit hackish and moreover
the "for i in self: pass" needs to catch the `StopIteration`.
>
> I will rewrite this part using $14589 as a dependency. It's a bit stupid
to deal with <64 vertices graphs only.
>
> > 1) With the current implementation it would be easy to provide the
number of independent set of each cardinality and to iterate through the
set of independent set of given cardinality.
>
> And it already is :
> {{{
> n_sets = [0]*g.order()
> for s in IndependentSets(g):
> n_sets[len(s)] += 1
> }}}
> What do you want ? Ugly "if" everywhere in the main loop to filter this
before returning them ?...
No. What I meant is to consider a more general attribute `.count` of type
`int[64]` which contains the number of independent set of each
cardinality. But your solution is satisfactory and you can keep the
implementation as it is. Could you add your clever solution to the
documentation?
> > 1) The complement of an independent set is a dominating set, right
(not a clique) ? If so, please change the documentation accordingly.
>
> The complement of an independent set is a vertex cover (and very often a
dominating set too, unless the graph has isolated vertices), but an
independent set of the <complement of the graph> is a clique. Was that the
problem ?
My mistake.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:8>
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.
