Opened 12 years ago

Closed 12 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:

Status badges

Description (last modified by abmasse)

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)

trac_10886.patch (6.5 KB) - added by rlm 12 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 12 years ago by rlm

Status: newneeds_review

comment:2 Changed 12 years ago by jason

Cc: jason added

comment:3 Changed 12 years ago by abmasse

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 the DisjointSet_of_integers class. You should add it as well to the DisjointSet_of_hashables.

#. While you're at it, I suggest the name number_of_subsets instead of number_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 as cardinality, number_of_sets, etc. be there too?

comment:4 Changed 12 years ago by abmasse

Description: modified (diff)
Reviewers: Alexandre Blondin Massé
Status: needs_reviewneeds_info

Hi, Robert!

I just took a look at your patch. Two remarks and a question:

  1. The function number_of_sets you added is only defined for the DisjointSet_of_integers class. You should add it as well to the DisjointSet_of_hashables.
  1. While you're at it, I suggest the name number_of_subsets instead of number_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).
  1.  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 as cardinality, number_of_sets, etc. be there too?

comment:5 Changed 12 years ago by abmasse

Sorry for the duplicate message. I hit the "Submit changes" button instead of "Show preview" by accident.

Alex

Changed 12 years ago by rlm

Attachment: trac_10886.patch added

comment:6 Changed 12 years ago by rlm

Status: needs_infoneeds_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 ; Changed 12 years ago by slabbe

  1.  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 as cardinality, 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 ; Changed 12 years ago by rlm

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 12 years ago by slabbe

Reviewers: Alexandre Blondin Massé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 12 years ago by abmasse

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 Changed 12 years ago by 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.

Cheers,

Robert

comment:12 in reply to:  11 Changed 12 years ago by abmasse

Status: needs_reviewpositive_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 12 years ago by jdemeyer

Merged in: sage-4.7.alpha4
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.