MRPT  1.9.9
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-2018, 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 
13 #include <mrpt/math/CMatrix.h>
14 #include <mrpt/math/ops_matrices.h>
15 
16 namespace mrpt
17 {
18 /** Abstract graph and tree data structures, plus generic graph algorithms
19  * \ingroup mrpt_graphs_grp
20  */
21 namespace graphs
22 {
23 /** Algorithms for finding the min-normalized-cut of a weighted undirected
24  * 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
29  * Transactions on Pattern Analysis and Machine Intelligence, vol.22, no.8, pp.
30  * 888-905, Aug. 2000.</code><br>
31  *
32  * \tparam GRAPH_MATRIX The type of square matrices used to represent the
33  * connectivity in a graph (e.g. mrpt::math::CMatrix)
34  * \tparam num_t The type of matrix elements, thresholds, etc. (typ: float or
35  * double). Defaults to the type of matrix elements.
36  *
37  * \note Prior to MRPT 1.0.0 this class wasn't a template and provided static
38  * variables for debugging, which were removed since that version.
39  */
40 template <class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
42 {
43  public:
44  /** Performs the spectral recursive partition into K-parts for a given
45  * graph.
46  * The default threshold for the N-cut is 1, which correspond to a cut
47  * equal
48  * of the geometric mean of self-associations of each pair of groups.
49  *
50  * \param in_A [IN] The weights matrix for the graph. It must be a
51  * square
52  * matrix, where element W<sub>ij</sub> is the "likelihood" between nodes
53  * "i" and "j", and typically W<sub>ii</sub> = 1.
54  * \param out_parts [OUT] An array of partitions, where each partition
55  * is
56  * represented as a vector of indexs for nodes.
57  * \param threshold_Ncut [IN] If it is desired to use other than the default
58  * threshold, it can be passed here.
59  * \param forceSimetry [IN] If set to true (default) the elements
60  * W<sub>ij</sub> and W<sub>ji</sub> are replaced by
61  * 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to
62  * be simetric.
63  * \param useSpectralBisection [IN] If set to true (default) a quick
64  * spectral bisection will be used. If set to false, a brute force, exact
65  * finding of the min-cut is performed.
66  * \param recursive [IN] Default=true, recursive algorithm for finding N
67  * partitions. Set to false to force 1 bisection as maximum.
68  * \param minSizeClusters [IN] Default=1, Minimum size of partitions to be
69  * accepted.
70  *
71  * \sa mrpt::math::CMatrix, SpectralBisection
72  *
73  * \exception Throws a std::logic_error if an invalid matrix is passed.
74  */
75  static void RecursiveSpectralPartition(
76  GRAPH_MATRIX& in_A, std::vector<std::vector<uint32_t>>& out_parts,
77  num_t threshold_Ncut = 1, bool forceSimetry = true,
78  bool useSpectralBisection = true, bool recursive = true,
79  unsigned minSizeClusters = 1, const bool verbose = false);
80 
81  /** Performs the spectral bisection of a graph. This method always perform
82  * the bisection, and a measure of the goodness for this cut is returned.
83  *
84  * \param in_A [IN] The weights matrix for the graph. It must be a
85  * square
86  * matrix, where element W<sub>ij</sub> is the "likelihood" between nodes
87  * "i" and "j", and typically W<sub>ii</sub> = 1.
88  * \param out_part1 [OUT] The indexs of the nodes that fall into the
89  * first
90  * group.
91  * \param out_part2 [OUT] The indexs of the nodes that fall into the
92  * second
93  * group.
94  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the
95  * range [0-2].
96  * \param forceSimetry [IN] If set to true (default) the elements
97  * W<sub>ij</sub> and W<sub>ji</sub> are replaced by
98  * 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to
99  * be simetric.
100  *
101  * \sa mrpt::math::CMatrix, RecursiveSpectralPartition
102  *
103  * \exception Throws a std::logic_error if an invalid matrix is passed.
104  */
105  static void SpectralBisection(
106  GRAPH_MATRIX& in_A, std::vector<uint32_t>& out_part1,
107  std::vector<uint32_t>& out_part2, num_t& out_cut_value,
108  bool forceSimetry = true);
109 
110  /** Performs an EXACT minimum n-Cut graph bisection, (Use
111  * CGraphPartitioner::SpectralBisection for a faster algorithm)
112  *
113  * \param in_A [IN] The weights matrix for the graph. It must be a
114  * square
115  * matrix, where element W<sub>ij</sub> is the "likelihood" between nodes
116  * "i" and "j", and typically W<sub>ii</sub> = 1.
117  * \param out_part1 [OUT] The indexs of the nodes that fall into the
118  * first
119  * group.
120  * \param out_part2 [OUT] The indexs of the nodes that fall into the
121  * second
122  * group.
123  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the
124  * range [0-2].
125  * \param forceSimetry [IN] If set to true (default) the elements
126  * W<sub>ij</sub> and W<sub>ji</sub> are replaced by
127  * 0.5*(W<sub>ij</sub>+W<sub>ji</sub>). Set to false if matrix is known to
128  * be simetric.
129  *
130  * \sa mrpt::math::CMatrix, RecursiveSpectralPartition
131  *
132  * \exception Throws a std::logic_error if an invalid matrix is passed.
133  */
134  static void exactBisection(
135  GRAPH_MATRIX& in_A, std::vector<uint32_t>& out_part1,
136  std::vector<uint32_t>& out_part2, num_t& out_cut_value,
137  bool forceSimetry = true);
138 
139  /** Returns the normaliced cut of a graph, given its adjacency matrix A and
140  * a bisection:
141  */
142  static num_t nCut(
143  const GRAPH_MATRIX& in_A, const std::vector<uint32_t>& in_part1,
144  const std::vector<uint32_t>& in_part2);
145 
146 }; // End of class def.
147 
148 } // End of namespace
149 } // End of namespace
150 
151 // Template implementation:
152 #include "CGraphPartitioner_impl.h"
153 
154 #endif
This file implements miscelaneous matrix and matrix/vector operations, and internal functions in mrpt...
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.
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: ...
Versatile class for consistent logging and management of output messages.
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
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...
Algorithms for finding the min-normalized-cut of a weighted undirected graph.
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.



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: 7d5e6d718 Fri Aug 24 01:51:28 2018 +0200 at lun nov 2 08:35:50 CET 2020