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