# 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(
)
{"ft_lang_label":"__label__en","ft_lang_prob":0.60871905,"math_prob":0.98102474,"size":5371,"snap":"2021-43-2021-49","text_gpt3_token_len":1464,"char_repetition_ratio":0.130613,"word_repetition_ratio":0.5621079,"special_character_ratio":0.26345187,"punctuation_ratio":0.2027833,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99647653,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-12-05T20:34:56Z\",\"WARC-Record-ID\":\"<urn:uuid:eea8017d-27d9-4ec5-85cb-42f66c692fcf>\",\"Content-Length\":\"34270\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:46b1f654-c090-4198-923c-461abcf20a0f>\",\"WARC-Concurrent-To\":\"<urn:uuid:bc93ef1c-da57-42b2-91f9-94856fe975d3>\",\"WARC-IP-Address\":\"150.214.150.101\",\"WARC-Target-URI\":\"https://mrpt.ual.es/reference/2.1.3/class_mrpt_graphs_CGraphPartitioner.html\",\"WARC-Payload-Digest\":\"sha1:CRLJ6KG2XFLYXWPDZ3GSEBY3PKGC4IUJ\",\"WARC-Block-Digest\":\"sha1:SCTHKBXYJLWSE26VZA4RJ6P6K2DWIODE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964363216.90_warc_CC-MAIN-20211205191620-20211205221620-00303.warc.gz\"}"}