template class mrpt::graphs::CGraphPartitioner

Overview

Finds the min-normalized-cut of a weighted undirected graph.

Two methods are provided:

SpectralBisection() : Bisection.
RecursiveSpectralPartition() : Iterative N-parts partition.

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.