Conversion DisjointSets to set of sets

Feature requested by Ed. Scheinerman of Hopkins
(doing cool graph theory stuff with julia)

He offers a solution as well

using DataStructures

# This takes a DisjointSets object and returns its ground set
function ground_set{T}(DS::DisjointSets{T})
    G = Set{T}()
    for item in keys(DS.intmap)
        push!(G,item)
    end
    return G
end


function set_of_sets{T}(DS::DisjointSets{T})
    n = num_groups(DS)
    GS = ground_set(DS)

    # Get root elements
    roots = Set{Int}()
    for item in GS
        r = find_root(DS,item)
        push!(roots,r)
    end
    roots = collect(roots)

    # Map root numbers to [1:n]
    rootmap = Dict{Int,Int}()
    for k=1:n
        rootmap[roots[k]] = k
    end

    # Create an array of sets to hold the parts
    parts = Array(Set{T},n)
    for k=1:n
        parts[k] = Set{T}()
    end

    # place each ground set item in its appropriate part
    for item in GS
        index = rootmap[find_root(DS,item)]
        push!(parts[index], item)
    end

    # now take those parts and pack them into a set
    P = Set{Set{T}}() # This is a set of sets
    for item in parts
        push!(P,item)
    end

    return P
end

Moved from https://github.com/JuliaLang/julia/issues/7310

Start by locating the DisjointSets implementation and reviewing its num_groups, find_root, and internal mapping APIs. Compare the requested ground_set and set_of_sets behavior with existing collection conventions, then verify that the conversion preserves every element and group in the returned set of sets.