#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:
---------------------------------+------------------------------------------
Changes (by vdelecroix):
* status: needs_review => needs_work
* work_issues: => design, documentation
Old description:
> I'm rather disappointed by this patch. Or I'm pleasantly surprised by
> Python, I don't know. I expected a much better speedup.
>
> {{{
> sage: g = graphs.RandomGNP(50,.7)
> sage: import networkx
> sage: gn = g.networkx_graph()
> sage: %timeit list(networkx.find_cliques(gn))
> 5 loops, best of 3: 79.8 ms per loop
> sage: %timeit list(IndependentSets(g,complement=True, maximal = True))
> 25 loops, best of 3: 26.4 ms per loop
> }}}
>
> Either way, this patch implements a `sage.graphs.independent_set` module
> that can list/count (possibly maximal) independent sets in a small graph
> (<64 vertices).
>
> And count them.
>
> Anyway, don't hesitate to tell me that this patch is useless if you feel
> like it. I'm not *that* convinced either.
>
> Nathann
New description:
I'm rather disappointed by this patch. Or I'm pleasantly surprised by
Python, I don't know. I expected a much better speedup.
{{{
sage: g = graphs.RandomGNP(50,.7)
sage: import networkx
sage: gn = g.networkx_graph()
sage: %timeit list(networkx.find_cliques(gn))
10 loops, best of 3: 59.9 ms per loop
sage: from sage.graphs.independent_sets import IndependentSets
sage: %timeit list(IndependentSets(g,complement=True, maximal = True))
100 loops, best of 3: 19.7 ms per loop
sage: %timeit IndependentSets(g,complement=True, maximal =
True).cardinality()
100 loops, best of 3: 17.6 ms per loop
}}}
Either way, this patch implements a `sage.graphs.independent_set` module
that can list/count (possibly maximal) independent sets in a small graph
(<64 vertices).
And count them.
Anyway, don't hesitate to tell me that this patch is useless if you feel
like it. I'm not *that* convinced either.
Nathann
--
Comment:
0) I found your patch useful!
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`.
'''Todo'''
1) I am not sure the following is what we want
{{{
sage: I = independent_sets.IndependentSets(graphs.PetersenGraph())
sage: i1 = iter(I); sage: i2 = iter(I)
sage: i1.next()
[0]
sage: i2.next()
[0, 2]
sage: i1.next()
[0, 2, 6]
sage: i2.next()
[0, 2, 8]
}}}
In other words an iterator is an iterator and nothing else. If you want to
design the set of independent sets it should be an object different from
the iterator. It would be better to have a Python class `IndependentSets`
desinged to modelize the set of independent sets (it should inherit from
`Parent` :P) and a Cython iterator `IndependentSetIterator`. What do you
think?
2) Could you provide a method to graph (independent_set_iterator or/and
independent_sets)?
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`.
'''Possible improvements'''
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.
'''Documentation'''
1) The complement of an independent set is a dominating set, right (not a
clique) ? If so, please change the documentation accordingly.
2) wikipedia links might be useful
:wikipedia:Independent_set_(graph_theory), :wikipedia:Dominating_set,
:wikipedia:Clique_graph
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:6>
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.
