Main MRPT website > C++ reference
MRPT logo

CGraphPartitioner.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 #ifndef CGRAPHPARTITIONER_H
00029 #define CGRAPHPARTITIONER_H
00030 
00031 #include <mrpt/utils/utils_defs.h>
00032 #include <mrpt/utils/CDebugOutputCapable.h>
00033 #include <mrpt/math/CMatrix.h>
00034 #include <mrpt/math/ops_matrices.h>
00035 
00036 namespace mrpt
00037 {
00038 namespace math
00039 {
00040         /** Algorithms for finding the min-normalized-cut of a weighted undirected graph.
00041          *    Two static methods are provided, one for bisection and the other for
00042          *      iterative N-parts partition.
00043          *  It is based on the Shi-Malik method, proposed for example in:<br><br>
00044          *  <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>
00045          *
00046          */
00047         class BASE_IMPEXP CGraphPartitioner : public mrpt::utils::CDebugOutputCapable
00048         {
00049         public:
00050                 /** Performs the spectral recursive partition into K-parts for a given graph.
00051                  *   The default threshold for the N-cut is 1, which correspond to a cut equal
00052                  *   of the geometric mean of self-associations of each pair of groups.
00053                  *
00054                  * \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.
00055                  * \param out_parts              [OUT] An array of partitions, where each partition is represented as a vector of indexs for nodes.
00056                  * \param threshold_Ncut [IN] If it is desired to use other than the default threshold, it can be passed here.
00057                  * \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.
00058                  * \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.
00059                  * \param recursive [IN] Default=true, recursive algorithm for finding N partitions. Set to false to force 1 bisection as maximum.
00060                  * \param minSizeClusters [IN] Default=1, Minimum size of partitions to be accepted.
00061                  *
00062                  * \sa CMatrix, SpectralBisection
00063                  *
00064                  * \exception Throws a std::logic_error if an invalid matrix is passed.
00065                  */
00066                 static void  RecursiveSpectralPartition(
00067                   CMatrix                                       &in_A,
00068                   std::vector<vector_uint>      &out_parts,
00069                   float                                         threshold_Ncut = 1.0f,
00070                   bool                                          forceSimetry = true,
00071                   bool                                          useSpectralBisection = true,
00072                   bool                                          recursive = true,
00073                   unsigned                                      minSizeClusters = 1);
00074 
00075                 /** Performs the spectral bisection of a graph. This method always perform
00076                  *   the bisection, and a measure of the goodness for this cut is returned.
00077                  *
00078                  * \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.
00079                  * \param out_part1             [OUT] The indexs of the nodes that fall into the first group.
00080                  * \param out_part2             [OUT] The indexs of the nodes that fall into the second group.
00081                  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2].
00082                  * \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.
00083                  *
00084                  * \sa CMatrix, RecursiveSpectralPartition
00085                  *
00086                  * \exception Throws a std::logic_error if an invalid matrix is passed.
00087                  */
00088                 static void  SpectralBisection(
00089                                                         CMatrix                                 &in_A,
00090                                                         vector_uint                             &out_part1,
00091                                                         vector_uint                             &out_part2,
00092                                                         float                                   &out_cut_value,
00093                                                         bool                                    forceSimetry = true );
00094 
00095                 /** Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm)
00096                  *
00097                  * \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.
00098                  * \param out_part1             [OUT] The indexs of the nodes that fall into the first group.
00099                  * \param out_part2             [OUT] The indexs of the nodes that fall into the second group.
00100                  * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2].
00101                  * \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.
00102                  *
00103                  * \sa CMatrix, RecursiveSpectralPartition
00104                  *
00105                  * \exception Throws a std::logic_error if an invalid matrix is passed.
00106                  */
00107                 static void  exactBisection(
00108                                                         CMatrix                 &in_A,
00109                                                         vector_uint             &out_part1,
00110                                                         vector_uint             &out_part2,
00111                                                         float                   &out_cut_value,
00112                                                         bool                    forceSimetry = true );
00113 
00114                 /** Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection:
00115                   */
00116                 static float  nCut(
00117                                                         const CMatrix                   &in_A,
00118                                                         const vector_uint               &in_part1,
00119                                                         const vector_uint               &in_part2 );
00120 
00121 
00122                         /** 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.
00123                           */
00124             static bool DEBUG_SAVE_EIGENVECTOR_FILES;
00125 
00126                         /** If set to true (default=false), debug info will be displayed to cout.
00127                           */
00128             static bool VERBOSE;
00129 
00130         private:
00131             /** Used internally when DEBUG_SAVE_EIGENVECTOR_FILES=true
00132               */
00133             static int debug_file_no;
00134 
00135         }; // End of class def.
00136 
00137         } // End of namespace
00138 } // End of namespace
00139 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011