Create an interface for Disjoint Set data structure

[seblabbe]

I would like to have an easy to use disjoint-set data structure like the one described here:

http://en.wikipedia.org/wiki/Disjoint_set_data_structure

sage: d = DisjointSet(range(5))
sage: d
{{0}, {1}, {2}, {3}, {4}}
sage: d.union(3,4)
sage: d
{{0}, {1}, {2}, {3, 4}}
sage: d.union(0,2)
sage: d
{{0, 2}, {1}, {3, 4}}
sage: d.union(1,4)
sage: d.find(3)
3
sage: d.find(4)
3

As suggested by Robert Miller on sage-devel, one could use what is defined in

sage/groups/perm_gps/partn_ref/data_structures_*

CC: @rlmill

Component: combinatorics

Keywords: disjoint set data structure

Author: Sébastien Labbé

Reviewer: Robert Miller

Merged: sage-4.3.3.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/6775

[seblabbe]

comment:1

I just added a patch. I have two issues :

1. I still have some problems with pikling :

slabbe@slabbe-laptop:~/sage-4.1/devel/sage-combinat/sage/sets$ sage
----------------------------------------------------------------------
| Sage Version 4.1, Release Date: 2009-07-09                         |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: combinat
sage: d = DisjointSet(5)
sage: b = loads(dumps(d))
sage: b


------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occured in SAGE.
This probably occured because a *compiled* component
of SAGE has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run SAGE under gdb with 'sage -gdb' to debug this.
SAGE will now terminate (sorry).
------------------------------------------------------------

2. I am using the __del__ function to call the OP_dealloc, but I not sure it is proper...

[rlmill]

comment:4

1. You should probably declare things like

cdef class DisjointSet_of_integers(SageObject):
    cdef OrbitPartition *_nodes 

and

cdef class DisjointSet_of_hashable(SageObject):
   cdef list _int_to_el
   cdef dict _el_to_int
   cdef DisjointSet_of_integers _d

in disjoint_set.pxd instead of disjoint_set.pyx. That'll make it easier to use these classes elsewhere.

2. You should have __del__ print something and see if it's even getting called. I would define __dealloc__ and see if that gets called instead. You're using OP_dealloc correctly.

[seblabbe]

comment:5

I just replace the old patch and I solved the pickle problem.

Replying to @rlmill:

1. You should probably declare things like

[snip]

in disjoint_set.pxd instead of disjoint_set.pyx. That'll make it easier to use these classes elsewhere.

Done. Thanks for the comment. But is it really necessary since the function DisjointSet is the function used as a constructor? Should I also add that one to the .pxd ?

2. You should have __del__ print something and see if it's even getting called. I would define __dealloc__ and see if that gets called instead. You're using OP_dealloc correctly.

The function __del__ was not called, but __dealloc__ is. Although, I am getting memory errors when using the __dealloc__ function. I put a pass command in it and I get All test pass. Am I losing memory somewhere?

Needs review!

[rlmill]

comment:6

Replying to @seblabbe:

Replying to @rlmill:

1. You should probably declare things like

[snip]

in disjoint_set.pxd instead of disjoint_set.pyx. That'll make it easier to use these classes elsewhere.

Done. Thanks for the comment. But is it really necessary since the function DisjointSet is the function used as a constructor?

It would make things easier for developers using this later on, who want to use some Cython with this object. The DisjointSet function is a Python function, so it is irrelevant. I'm just talking about the class definitions.

2. You should have __del__ print something and see if it's even getting called. I would define __dealloc__ and see if that gets called instead. You're using OP_dealloc correctly.

The function __del__ was not called, but __dealloc__ is. Although, I am getting memory errors when using the __dealloc__ function. I put a pass command in it and I get All test pass. Am I losing memory somewhere?

Yes, because your dealloc isn't doing anything. You should replace pass with OP_dealloc(self._nodes).