Main MRPT website > C++ reference
MRPT logo
CGraphPartitioner.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 #ifndef CGRAPHPARTITIONER_H
29 #define CGRAPHPARTITIONER_H
30 
31 #include <mrpt/utils/utils_defs.h>
32 #include <mrpt/utils/CDebugOutputCapable.h>
33 #include <mrpt/math/CMatrix.h>
34 #include <mrpt/math/ops_matrices.h>
35 
36 #include <mrpt/graphs/link_pragmas.h>
37 
38 namespace mrpt
39 {
40  /** Abstract graph and tree data structures, plus generic graph algorithms
41  * \ingroup mrpt_graphs_grp
42  */
43  namespace graphs
44  {
45  using namespace mrpt::math;
46 
47  /** Algorithms for finding the min-normalized-cut of a weighted undirected graph.
48  * Two static methods are provided, one for bisection and the other for
49  * iterative N-parts partition.
50  * It is based on the Shi-Malik method, proposed for example in:<br><br>
51  * <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>
52  *
53  */
54  class GRAPHS_IMPEXP CGraphPartitioner : public mrpt::utils::CDebugOutputCapable
55  {
56  public:
57  /** Performs the spectral recursive partition into K-parts for a given graph.
58  * The default threshold for the N-cut is 1, which correspond to a cut equal
59  * of the geometric mean of self-associations of each pair of groups.
60  *
61  * \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.
62  * \param out_parts [OUT] An array of partitions, where each partition is represented as a vector of indexs for nodes.
63  * \param threshold_Ncut [IN] If it is desired to use other than the default threshold, it can be passed here.
64  * \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.
65  * \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.
66  * \param recursive [IN] Default=true, recursive algorithm for finding N partitions. Set to false to force 1 bisection as maximum.
67  * \param minSizeClusters [IN] Default=1, Minimum size of partitions to be accepted.
68  *
69  * \sa CMatrix, SpectralBisection
70  *
71  * \exception Throws a std::logic_error if an invalid matrix is passed.
72  */
73  static void RecursiveSpectralPartition(
74  CMatrix &in_A,
75  std::vector<vector_uint> &out_parts,
76  float threshold_Ncut = 1.0f,
77  bool forceSimetry = true,
78  bool useSpectralBisection = true,
79  bool recursive = true,
80  unsigned minSizeClusters = 1);
81 
82  /** Performs the spectral bisection of a graph. This method always perform
83  * the bisection, and a measure of the goodness for this cut is returned.
84  *
85  * \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.
86  * \param out_part1 [OUT] The indexs of the nodes that fall into the first group.
87  * \param out_part2 [OUT] The indexs of the nodes that fall into the second group.
88  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2].
89  * \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.
90  *
91  * \sa CMatrix, RecursiveSpectralPartition
92  *
93  * \exception Throws a std::logic_error if an invalid matrix is passed.
94  */
95  static void SpectralBisection(
96  CMatrix &in_A,
97  vector_uint &out_part1,
98  vector_uint &out_part2,
99  float &out_cut_value,
100  bool forceSimetry = true );
101 
102  /** Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm)
103  *
104  * \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.
105  * \param out_part1 [OUT] The indexs of the nodes that fall into the first group.
106  * \param out_part2 [OUT] The indexs of the nodes that fall into the second group.
107  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2].
108  * \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.
109  *
110  * \sa CMatrix, RecursiveSpectralPartition
111  *
112  * \exception Throws a std::logic_error if an invalid matrix is passed.
113  */
114  static void exactBisection(
115  CMatrix &in_A,
116  vector_uint &out_part1,
117  vector_uint &out_part2,
118  float &out_cut_value,
119  bool forceSimetry = true );
120 
121  /** Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection:
122  */
123  static float nCut(
124  const CMatrix &in_A,
125  const vector_uint &in_part1,
126  const vector_uint &in_part2 );
127 
128 
129  /** If set to true (default=false), each eigenvector computed (and the laplacian of the adj. matrix) will be saved to files "DEBUG_GRAPHPART_eigvectors_xxx" and "DEBUG_GRAPHPART_laplacian_xxx", respectively.
130  */
131  static bool DEBUG_SAVE_EIGENVECTOR_FILES;
132 
133  /** If set to true (default=false), debug info will be displayed to cout.
134  */
135  static bool VERBOSE;
136 
137  private:
138  /** Used internally when DEBUG_SAVE_EIGENVECTOR_FILES=true
139  */
140  static int debug_file_no;
141 
142  }; // End of class def.
143 
144  } // End of namespace
145 } // End of namespace
146 #endif


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013