Template Class CGraphPartitioner

Class Documentation

template<class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
class CGraphPartitioner

Finds the min-normalized-cut of a weighted undirected graph. Two methods are provided:

This is an implementation of the Shi-Malik method proposed in:

  • J. Shi and J. Malik, “Normalized Cuts and Image Segmentation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, no.8, pp. 888-905, Aug. 2000.

Template Parameters:

  • GRAPH_MATRIX – The type of square matrices used to represent the connectivity in a graph. Supported types are: mrpt::math::CMatrixDouble, mrpt::math::CMatrixD, mrpt::math::CMatrixFloat, mrpt::math::CMatrixF

  • num_t – The type of matrix elements, thresholds, etc. (double or float). Defaults to the type of matrix elements.

Public Static Functions

static void RecursiveSpectralPartition(GRAPH_MATRIX &in_A, std::vector<std::vector<uint32_t>> &out_parts, num_t threshold_Ncut = 1, bool forceSimetry = true, bool useSpectralBisection = true, bool recursive = true, unsigned minSizeClusters = 1, const bool verbose = false)

Performs the spectral recursive partition into K-parts for a given graph. The default threshold for the N-cut is 1, which correspond to a cut equal of the geometric mean of self-associations of each pair of groups.

See also

SpectralBisection

Parameters:

  • in_A – [IN] The weights matrix for the graph. It must be a square matrix, where element Wij is the “likelihood” between nodes “i” and “j”, and typically Wii = 1.

  • out_parts – [OUT] An array of partitions, where each partition is represented as a vector of indexs for nodes.

  • threshold_Ncut – [IN] If it is desired to use other than the default threshold, it can be passed here.

  • forceSimetry – [IN] If set to true (default) the elements Wij and Wji are replaced by 0.5*(Wij+Wji). Set to false if matrix is known to be simetric.

  • useSpectralBisection – [IN] If set to true (default) a quick spectral bisection will be used. If set to false, a brute force, exact finding of the min-cut is performed.

  • recursive – [IN] Default=true, recursive algorithm for finding N partitions. Set to false to force 1 bisection as maximum.

  • minSizeClusters – [IN] Default=1, Minimum size of partitions to be accepted.

Throws:

Throws – a std::logic_error if an invalid matrix is passed.

static void SpectralBisection(GRAPH_MATRIX &in_A, std::vector<uint32_t> &out_part1, std::vector<uint32_t> &out_part2, num_t &out_cut_value, bool forceSimetry = true)

Performs the spectral bisection of a graph. This method always perform the bisection, and a measure of the goodness for this cut is returned.

See also

mrpt::math::CMatrixF, RecursiveSpectralPartition

Parameters:

  • in_A – [IN] The weights matrix for the graph. It must be a square matrix, where element Wij is the “likelihood” between nodes “i” and “j”, and typically Wii = 1.

  • out_part1 – [OUT] The indexs of the nodes that fall into the first group.

  • out_part2 – [OUT] The indexs of the nodes that fall into the second group.

  • out_cut_value – [OUT] The N-cut value for the proposed cut, in the range [0-2].

  • forceSimetry – [IN] If set to true (default) the elements Wij and Wji are replaced by 0.5*(Wij+Wji). Set to false if matrix is known to be simetric.

Throws:

Throws – a std::logic_error if an invalid matrix is passed.

static void exactBisection(GRAPH_MATRIX &in_A, std::vector<uint32_t> &out_part1, std::vector<uint32_t> &out_part2, num_t &out_cut_value, bool forceSimetry = true)

Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm)

See also

mrpt::math::CMatrixF, RecursiveSpectralPartition

Parameters:

  • in_A – [IN] The weights matrix for the graph. It must be a square matrix, where element Wij is the “likelihood” between nodes “i” and “j”, and typically Wii = 1.

  • out_part1 – [OUT] The indexs of the nodes that fall into the first group.

  • out_part2 – [OUT] The indexs of the nodes that fall into the second group.

  • out_cut_value – [OUT] The N-cut value for the proposed cut, in the range [0-2].

  • forceSimetry – [IN] If set to true (default) the elements Wij and Wji are replaced by 0.5*(Wij+Wji). Set to false if matrix is known to be simetric.

Throws:

Throws – a std::logic_error if an invalid matrix is passed.

static num_t nCut(const GRAPH_MATRIX &in_A, const std::vector<uint32_t> &in_part1, const std::vector<uint32_t> &in_part2)

Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection: