El lunes, 7 de abril de 2014 12:59:41 UTC-5, David P. Sanders escribió:
>
>
>
> El lunes, 7 de abril de 2014 12:35:05 UTC-5, David P. Sanders escribió:
>>
>> Hi,
>>
>> I need to (conceptually) add a field to the IntDisjointSets data
>> structure available in DataStructures.jl, which is basically the size
>> (number of elements) in each of the disjoint sets.
>>
>
> Sorry, that's not correct -- it's not the number of elements of each set;
> rather each set has a certain `size` which is a separate quantity.
>
> I have been playing with it, and all the functions are easy to implement,
> except for union!:
> the new union! will be a word-for-word copy of the old union!, except that
> the information about the size also has to be updated.
> Is there some way of avoiding copy-paste in this case?
>
Apologies for the multiple auto-replies, but there doesn't seem to be a way
to edit a previous post?
A possible solution would perhaps be for the original union! to return the
(xroot, yroot, newroot), where newroot is the root that it finally chose;
with this information, the
new union! function would have enough information to update the sizes
structure.
>
> using DataStructures
> import Base.length
>
> type MyDisjointSets
> forest::IntDisjointSets
> sizes::Vector{Int}
>
> MyDisjointSets(n::Integer) = new(IntDisjointSets(n), ones(n))
> end
>
> length(s::MyDisjointSets) = length(s.forest)
> num_groups(s::MyDisjointSets) = num_groups(s)
>
> find_root(s::MyDisjointSets, x::Integer) = find_root(s.forest, x)
> in_same_set(s::MyDisjointSets, x::Integer, y::Integer) =
> find_root(s.forest, x) == find_root(s.forest, y)
>
>
>
>
>> What is the julian way to do this kind of "inheritance"?
>> Should I create a new type which *contains* an IntDisjointSets object and
>> another Vector, and then define the functions find_root and union! for that
>> new structure?
>>
>> Would there be interest in adding this to DataStructures once it's
>> implemented?
>>
>> Thanks,
>> David
>>
>
