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 elixyre)

Hi,

I want append a simple shortcut for iter elements of the class : DisjointSet?.

Attachments (3)

trac14411-disjoint_set-EliX-jbp.patch (1.0 KB) - added by elixyre 8 years ago.
shortcut DisjointSet?.iter
trac14411-disjoint_set-EliX-jbp.2.patch (1.7 KB) - added by elixyre 8 years ago.
trac14411-disjoint_set-EliX-jbp.3.patch (1.6 KB) - added by elixyre 8 years ago.

Download all attachments as: .zip

Change History (20)

Changed 8 years ago by elixyre

shortcut DisjointSet?.iter

comment:1 Changed 8 years ago by elixyre

  • Description modified (diff)

comment:2 Changed 8 years ago by tscrim

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

comment:3 follow-up: Changed 8 years ago by elixyre

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 tscrim

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 slabbe

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

comment:6 Changed 8 years ago by elixyre

No i'm okay with that. So I modify my patch to be consistent.

comment:7 Changed 8 years ago by tscrim

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

Last edited 8 years ago by tscrim (previous) (diff)

comment:8 Changed 8 years ago by elixyre

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 tscrim

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 ncohen

  • Status changed from needs_review to needs_work

comment:11 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:12 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 4 years ago by slabbe

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

  • Authors Jean-Baptiste Priez deleted
  • 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 embray

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

Note: See TracTickets for help on using tickets.