template class mrpt::graphs::CGraphPartitioner

Overview

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:

    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.

See also:

SpectralBisection

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.

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 W ij is the “likelihood” between nodes “i” and “j”, and typically W ii = 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 W ij and W ji are replaced by 0.5*(W ij +W ji). Set to false if matrix is known to be simetric.

Throws

a std::logic_error if an invalid matrix is passed.

See also:

mrpt::math::CMatrixF, RecursiveSpectralPartition

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)

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_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 W ij and W ji are replaced by 0.5*(W ij +W ji). Set to false if matrix is known to be simetric.

Throws

a std::logic_error if an invalid matrix is passed.

See also:

mrpt::math::CMatrixF, RecursiveSpectralPartition

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: