Opened 8 years ago
Last modified 7 years ago
#13917 closed enhancement
IndependentSets class — at Version 10
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | graph theory | Keywords: | |
Cc: | vdelecroix | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | ahmorales |
Report Upstream: | N/A | Work issues: | design, documentation |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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: 48.8 ms per loop sage: from sage.graphs.independent_sets import IndependentSets sage: %timeit list(IndependentSets(g,complement=True, maximal = True)) 10 loops, best of 3: 20.8 ms per loop sage: %timeit IndependentSets(g,complement=True, maximal = True).cardinality() 100 loops, best of 3: 19 ms per loop
Either way, this patch implements a sage.graphs.independent_set
module that can list/count (possibly maximal) independent sets.
Anyway, don't hesitate to tell me that this patch is useless if you feel like it. I'm not *that* convinced either.
Nathann
Change History (11)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
- Reviewers set to ahmorales
Changed 8 years ago by
comment:4 Changed 8 years ago by
- Cc vdelecroix added
comment:5 Changed 8 years ago by
Hi,
People from statistical physics are interested in finer quantities than the number of independent configurations (independent sets are related to particule interactions). In their case each configuration is counted with a weight of the form $\prod_{v \in I} \lambda(v)$
where $\lambda: V \rightarrow \mathbb{R}_+$
is a function on the vertices. Considering the case of $\lambda$ being constant, the code could even return the polynomial $f(\lambda)$
whose coefficient for $\lambda^k$
is the number of independent set with $k$
vertices (or equivalently the list of number of independent set of given size). Perhaps this polynomial has a name in graph theory ?
I let the serious comments to the reviewer.
Vincent
comment:6 follow-up: ↓ 7 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_review to needs_work
- Work issues set to design, documentation
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
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 8 years ago by
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 theStopIteration
.
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
comment:8 in reply to: ↑ 7 Changed 8 years ago by
Replying to 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 theStopIteration
.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)] += 1What 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.
comment:9 Changed 8 years ago by
(new patch that works with >64 vertices, based on top of 14589. And even slower than the first one >_<
)
Nathann
comment:10 Changed 8 years ago by
- Description modified (diff)
I think this patch is useful. I was looking for something to count independents sets of a given size since they index certain triangulations of polytopes coming from flows on graphs (#14654).