Template Function brille::munkres_permutation

Function Documentation

template<class T, class R, class I, typename = typename std::enable_if<std::is_same<typename CostTraits<T>::type, R>::value>::type>
bool brille::munkres_permutation(const T *centre, const T *neighbour, const std::array<I, 3> &Nel, const R Wscl, const R Wvec, const R Wmat, const size_t span, const size_t Nobj, bArray<size_t> &permutations, const size_t centre_idx, const size_t neighbour_idx, const int vec_cost_func = 0)

Use Munkres’ Assignment algorithm to determine a permutation.

For two arrays of data, located in memory at centre and neighbour, and each representing Nobj sets of Nel[0] scalars, Nel[1] vector elements, and Nel[2] matrix elements, determine the sorting permutation that maps the elements at centre onto the same global mapping as the sorting permutation already stored at permutations[neighbour_idx]. The resultant global permutation is stored at permutations[centre_idx].

Each array of data to be compared must be formatted as: 

  [ 0{(0…Nel[0]-1)(0…Nel[1]-1)(0…Nel[2]-1)}
    1{(0…Nel[0]-1)(0…Nel[1]-1)(0…Nel[2]-1)}
    ⋮
    Nobj-1{(0…Nel[0]-1)(0…Nel[1]-1)(0…Nel[2]-1)} ]

The function constructs an Nobj×Nobj cost matrix, where each element is given by 

  Cᵢⱼ = Wscl×∑ₖ₋₀ᴺˢᶜˡ√(centre[i,k]-neighbour[j,k])
      + Wvec×𝔣ᵥ(centre_vec[i],neighbour_vec[j])
      + Wmat×𝔣ₘ(centre_mat[i],neighbour_mat[j])

where Wscl, Wvec, and Wmat are weight factors for adjusting the relative cost of the scalar, vector, and matrix differences, respectively; 𝔣ᵥ is the vector cost function; and 𝔣ₘ is the matrix cost function.

The vector cost function is selected by vec_cost_func to be one of: the angle between the vectors, the length of the difference between the vectors, or one minus the inner product of the vectors.

The matrix cost function is the Frobenius norm of the difference between the two matrices.

Return

true if the permutation was assigned successfully, otherwise false

Parameters

  • centre: The values to be sorted by the determined permutation

  • neighbour: The values against which the centre values are compared

  • Nel: The number of scalars, vector elements, and matrix elements per object

  • Wscl: The cost weight for scalar elements

  • Wvec: The cost weight for vectors

  • Wmat: The cost weight for matrices

  • span: The number of elements per object, Nel[0]+Nel[1]+Nel[2]

  • Nobj: The number of objects at each of centre and neighbour

  • [out] permutations: Contains the global permutation sorting for the neighbour and is where the centre permutation is stored

  • centre_idx: The index into permutations where the output is stored

  • neighbour_idx: The index into permutations to find the neighbour permutation

  • vec_cost_func: Used to select the eigenvector cost function: 0 –> vector_angle 1 –> vector_distance 2 –> 1-brille::utils::vector_product 3 –> abs(sin(brille::utils::hermitian_angle))