Opened 10 years ago
Closed 10 years ago
#10886 closed enhancement (fixed)
DisjointSet: number of sets function
Reported by: | rlm | Owned by: | jason |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | misc | Keywords: | |
Cc: | slabbe, abmasse, jason | Merged in: | sage-4.7.alpha4 |
Authors: | Robert Miller | Reviewers: | Alexandre Blondin Massé, Sébastien Labbé |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The DisjointSet? data structure in Sage lacks the function returning the number of current subsets contained in it. The goal of this ticket is to add this functionality.
Attachments (1)
Change History (14)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Cc jason added
comment:3 Changed 10 years ago by
comment:4 follow-up: ↓ 7 Changed 10 years ago by
- Description modified (diff)
- Reviewers set to Alexandre Blondin Massé
- Status changed from needs_review to needs_info
Hi, Robert!
I just took a look at your patch. Two remarks and a question:
- The function
number_of_sets
you added is only defined for theDisjointSet_of_integers
class. You should add it as well to theDisjointSet_of_hashables
.
- While you're at it, I suggest the name
number_of_subsets
instead ofnumber_of_sets
, since we talk about partitioning a set into disjoint subsets. It follows the terminology used in the first line of Wikipedia (http://en.wikipedia.org/wiki/Disjoint-set_data_structure).
- My question is mainly addressed to Sébastien but maybe you know the answer. What is the reason for creating the class
DisjointSet_class
? It says that it is supposed to contain functions common to all disjoint set data structures, but it only contains two basic functions. Shouln't functions such ascardinality
,number_of_sets
, etc. be there too?
comment:5 Changed 10 years ago by
Sorry for the duplicate message. I hit the "Submit changes" button instead of "Show preview" by accident.
Alex
Changed 10 years ago by
comment:6 Changed 10 years ago by
- Status changed from needs_info to needs_review
Alexandre,
Right you are! I've addressed your three comments in the new version of the patch. I also noticed that the to_digraph function wasn't implemented for hashable sets, so I went ahead and did that too.
Cheers, Robert
comment:7 in reply to: ↑ 4 ; follow-up: ↓ 8 Changed 10 years ago by
- My question is mainly addressed to Sébastien but maybe you know the answer. What is the reason for creating the class
DisjointSet_class
? It says that it is supposed to contain functions common to all disjoint set data structures, but it only contains two basic functions. Shouln't functions such ascardinality
,number_of_sets
, etc. be there too?
I feel I would code that differently today... but let's try to remember why I did it that way. The actual classes hierarchy is:
cdef class DisjointSet_class(SageObject): cdef class DisjointSet_of_integers(DisjointSet_class): cdef class DisjointSet_of_hashables(DisjointSet_class):
Right now, the important attributes are not in DisjointSet_class
but in the two others. Moreover, the attributes are not the same, so that almost no method are coded the same way as you noticed.
I remember I hesitated to take the following hierarchy instead (in this situation, an instance of DisjointSet_of_hashables
would not contain an attribute DisjointSet_of_integers
as it is the case now) :
cdef class DisjointSet_of_integers(SageObject): cdef class DisjointSet_of_hashables(DisjointSet_of_integers):
But, then almost every methods of DisjointSet_of_integers
was overwritten by DisjointSet_of_hashables
. And since DisjointSet_of_hashables
is not a DisjointSet_of_integers
, I was feeling it was not a good hierarchy to choose. Maybe I did a mistake? Indeed, in this situation, the method number_of_sets
would be coded at only one place.
What do you think?
Sébastien
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 10 years ago by
Replying to slabbe:
What do you think?
Sébastien
Sébastien,
Can you take a look at the patch and give your opinion? I've made a few minor changes to the way the classes point at the underlying orbit partitions, which makes it easier for them to share functionality which doesn't depend on how the elements are labeled. I think this is the best "middle path" approach.
-- Robert
comment:9 in reply to: ↑ 8 Changed 10 years ago by
- Reviewers changed from Alexandre Blondin Massé to Alexandre Blondin Massé, Sébastien Labbé
Hi Robert,
Replying to rlm:
Can you take a look at the patch and give your opinion? I've made a few minor changes to the way the classes point at the underlying orbit partitions, which makes it easier for them to share functionality which doesn't depend on how the elements are labeled. I think this is the best "middle path" approach.
-- Robert
I completely agree with the patch. That's a "middle path" I haven't thought about. Adding this _nodes
attribute to the class DisjointSet_of_hashables
makes it behave like its twin which allow cardinality
and number_of_subsets
methods to jump to the parent. Thanks for the improvement.
To me it's a positive review (all tests passed, doc is fine).
Sébastien
comment:10 Changed 10 years ago by
Just some questions before I set this ticket to positive review.
Are cardinality
and number_of_subsets
the only functions that should jump to the parent class?
Correct me if I'm wrong: the reason why the methods find
, union
, root_to_elements_dict
, to_digraph
, etc. is that they are specific to each data structure. In principle, they all should be in the parent class, but be declared as "abstract", but this is not in the Python philosophy.
Does my understanding seems correct?
Alex
comment:11 follow-up: ↓ 12 Changed 10 years ago by
Alex,
I think that's all right. In principle, one could set dummy "translation" functions for the d.j.of integers class which simply act as the identity to make the code more uniform, but I don't think this is a good idea.
Cheers,
Robert
comment:12 in reply to: ↑ 11 Changed 10 years ago by
- Status changed from needs_review to positive_review
Replying to rlm:
Alex,
I think that's all right. In principle, one could set dummy "translation" functions for the d.j.of integers class which simply act as the identity to make the code more uniform, but I don't think this is a good idea.
Alright!
Same as Sébastien, I tested it on sage-4.6.2, looked at the documentation and everything is fine. Positive review.
comment:13 Changed 10 years ago by
- Merged in set to sage-4.7.alpha4
- Resolution set to fixed
- Status changed from positive_review to closed
Hi, Robert!
I just took a look at your patch. Two remarks and a question: