00001 /* +---------------------------------------------------------------------------+ 00002 | The Mobile Robot Programming Toolkit (MRPT) C++ library | 00003 | | 00004 | http://mrpt.sourceforge.net/ | 00005 | | 00006 | Copyright (C) 2005-2009 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 00035 namespace mrpt 00036 { 00037 namespace math 00038 { 00039 /** Algorithms for finding the min-normalized-cut of a weighted undirected graph. 00040 * Two static methods are provided, one for bisection and the other for 00041 * iterative N-parts partition. 00042 * It is based on the Shi-Malik method, proposed for example in:<br><br> 00043 * <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> 00044 * 00045 */ 00046 class MRPTDLLIMPEXP CGraphPartitioner : public mrpt::utils::CDebugOutputCapable 00047 { 00048 public: 00049 /** Performs the spectral recursive partition into K-parts for a given graph. 00050 * The default threshold for the N-cut is 1, which correspond to a cut equal 00051 * of the geometric mean of self-associations of each pair of groups. 00052 * 00053 * \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. 00054 * \param out_parts [OUT] An array of partitions, where each partition is represented as a vector of indexs for nodes. 00055 * \param threshold_Ncut [IN] If it is desired to use other than the default threshold, it can be passed here. 00056 * \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. 00057 * \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. 00058 * \param recursive [IN] Default=true, recursive algorithm for finding N partitions. Set to false to force 1 bisection as maximum. 00059 * \param minSizeClusters [IN] Default=1, Minimum size of partitions to be accepted. 00060 * 00061 * \sa CMatrix, SpectralBisection 00062 * 00063 * \exception Throws a std::logic_error if an invalid matrix is passed. 00064 */ 00065 static void RecursiveSpectralPartition( 00066 CMatrix &in_A, 00067 std::vector<vector_uint> &out_parts, 00068 float threshold_Ncut = 1.0f, 00069 bool forceSimetry = true, 00070 bool useSpectralBisection = true, 00071 bool recursive = true, 00072 unsigned minSizeClusters = 1); 00073 00074 /** Performs the spectral bisection of a graph. This method always perform 00075 * the bisection, and a measure of the goodness for this cut is returned. 00076 * 00077 * \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. 00078 * \param out_part1 [OUT] The indexs of the nodes that fall into the first group. 00079 * \param out_part2 [OUT] The indexs of the nodes that fall into the second group. 00080 * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2]. 00081 * \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. 00082 * 00083 * \sa CMatrix, RecursiveSpectralPartition 00084 * 00085 * \exception Throws a std::logic_error if an invalid matrix is passed. 00086 */ 00087 static void SpectralBisection( 00088 CMatrix &in_A, 00089 vector_uint &out_part1, 00090 vector_uint &out_part2, 00091 float &out_cut_value, 00092 bool forceSimetry = true ); 00093 00094 /** Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm) 00095 * 00096 * \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. 00097 * \param out_part1 [OUT] The indexs of the nodes that fall into the first group. 00098 * \param out_part2 [OUT] The indexs of the nodes that fall into the second group. 00099 * \param out_cut_value [OUT] The N-cut value for the proposed cut, in the range [0-2]. 00100 * \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. 00101 * 00102 * \sa CMatrix, RecursiveSpectralPartition 00103 * 00104 * \exception Throws a std::logic_error if an invalid matrix is passed. 00105 */ 00106 static void exactBisection( 00107 CMatrix &in_A, 00108 vector_uint &out_part1, 00109 vector_uint &out_part2, 00110 float &out_cut_value, 00111 bool forceSimetry = true ); 00112 00113 /** Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection: 00114 */ 00115 static float nCut( 00116 const CMatrix &in_A, 00117 const vector_uint &in_part1, 00118 const vector_uint &in_part2 ); 00119 00120 00121 /** 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. 00122 */ 00123 static bool DEBUG_SAVE_EIGENVECTOR_FILES; 00124 00125 /** If set to true (default=false), debug info will be displayed to cout. 00126 */ 00127 static bool VERBOSE; 00128 00129 private: 00130 /** Used internally when DEBUG_SAVE_EIGENVECTOR_FILES=true 00131 */ 00132 static int debug_file_no; 00133 00134 }; // End of class def. 00135 00136 } // End of namespace 00137 } // End of namespace 00138 #endif
Page generated by Doxygen 1.5.7.1 for MRPT 0.7.1 SVN: at Mon Aug 17 23:10:56 EDT 2009 |