Algorithms for finding the min-normalized-cut of a weighted undirected graph. More...
#include <mrpt/math/CGraphPartitioner.h>
Static Public Member Functions | |
static void | RecursiveSpectralPartition (CMatrix &in_A, std::vector< vector_uint > &out_parts, float threshold_Ncut=1.0f, bool forceSimetry=true, bool useSpectralBisection=true, bool recursive=true, unsigned minSizeClusters=1) |
Performs the spectral recursive partition into K-parts for a given graph. | |
static void | SpectralBisection (CMatrix &in_A, vector_uint &out_part1, vector_uint &out_part2, float &out_cut_value, bool forceSimetry=true) |
Performs the spectral bisection of a graph. | |
static void | exactBisection (CMatrix &in_A, vector_uint &out_part1, vector_uint &out_part2, float &out_cut_value, bool forceSimetry=true) |
Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm). | |
static float | nCut (const CMatrix &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:. | |
Static Public Attributes | |
static bool | DEBUG_SAVE_EIGENVECTOR_FILES |
If set to true (default=false), each eigenvector computed (and the laplacian of the adj. | |
static bool | VERBOSE |
If set to true (default=false), debug info will be displayed to cout. | |
Static Private Attributes | |
static int | debug_file_no |
Used internally when DEBUG_SAVE_EIGENVECTOR_FILES=true. |
Algorithms for finding the min-normalized-cut of a weighted undirected graph.
Two static methods are provided, one for bisection and the other for iterative N-parts partition. It is based on the Shi-Malik method, proposed for example 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.
Definition at line 46 of file CGraphPartitioner.h.
static void mrpt::math::CGraphPartitioner::exactBisection | ( | CMatrix & | in_A, | |
vector_uint & | out_part1, | |||
vector_uint & | out_part2, | |||
float & | out_cut_value, | |||
bool | forceSimetry = true | |||
) | [static] |
Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm).
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 | a std::logic_error if an invalid matrix is passed. |
static float mrpt::math::CGraphPartitioner::nCut | ( | const CMatrix & | 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:.
static void mrpt::math::CGraphPartitioner::RecursiveSpectralPartition | ( | CMatrix & | in_A, | |
std::vector< vector_uint > & | out_parts, | |||
float | threshold_Ncut = 1.0f , |
|||
bool | forceSimetry = true , |
|||
bool | useSpectralBisection = true , |
|||
bool | recursive = true , |
|||
unsigned | minSizeClusters = 1 | |||
) | [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.
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 | a std::logic_error if an invalid matrix is passed. |
static void mrpt::math::CGraphPartitioner::SpectralBisection | ( | CMatrix & | in_A, | |
vector_uint & | out_part1, | |||
vector_uint & | out_part2, | |||
float & | 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.
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 | a std::logic_error if an invalid matrix is passed. |
int mrpt::math::CGraphPartitioner::debug_file_no [static, private] |
Used internally when DEBUG_SAVE_EIGENVECTOR_FILES=true.
Definition at line 132 of file CGraphPartitioner.h.
If set to true (default=false), each eigenvector computed (and the laplacian of the adj.
matrix) will be saved to files "DEBUG_GRAPHPART_eigvectors_xxx" and "DEBUG_GRAPHPART_laplacian_xxx", respectively.
Definition at line 123 of file CGraphPartitioner.h.
bool mrpt::math::CGraphPartitioner::VERBOSE [static] |
If set to true (default=false), debug info will be displayed to cout.
Definition at line 127 of file CGraphPartitioner.h.
Page generated by Doxygen 1.6.1 for MRPT 0.7.1 SVN: at Tue Dec 22 08:29:35 CET 2009 |