Opened 8 years ago
Closed 4 years ago
#14411 closed enhancement (wontfix)
Disjoint Sets --> iter
Reported by: | elixyre | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | misc | Keywords: | |
Cc: | florent.hivert@…, slabbe | Merged in: | |
Authors: | Reviewers: | Travis Scrimshaw | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Hi,
I want append a simple shortcut for iter elements of the class : DisjointSet?.
Attachments (3)
Change History (20)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Component changed from graph theory to misc
- Reviewers set to Travis Scrimshaw
- Status changed from new to needs_review
- Type changed from PLEASE CHANGE to enhancement
A few things I would like to see:
- Reference the ticket number in the commit message
- Use double quotes instead of single quotes for consistency
- Since dictionaries are non-deterministic in their ordering, could you change the last test to something like
sage: L = [s for s in d] sage: len(L) 3
Also you probably could just return self.root_to_elements_dict().itervalues()
since it is an iterator object (it avoids a level of indirection).
Thanks,
Travis
PS - I'm assuming this was suppose to be set to needs_review. Sorry if it wasn't.
Changed 8 years ago by
comment:3 follow-up: ↓ 5 Changed 8 years ago by
I made a new version. It's ok with that?
Furthermore, I added a new method _getitem_
which return the set associated to the argument:
sage: d = DisjointSet(range(4)) sage: d.union(1,2); d {{0}, {1,2}, {3}} sage: d[2] [1,2]
(My opinion is when we write d.find(2)
we expect
[1,2]
and not
1
(that means nothing for user) but I don't want reimplement all so... what is your opinion about that?)
Thanks,
Jean-Baptiste
comment:4 Changed 8 years ago by
From the wikipedia page, find()
returns the representative of the subset, not the entire subset. As such, to be consistent with find()
and the expected behavior of DisjointSet
, I think __getitem__()
should return the representative as well.
Thanks,
Travis
comment:5 in reply to: ↑ 3 Changed 8 years ago by
- Cc slabbe added; slabqc@… removed
(My opinion is when we write
d.find(2)
we expect
[1,2]
and not
1
(that means nothing for user) but I don't want reimplement all so... what is your opinion about that?)
The data structure is made so that knowing if two elements a
and
b
are in the same subset is optimal in time complexity :
d.find(a) == d.find(b)
. Returning the whole subset containing the element
2
is another question and its time complexity is very different (you need to call
find
on every elements...).
Are you sure you need the union-find data structure for your problem?
Changed 8 years ago by
comment:6 Changed 8 years ago by
No i'm okay with that. So I modify my patch to be consistent.
comment:7 Changed 8 years ago by
I still think __getitem__
should be the same as find()
. In particular, I'd just set
__getitem__ = find
and add a doctest to the class/module doc. If you want a method to return the full subset, you should call it something like get_subset()
. Also could you make the first line of your comment message be a short description of the patch.
Thanks,
Travis
comment:8 Changed 8 years ago by
Hi,
Last time I answered little bit quickly (and my code is false). For me, a disjoint union is roughly a list of list (set of disjoint sets) with two particular method union
and find
. It seems natural (and consistent with the representation), if there is a _getitem_
method that returns one of these lists. It will be disturbing and irrelevant to have
__getitem__ = find
And if you are agree with that my question is : what's the input? An element in the union of the sets or an indice? I think it could be interesting to have an element.
(I imagine a disjoint sets on all permutations of size k
, it seems cool and agradable to visualize easily the class of a particular permutation)
Thanks,
Jean-Baptiste
comment:9 Changed 8 years ago by
You're forgetting that this is not a dijoint union as a mathematical object but a specific data structure of DisjointSet
which is not a list of lists. In some sense, there is less structure as DisjointSet
is better described as a map from elements to a representative (in particular the subsets are not ordered). Thus the most logical behavior to me is that __getitem__()
should match find()
.
Actually considering that, the iterator should the representatives (i.e. the iterkeys()
) and not the subsets.
To reiterate, this is a tool (class) used to solve problems efficiently, not to represent a mathematical structure. The mathematical structure you're after would either be DisjointUnionEnumeratedSets
or SetPartitions
. If you really want to return the whole subset from an element, this should get its own specialized method.
Best,
Travis
comment:10 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:11 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:12 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:13 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:14 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:15 Changed 4 years ago by
- Status changed from needs_work to needs_review
I suggest to close this ticket as a duplicate of #20057.
comment:16 Changed 4 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from needs_review to positive_review
comment:17 Changed 4 years ago by
- Resolution set to wontfix
- Status changed from positive_review to closed
Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).
shortcut DisjointSet?.iter