MRPT  1.9.9
CGraphPartitioner.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2019, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
12 #include <vector>
13 
14 namespace mrpt
15 {
16 /** Abstract graph and tree data structures, plus generic graph algorithms
17  * \ingroup mrpt_graphs_grp
18  */
19 namespace graphs
20 {
21 /** Finds the min-normalized-cut of a weighted undirected graph.
22  * Two methods are provided:
23  * - SpectralBisection(): Bisection.
24  * - RecursiveSpectralPartition(): Iterative N-parts partition.
25  *
26  * This is an implementation of the Shi-Malik method proposed in:
27  * - J. Shi and J. Malik, "Normalized Cuts and Image Segmentation",
28  * IEEE Transactions on Pattern Analysis and Machine Intelligence,
29  * vol.22, no.8, pp. 888-905, Aug. 2000.
30  *
31  * \tparam GRAPH_MATRIX The type of square matrices used to represent the
32  * connectivity in a graph. Supported types are: mrpt::math::CMatrixDouble,
33  * mrpt::math::CMatrixD, mrpt::math::CMatrixFloat, mrpt::math::CMatrixF
34  *
35  * \tparam num_t The type of matrix elements, thresholds, etc. (double or
36  * float). Defaults to the type of matrix elements.
37  */
38 template <class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
40 {
41  public:
42  /** Performs the spectral recursive partition into K-parts for a given
43  * graph.
44  * The default threshold for the N-cut is 1, which correspond to a cut
45  * equal of the geometric mean of self-associations of each pair of groups.
46  *
47  * \param in_A [IN] The weights matrix for the graph. It must be a square
48  * matrix, where element W<sub>ij</sub> is the "likelihood" between nodes
49  * "i" and "j", and typically W<sub>ii</sub> = 1.
50  * \param out_parts [OUT] An array of partitions, where each partition is
51  * represented as a vector of indexs for nodes.
52  * \param threshold_Ncut [IN] If it is desired to use other than the default
53  * threshold, it can be passed here.
54  * \param forceSimetry [IN] If set to true (default) the elements
55  * W<sub>ij</sub> and W<sub>ji</sub> are replaced by
56  * 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to
57  * be simetric.
58  * \param useSpectralBisection [IN] If set to true (default) a quick
59  * spectral bisection will be used. If set to false, a brute force, exact
60  * finding of the min-cut is performed.
61  * \param recursive [IN] Default=true, recursive algorithm for finding N
62  * partitions. Set to false to force 1 bisection as maximum.
63  * \param minSizeClusters [IN] Default=1, Minimum size of partitions to be
64  * accepted.
65  *
66  * \sa SpectralBisection
67  *
68  * \exception Throws a std::logic_error if an invalid matrix is passed.
69  */
70  static void RecursiveSpectralPartition(
71  GRAPH_MATRIX& in_A, std::vector<std::vector<uint32_t>>& out_parts,
72  num_t threshold_Ncut = 1, bool forceSimetry = true,
73  bool useSpectralBisection = true, bool recursive = true,
74  unsigned minSizeClusters = 1, const bool verbose = false);
75 
76  /** Performs the spectral bisection of a graph. This method always perform
77  * the bisection, and a measure of the goodness for this cut is returned.
78  *
79  * \param in_A [IN] The weights matrix for the graph. It must be a
80  * square
81  * matrix, where element W<sub>ij</sub> is the "likelihood" between nodes
82  * "i" and "j", and typically W<sub>ii</sub> = 1.
83  * \param out_part1 [OUT] The indexs of the nodes that fall into the
84  * first
85  * group.
86  * \param out_part2 [OUT] The indexs of the nodes that fall into the
87  * second
88  * group.
89  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the
90  * range [0-2].
91  * \param forceSimetry [IN] If set to true (default) the elements
92  * W<sub>ij</sub> and W<sub>ji</sub> are replaced by
93  * 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to
94  * be simetric.
95  *
96  * \sa mrpt::math::CMatrixF, RecursiveSpectralPartition
97  *
98  * \exception Throws a std::logic_error if an invalid matrix is passed.
99  */
100  static void SpectralBisection(
101  GRAPH_MATRIX& in_A, std::vector<uint32_t>& out_part1,
102  std::vector<uint32_t>& out_part2, num_t& out_cut_value,
103  bool forceSimetry = true);
104 
105  /** Performs an EXACT minimum n-Cut graph bisection, (Use
106  * CGraphPartitioner::SpectralBisection for a faster algorithm)
107  *
108  * \param in_A [IN] The weights matrix for the graph. It must be a
109  * square
110  * matrix, where element W<sub>ij</sub> is the "likelihood" between nodes
111  * "i" and "j", and typically W<sub>ii</sub> = 1.
112  * \param out_part1 [OUT] The indexs of the nodes that fall into the
113  * first
114  * group.
115  * \param out_part2 [OUT] The indexs of the nodes that fall into the
116  * second
117  * group.
118  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the
119  * range [0-2].
120  * \param forceSimetry [IN] If set to true (default) the elements
121  * W<sub>ij</sub> and W<sub>ji</sub> are replaced by
122  * 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to
123  * be simetric.
124  *
125  * \sa mrpt::math::CMatrixF, RecursiveSpectralPartition
126  *
127  * \exception Throws a std::logic_error if an invalid matrix is passed.
128  */
129  static void exactBisection(
130  GRAPH_MATRIX& in_A, std::vector<uint32_t>& out_part1,
131  std::vector<uint32_t>& out_part2, num_t& out_cut_value,
132  bool forceSimetry = true);
133 
134  /** Returns the normaliced cut of a graph, given its adjacency matrix A and
135  * a bisection:
136  */
137  static num_t nCut(
138  const GRAPH_MATRIX& in_A, const std::vector<uint32_t>& in_part1,
139  const std::vector<uint32_t>& in_part2);
140 
141 }; // End of class def.
142 
143 } // namespace graphs
144 } // namespace mrpt
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: ...
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 fast...
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
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.
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.
Finds the min-normalized-cut of a weighted undirected graph.



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: 338471620 Mon Feb 17 00:12:39 2020 +0100 at lun feb 17 00:15:10 CET 2020