DisjointSet: number of sets function

[rlm]

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.

[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?

[abmasse]

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.

2. 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).

3.  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?

[abmasse]

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

Alex

[rlm]

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

[slabbe]

3.  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

[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

[slabbe]

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

[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

[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

[abmasse]

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.