Main MRPT website > C++ reference for MRPT 1.5.7
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-2017, 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 
12 #include <mrpt/utils/utils_defs.h>
14 #include <mrpt/math/CMatrix.h>
15 #include <mrpt/math/ops_matrices.h>
16 
17 namespace 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>
36  class CGraphPartitioner : public mrpt::utils::COutputLogger
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  */
55  static void RecursiveSpectralPartition(
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:
117 #include "CGraphPartitioner_impl.h"
118 
119 #endif
std::vector< uint32_t > vector_uint
Definition: types_simple.h:28
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.
This file implements miscelaneous matrix and matrix/vector operations, and internal functions in mrpt...
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.
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
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...
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: ...
Algorithms for finding the min-normalized-cut of a weighted undirected graph.



Page generated by Doxygen 1.8.14 for MRPT 1.5.7 Git: 5902e14cc Wed Apr 24 15:04:01 2019 +0200 at lun oct 28 01:39:17 CET 2019