UnionFind.jl is a light-weight library for identifying groups of nodes in undirected graphs. It is written in Julia 0.7. It is currently in version 0.1.0.

This library exports two types, UnionFinder, and CompressedFinder.

UnionFinder{T <: Integer} is a graph representation which allows for the dynamic addition of edges as well as the identification of groups.

• UnionFinder{T <: Integer}(nodes :: T) :: UnionFinder{T} returns a UnionFinder instance representing a graph of nodes unconnected nodes. Each node will be indexed by a unique integer of type T in the inclusive range [1, nodes]. If nodes is non-positive, an ArgumentError will be thrown.

The identification of groups is handled lazily, meaning that all non-trivial methods will modify the contents of the target UnionFinder instance.

• union!{T <: Integer}(uf :: UnionFinder{T}, u :: T, v :: T) adds an edge to uf connecting node u to node v. If either u or v is non-positive or greater than nodes, a BoundsError will be thrown.
• union!{T <: Integer}(uf :: UnionFinder{T}, edges :: Array{(T, T)}) adds each edges within edges to uf. This method obeys the same bounds restrictions as the single edge union! method.
• union!{T <: Integer}(uf :: UnionFinder{T}, us :: Array{T}, vs :: Array{T}) adds edges of the form (us[i], vs[i]) to uf. This method obeys the same bounds restrictions as the single edge union! method.
• find!{T <: Integer}(uf :: UnionFinder{T}, node :: T) :: T returns the unique id of the node group containing node.
• size!{T <: Integer}(uf :: UnionFinder{T}, node :: T) :: T returns the number of nodes in the group containing node.
• reset!(uf :: UnionFinder) disconnects all nodes within uf, allowing for a new set of edges to be analyzed without making further allocations.
• length(uf :: UnionFinder) :: Int returns the number of nodes within uf.

The fields of UnionFinder instances should not be accesed by user-level code.

CompressedFinder{T <: Integer}

• CompressedFinder{T <: Integer}(uf :: UnionFinder) :: CompressedFinder{T} returns a CompressedFinder instance corresponding to the same groups represented by

• find{T <: Integer}(cf :: CompressedFinder{T}, node :: T) :: T returns the unique id of the group containing node. If node is non-positive or is larger than the number of nodes in cf, a BoundsError is thrown.
• groups{T <: Integer}(cf :: CompressedFinder{T}) :: T returns the number of groups within cf.

• ids :: Array{T} is an array mapping node indices to the group which contains them.
• groups :: T is the number of groups in the CompressedFinder instance.

using UnionFind

function floodfill(grid, wrap=false)
    uf = UnionFinder(length(grid))

    height, width = size(grid)
    for x in 1:width
        for y in 1:height
            # Look rightwards.
            if x != width && grid[x, y] == grid[x + 1, y]
                union!(uf, flatten(x, y, grid), flatten(x + 1, y, grid))
            elseif wrap && grid[x, y] == grid[1, y]
                union!(uf, flatten(x, y, grid), flatten(1, y, grid))
            end

            # Look upwards.
            if y != height && grid[x, y] == grid[x, y + 1]
                union!(uf, flatten(x, y, grid), flatten(x, y + 1, grid))
            elseif wrap && grid[x, y] == grid[x, 1]
                union!(uf, flatten(x, y, grid), flatten(x, 1, grid))
            end
        end
    end

    cf = CompressedFinder(uf)
    return reshape(cf.ids, size(grid))
end

flatten(x, y, grid) = y + (x - 1)size(grid)[1]

using UnionFind

# edges must be pre-sorted according to weight.
function kruskal{T <: Integer}(nodes :: T, edges :: Array{(T, T)})
    uf = UnionFinder(nodes)
    mst = Array{(T, T)}

    for i in 1:length(edges)
        (u, v) = edges[i]
        if find!(uf, u) != find!(uf, v)
            union!(uf, u, v)
            push!(mst, (u, v))
        end
    end
end