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.2 for MRPT 0.9.4 SVN: at Mon Jan 10 22:30:30 UTC 2011 |