Main MRPT website > C++ reference for MRPT 1.4.0
CGraphPartitioner.h
Go to the documentation of this file.
1/* +---------------------------------------------------------------------------+
2 | Mobile Robot Programming Toolkit (MRPT) |
3 | http://www.mrpt.org/ |
4 | |
5 | Copyright (c) 2005-2016, Individual contributors, see AUTHORS file |
6 | See: http://www.mrpt.org/Authors - All rights reserved. |
7 | Released under BSD License. See details in http://www.mrpt.org/License |
8 +---------------------------------------------------------------------------+ */
9#ifndef CGRAPHPARTITIONER_H
10#define CGRAPHPARTITIONER_H
11
14#include <mrpt/math/CMatrix.h>
16
17namespace mrpt
18{
19 /** Abstract graph and tree data structures, plus generic graph algorithms
20 * \ingroup mrpt_graphs_grp
21 */
22 namespace graphs
23 {
24 /** Algorithms for finding the min-normalized-cut of a weighted undirected graph.
25 * Two methods are provided, one for bisection and the other for
26 * iterative N-parts partition.
27 * It is an implementation of the Shi-Malik method proposed in:<br><br>
28 * <code>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.</code><br>
29 *
30 * \tparam GRAPH_MATRIX The type of square matrices used to represent the connectivity in a graph (e.g. mrpt::math::CMatrix)
31 * \tparam num_t The type of matrix elements, thresholds, etc. (typ: float or double). Defaults to the type of matrix elements.
32 *
33 * \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.
34 */
35 template <class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
37 {
38 public:
39 /** Performs the spectral recursive partition into K-parts for a given graph.
40 * The default threshold for the N-cut is 1, which correspond to a cut equal
41 * of the geometric mean of self-associations of each pair of groups.
42 *
43 * \param in_A [IN] The weights matrix for the graph. It must be a square matrix, where element W<sub>ij</sub> is the "likelihood" between nodes "i" and "j", and typically W<sub>ii</sub> = 1.
44 * \param out_parts [OUT] An array of partitions, where each partition is represented as a vector of indexs for nodes.
45 * \param threshold_Ncut [IN] If it is desired to use other than the default threshold, it can be passed here.
46 * \param forceSimetry [IN] If set to true (default) the elements W<sub>ij</sub> and W<sub>ji</sub> are replaced by 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to be simetric.
47 * \param 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.
48 * \param recursive [IN] Default=true, recursive algorithm for finding N partitions. Set to false to force 1 bisection as maximum.
49 * \param minSizeClusters [IN] Default=1, Minimum size of partitions to be accepted.
50 *
51 * \sa mrpt::math::CMatrix, SpectralBisection
52 *
53 * \exception Throws a std::logic_error if an invalid matrix is passed.
54 */
56 GRAPH_MATRIX &in_A,
57 std::vector<vector_uint> &out_parts,
58 num_t threshold_Ncut = 1,
59 bool forceSimetry = true,
60 bool useSpectralBisection = true,
61 bool recursive = true,
62 unsigned minSizeClusters = 1,
63 const bool verbose = false);
64
65 /** Performs the spectral bisection of a graph. This method always perform
66 * the bisection, and a measure of the goodness for this cut is returned.
67 *
68 * \param in_A [IN] The weights matrix for the graph. It must be a square matrix, where element W<sub>ij</sub> is the "likelihood" between nodes "i" and "j", and typically W<sub>ii</sub> = 1.
69 * \param out_part1 [OUT] The indexs of the nodes that fall into the first group.
70 * \param out_part2 [OUT] The indexs of the nodes that fall into the second group.
71 * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2].
72 * \param forceSimetry [IN] If set to true (default) the elements W<sub>ij</sub> and W<sub>ji</sub> are replaced by 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to be simetric.
73 *
74 * \sa mrpt::math::CMatrix, RecursiveSpectralPartition
75 *
76 * \exception Throws a std::logic_error if an invalid matrix is passed.
77 */
78 static void SpectralBisection(
79 GRAPH_MATRIX &in_A,
80 vector_uint &out_part1,
81 vector_uint &out_part2,
82 num_t &out_cut_value,
83 bool forceSimetry = true );
84
85 /** Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm)
86 *
87 * \param in_A [IN] The weights matrix for the graph. It must be a square matrix, where element W<sub>ij</sub> is the "likelihood" between nodes "i" and "j", and typically W<sub>ii</sub> = 1.
88 * \param out_part1 [OUT] The indexs of the nodes that fall into the first group.
89 * \param out_part2 [OUT] The indexs of the nodes that fall into the second group.
90 * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2].
91 * \param forceSimetry [IN] If set to true (default) the elements W<sub>ij</sub> and W<sub>ji</sub> are replaced by 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to be simetric.
92 *
93 * \sa mrpt::math::CMatrix, RecursiveSpectralPartition
94 *
95 * \exception Throws a std::logic_error if an invalid matrix is passed.
96 */
97 static void exactBisection(
98 GRAPH_MATRIX &in_A,
99 vector_uint &out_part1,
100 vector_uint &out_part2,
101 num_t &out_cut_value,
102 bool forceSimetry = true );
103
104 /** Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection:
105 */
106 static num_t nCut(
107 const GRAPH_MATRIX &in_A,
108 const vector_uint &in_part1,
109 const vector_uint &in_part2 );
110
111 }; // End of class def.
112
113 } // End of namespace
114} // End of namespace
115
116// Template implementation:
118
119#endif
Algorithms for finding the min-normalized-cut of a weighted undirected graph.
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.
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:
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.
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 fast...
This base class provides a common printf-like method to send debug information to std::cout,...
std::vector< uint32_t > vector_uint
Definition: types_simple.h:28
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
This file implements miscelaneous matrix and matrix/vector operations, and internal functions in mrpt...



Page generated by Doxygen 1.9.6 for MRPT 1.4.0 SVN: at Wed Mar 22 09:54:56 UTC 2023