# template class mrpt::graphs::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:

1. 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.

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.
#include <mrpt/graphs/CGraphPartitioner.h>

template <class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
class CGraphPartitioner
{
public:
//
methods

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
);

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
);

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
);

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

## Methods¶

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.

Parameters:

 in_A [IN] The weights matrix for the graph. It must be a square matrix, where element W ij is the “likelihood” between nodes “i” and “j”, and typically W ii = 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 W ij and W ji are replaced by 0.5*(W ij +W ji). 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 a std::logic_error if an invalid matrix is passed.

SpectralBisection

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.

Parameters:

 in_A [IN] The weights matrix for the graph. It must be a square matrix, where element W ij is the “likelihood” between nodes “i” and “j”, and typically W ii = 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 W ij and W ji are replaced by 0.5*(W ij +W ji). Set to false if matrix is known to be simetric. 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)

Parameters:

 in_A [IN] The weights matrix for the graph. It must be a square matrix, where element W ij is the “likelihood” between nodes “i” and “j”, and typically W ii = 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 W ij and W ji are replaced by 0.5*(W ij +W ji). Set to false if matrix is known to be simetric. Throws a std::logic_error if an invalid matrix is passed.

static num_t nCut(
)