MRPT logo

mrpt::math::CGraphPartitioner Class Reference

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

#include <mrpt/math/CGraphPartitioner.h>

Inheritance diagram for mrpt::math::CGraphPartitioner:

mrpt::utils::CDebugOutputCapable

List of all members.

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.


Detailed Description

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.


Member Function Documentation

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

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:
CMatrix, RecursiveSpectralPartition
Exceptions:
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.

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:
CMatrix, SpectralBisection
Exceptions:
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.

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


Member Data Documentation

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.

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.5.9 for MRPT 0.7.1 SVN: at Mon Aug 17 22:32:05 EDT 2009