#20057: Add iterator to DisjointSet class
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-7.1
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers: Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/iterate_disjoint_set | 1f96bc01bd77eea0bd64613a97c3f41857789526
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by slabbe):
I now remember why I did not coded the `__iter__`. It is because the two
basic and efficient methods of this data structure are join and find and
they are done lazyly. Lazyly in the sense that we you join the class of an
element a with the class of an element b, then the parent of the root of a
is now b or vice versa. It is not true that the structure is now that the
direct parent of all elements of the new merged class is equal to the
root. But this is what we get when we call `find` on all elements of the
data structure. At that time, I decided not to code `__iter__` because to
me, an internal method like `__iter__` is a basic internal method of
enumerable that is expected to be efficient. But for this particular data
structure, I did not find that calling `find` on every elements was in the
spirit of the data structure...
Anyway, I do think that a method that returns an enumerable on the roots
is useful as I answered to Jori in a private email yesterday. Thinking
about it now, I would have suggested a method `roots` that returns a list
of the roots (an iterator needs to store the list anyway), which avoids
the creation of the list of all elements in each class which is currently
done in the oneliner that got positively reviewed.
Also, one thing I would suggest is to add a `NotImplementedError` to the
`__iter__` to explain that such an enumeration needs to call `find` on all
elements which is a costly operation (all proportion preserved) for that
data structure. And suggest to use the method `roots`.
I let you decide if you agree with me and if we put this ticket on hold
...13 hours after a positive review.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
--
Ticket URL: <http://trac.sagemath.org/ticket/20057#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
