Sorting arrays of solutions

Sorting arrays of solutions

We provide functions for sorting analyzing arrays of vectors.

Computing unique points in an array of vectors

We provide the unique_points methods to sort through solutions.

unique_points(points::AbstractVector{<:AbstractVector}; options...)

Compute all unique points with respect to the given options. See UniquePoints for possible options. In particular, it is possible to pass group actions.

Example

julia> pts = [[1.0,0.5], [1.0,0.5], [0.5,1.0]];
julia> unique_points(pts)
2-element Array{Array{Float64,1},1}:
[1.0, 0.5]
[0.5, 1.0]

julia> unique_points(pts; group_action = x -> [x,x])
1-element Array{Array{Float64,1},1}:
[1.0, 0.5]

The unique_points method is powered by the UniquePoints data structure.

UniquePoints{V<:AbstractVector, T, F<:Function}

A data structure which holds points of type V where T=real(eltype(V)). This data structure provides an efficient (poly)logarithmic check whether a point already exists where two points u,v are considered equal if F(u,v)<tol, where tol is a tolerance provided through the add! function.

UniquePoints(v::AbstractVector{<:Number}, distance::F)

Initialize the data structure with just one data point v.

UniquePoints(V::Vector{<:AbstractVector{<:Number}}, distance::F; tol=1e-5)

Initialize the data structure with all points in v. These are added in order by add! with the given tolerance tol. In particular, 'UniquePoints' structure will contain only points for which the pairwise distance given by F is less than tol.

UniquePoints(v; kwargs...) = UniquePoints(v, euclidean_distance; kwargs...)

If F is not specialized, euclidean_distance is used.

Optional keywords:

• check_real=true adds real from points from group orbits (if they exist). The default is check_real=true.
• The user can use group_action=foo or, if there is more than one group acting, group_actions=[foo, bar]. Then, points that are in the same group orbit are considered equal. See GroupActions for details regarding the application rules.

Examples

julia> points(UniquePoints([[1.0,0.5], [1.0,0.5], [0.5,1.0]]))
2-element Array{Array{Float64,1},1}:
[1.0, 0.5]
[0.5, 1.0]

julia> points(UniquePoints([[1.0,0.5], [1.0,0.5], [0.5,1.0]], group_action = x -> [x,x]))
1-element Array{Array{Float64,1},1}:
[1.0, 0.5]

We provide several helper functions for UniquePoints.

points(data::UniquePoints)

Return the points stored in data.

is_contained(data::UniquePoints{V}, x::V; tol=1e-5)::Bool

Check whether x is contained in the data by using the tolerance tol to decide for duplicates.

is_contained(data::UniquePoints{V}, x::V, Val{true}(); tol=1e-5)::Int

If x is contained in data by using the tolerance tol return the index of the data point which already exists. If the data point is not existing -1 is returned. If data has the option check_real enabled, a -2 will be returned once a real vector was added.

Add x to data if it doesn't already exists by using the tolerance tol to decide for duplicates.

add!(data::UniquePoints{V}, x::V, Val(true); tol=1e-5)::Int

If x is contained in data by using the tolerance tol to decide for duplicates return the index of the data point which already exists. If the data point is not existing add it to data and return -1. If data has the option check_real enabled, a -2 will be returned once a real vector was added. The element will be the last element of points(data).

Similarly to add! but does not apply any group actions. If the data point is not existing add it to data and return -1. Otherwise the index of x in data.points is returned.

Base.empty!Function.
empty!(collection) -> collection

Remove all elements from a collection.

Examples

julia> A = Dict("a" => 1, "b" => 2)
Dict{String,Int64} with 2 entries:
"b" => 2
"a" => 1

julia> empty!(A);

julia> A
Dict{String,Int64} with 0 entries
source
empty!(data::UniquePoints)

Remove all points from data.

Computing points in an array of vectors which appear multiple times

If instead of unique points, the user wants to have the information which points in an array of points appear with multiplicity, they should use the next function.

multiplicities(vectors; distance=euclidean_distance, tol::Real = 1e-5, kwargs...)

Returns an array of arrays of integers. Each vector w in 'v' contains all indices i,j such that w[i] and w[j] have distance at most tol.

Optional keywords:

• check_real=true adds real from points from group orbits (if they exist) to the UniquePoints data structure used internally. The default is check_real=false.
• The user can use group_action=foo or, if there is more than one group acting, group_actions=[foo, bar]. Then, points that are in the same group orbit are considered equal. See GroupActions for details regarding the application rules.
julia> multiplicities([[1,0.5]; [1,0.5]; [1,1]])
[[1,2]]

This is the same as

multiplicities([[1,0.5]; [1,0.5]; [1,1]]; distance=(x,y) -> LinearAlgebra.norm(x-y))

Here is an example for using group actions.

julia> X = [[1, 2, 3, 4], [2,1,3,4], [1,2,4,3], [2,1,4,3]]
julia> permutation(x) = [x, x, x, x]
julia> m = multiplicities(X, group_action = permutation)
[[1,2], [3,4]]
multiplicities(V::Results; tol=1e-6)

Returns a Vector of Vector{PathResult}s grouping the PathResults whose solutions appear with multiplicities greater 1 in 'V'. Two solutions are regarded as equal, when their pairwise distance is less than 'tol'.

The multiplicities functions may also be applied to Result; see here: multiplicities(::HomotopyContinuation.Results).