Main MRPT website > C++ reference for MRPT 1.5.9
List of all members | Static Public Member Functions
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 >

Algorithms for finding the min-normalized-cut of a weighted undirected graph.

Two methods are provided, one for bisection and the other for iterative N-parts partition. It 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_MATRIXThe type of square matrices used to represent the connectivity in a graph (e.g. mrpt::math::CMatrix)
num_tThe type of matrix elements, thresholds, etc. (typ: float or double). Defaults to the type of matrix elements.
Note
Prior to MRPT 1.0.0 this class wasn't a template and provided static variables for debugging, which were removed since that version.

Definition at line 36 of file CGraphPartitioner.h.

#include <mrpt/graphs/CGraphPartitioner.h>

Inheritance diagram for mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >:
Inheritance graph

Static Public Member Functions

static void RecursiveSpectralPartition (GRAPH_MATRIX &in_A, std::vector< vector_uint > &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, vector_uint &out_part1, vector_uint &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, vector_uint &out_part1, vector_uint &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 vector_uint &in_part1, const vector_uint &in_part2)
 Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection: More...
 

Member Function Documentation

◆ exactBisection()

template<class GRAPH_MATRIX , typename num_t >
void mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::exactBisection ( GRAPH_MATRIX &  in_A,
vector_uint out_part1,
vector_uint 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.
See also
mrpt::math::CMatrix, RecursiveSpectralPartition
Exceptions
Throwsa std::logic_error if an invalid matrix is passed.

Definition at line 271 of file CGraphPartitioner_impl.h.

References ASSERT_, and THROW_EXCEPTION.

◆ nCut()

template<class GRAPH_MATRIX , typename num_t >
num_t mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::nCut ( const GRAPH_MATRIX &  in_A,
const vector_uint in_part1,
const vector_uint in_part2 
)
static

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

Definition at line 229 of file CGraphPartitioner_impl.h.

◆ RecursiveSpectralPartition()

template<class GRAPH_MATRIX , typename num_t >
void mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::RecursiveSpectralPartition ( GRAPH_MATRIX &  in_A,
std::vector< vector_uint > &  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.
See also
mrpt::math::CMatrix, SpectralBisection
Exceptions
Throwsa std::logic_error if an invalid matrix is passed.

Definition at line 101 of file CGraphPartitioner_impl.h.

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

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

◆ SpectralBisection()

template<class GRAPH_MATRIX , typename num_t >
void mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::SpectralBisection ( GRAPH_MATRIX &  in_A,
vector_uint out_part1,
vector_uint 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.
See also
mrpt::math::CMatrix, RecursiveSpectralPartition
Exceptions
Throwsa std::logic_error if an invalid matrix is passed.

Definition at line 24 of file CGraphPartitioner_impl.h.

References eigenValues(), eigenVectors(), mean(), and THROW_EXCEPTION.




Page generated by Doxygen 1.8.14 for MRPT 1.5.9 Git: 690a4699f Wed Apr 15 19:29:53 2020 +0200 at miƩ abr 15 19:30:12 CEST 2020