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 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 10 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 10 years ago by rlm

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by jason

  • Cc jason added

comment:3 Changed 10 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 follow-up: Changed 10 years ago by abmasse

  • 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:

  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 10 years ago by abmasse

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

Alex

Changed 10 years ago by rlm

comment:6 Changed 10 years ago by rlm

  • 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: Changed 10 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 ; follow-up: Changed 10 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 10 years ago by slabbe

  • 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 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 follow-up: Changed 10 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 10 years ago by abmasse

  • 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 jdemeyer

  • Merged in set to sage-4.7.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.