#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 ncohen):
Yoooooooooooo !!
> 0) I found your patch useful!
Cool !
> 0') I thought that in your timing most of the time was lost in the
creation of the list and the for loop... but no: it is not much faster to
enumerate all independent set rather than counting them with the method
cardinality (I update the example in the description). So, I am as well
surprised by `Python/Cython`.
Yep `O_o`
> 1) I am not sure the following is what we want
Ok. So what you want is an empty class that does nothing, which calls
another class that does all the job ? It cannot be just an independent
iterator, for I also want to compute the number of cliques without having
to compute all the lists of elements at Python level.
> In other words an iterator is an iterator and nothing else.
Says the dogma.
> If you want to design the set of independent sets it should be an object
different from the iterator.
Says the dogma.
> It would be better to have a Python class `IndependentSets` desinged to
modelize the set of independent sets
And what on earth would it do that is not a feature of the iterator ?
> (it should inherit from `Parent` :P)
Over my dead body.
> and a Cython iterator `IndependentSetIterator`. What do you think?
I will not create an empty class if I can avoid it.
> 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.
> 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 ?...
> 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 ?
> 2) wikipedia links might be useful
:wikipedia:Independent_set_(graph_theory), :wikipedia:Dominating_set,
:wikipedia:Clique_graph
Right, right. I will add them to the next version of this patch.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:7>
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.
