MRPT  1.9.9
mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t > Class Template Reference

Detailed Description

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

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.

Definition at line 39 of file CGraphPartitioner.h.

#include <mrpt/graphs/CGraphPartitioner.h>

Static Public Member 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. More...

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

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) More...

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: More...

◆ exactBisection()

template<class GRAPH_MATRIX , typename num_t >
 void CGraphPartitioner::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

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 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.
mrpt::math::CMatrixF, RecursiveSpectralPartition
Exceptions
 Throws a std::logic_error if an invalid matrix is passed.

Definition at line 267 of file CGraphPartitioner.cpp.

References ASSERT_, and THROW_EXCEPTION.

◆ nCut()

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

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

Definition at line 230 of file CGraphPartitioner.cpp.

◆ RecursiveSpectralPartition()

template<class GRAPH_MATRIX , typename num_t >
 void CGraphPartitioner::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

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 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.
SpectralBisection
Exceptions
 Throws a std::logic_error if an invalid matrix is passed.

Definition at line 103 of file CGraphPartitioner.cpp.

References mrpt::format(), MRPT_END, MRPT_START, and THROW_EXCEPTION.

Referenced by mrpt::pbmap::SemanticClustering::evalPartition().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SpectralBisection()

template<class GRAPH_MATRIX , typename num_t >
 void CGraphPartitioner::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

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 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.
 Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: abb8b1a1e Fri Oct 18 14:19:12 2019 +0200 at vie oct 18 14:20:13 CEST 2019 