Detailed Description

template<class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
class mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >

Algorithms for finding the min-normalized-cut of a weighted undirected graph.

Two methods are provided, one for bisection and the other for iterative N-parts partition. It is an implementation of the Shi-Malik method proposed in:

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.

Template Parameters

GRAPH_MATRIX	The type of square matrices used to represent the connectivity in a graph (e.g. mrpt::math::CMatrix)
num_t	The type of matrix elements, thresholds, etc. (typ: float or double). Defaults to the type of matrix elements.

Note: Prior to MRPT 1.0.0 this class wasn't a template and provided static variables for debugging, which were removed since that version.

Definition at line 41 of file CGraphPartitioner.h.

#include <mrpt/graphs/CGraphPartitioner.h>

Inheritance diagram for mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >:

Static Public Member Functions
static void	RecursiveSpectralPartition (GRAPH_MATRIX &in_A, std::vector< std::vector< uint32_t >> &out_parts, num_t threshold_Ncut=1, bool forceSimetry=true, bool useSpectralBisection=true, bool recursive=true, unsigned minSizeClusters=1, const bool verbose=false)
	Performs the spectral recursive partition into K-parts for a given graph. More...

static void	SpectralBisection (GRAPH_MATRIX &in_A, std::vector< uint32_t > &out_part1, std::vector< uint32_t > &out_part2, num_t &out_cut_value, bool forceSimetry=true)
	Performs the spectral bisection of a graph. More...

static void	exactBisection (GRAPH_MATRIX &in_A, std::vector< uint32_t > &out_part1, std::vector< uint32_t > &out_part2, num_t &out_cut_value, bool forceSimetry=true)
	Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm) More...

static num_t	nCut (const GRAPH_MATRIX &in_A, const std::vector< uint32_t > &in_part1, const std::vector< uint32_t > &in_part2)
	Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection: More...

static std::array< mrpt::system::TConsoleColor, NUMBER_OF_VERBOSITY_LEVELS > &	logging_levels_to_colors ()
	Map from VerbosityLevels to their corresponding mrpt::system::TConsoleColor. More...

static std::array< std::string, NUMBER_OF_VERBOSITY_LEVELS > &	logging_levels_to_names ()
	Map from VerbosityLevels to their corresponding names. More...

Protected Attributes
VerbosityLevel	m_min_verbosity_level
	Provided messages with VerbosityLevel smaller than this value shall be ignored. More...

Logging methods
bool	logging_enable_console_output
	[Default=true] Set it to false in case you don't want the logged messages to be dumped to the output automatically. More...

bool	logging_enable_keep_record
	[Default=false] Enables storing all messages into an internal list. More...

void	logStr (const VerbosityLevel level, const std::string &msg_str) const
	Main method to add the specified message string to the logger. More...

void	logFmt (const VerbosityLevel level, const char *fmt,...) const MRPT_printf_format_check(3
	Alternative logging method, which mimics the printf behavior. More...

void void	logCond (const VerbosityLevel level, bool cond, const std::string &msg_str) const
	Log the given message only if the condition is satisfied. More...

void	setLoggerName (const std::string &name)
	Set the name of the COutputLogger instance. More...

std::string	getLoggerName () const
	Return the name of the COutputLogger instance. More...

void	setMinLoggingLevel (const VerbosityLevel level)
	Set the minimum logging level for which the incoming logs are going to be taken into account. More...

void	setVerbosityLevel (const VerbosityLevel level)
	alias of setMinLoggingLevel() More...

VerbosityLevel	getMinLoggingLevel () const

bool	isLoggingLevelVisible (VerbosityLevel level) const

void	getLogAsString (std::string &log_contents) const
	Fill the provided string with the contents of the logger's history in std::string representation. More...

std::string	getLogAsString () const
	Get the history of COutputLogger instance in a string representation. More...

void	writeLogToFile (const std::string *fname_in=NULL) const
	Write the contents of the COutputLogger instance to an external file. More...

void	dumpLogToConsole () const
	Dump the current contents of the COutputLogger instance in the terminal window. More...

std::string	getLoggerLastMsg () const
	Return the last Tmsg instance registered in the logger history. More...

void	getLoggerLastMsg (std::string &msg_str) const
	Fill inputtted string with the contents of the last message in history. More...

void	loggerReset ()
	Reset the contents of the logger instance. More...

void	logRegisterCallback (output_logger_callback_t userFunc)

bool	logDeregisterCallback (output_logger_callback_t userFunc)

Member Function Documentation

◆ dumpLogToConsole()

void COutputLogger::dumpLogToConsole ( ) const

inherited

Dump the current contents of the COutputLogger instance in the terminal window.

See also: writeToFile

Definition at line 190 of file COutputLogger.cpp.

◆ exactBisection()

template<class GRAPH_MATRIX , typename num_t >

void mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::exactBisection	(	GRAPH_MATRIX &	in_A,
		std::vector< uint32_t > &	out_part1,
		std::vector< uint32_t > &	out_part2,
		num_t &	out_cut_value,
		bool	forceSimetry = `true`
	)

static

Performs an EXACT minimum n-Cut graph bisection, (Use CGraphPartitioner::SpectralBisection for a faster algorithm)

Parameters

in_A	[IN] The weights matrix for the graph. It must be a square matrix, where element W_ij is the "likelihood" between nodes "i" and "j", and typically W_ii = 1.
out_part1	[OUT] The indexs of the nodes that fall into the first group.
out_part2	[OUT] The indexs of the nodes that fall into the second group.
out_cut_value	[OUT] The N-cut value for the proposed cut, in the range [0-2].
forceSimetry	[IN] If set to true (default) the elements W_ij and W_ji are replaced by 0.5*(W_ij+W_ji). Set to false if matrix is known to be simetric.

See also: mrpt::math::CMatrix, RecursiveSpectralPartition

Exceptions

Throws a std::logic_error if an invalid matrix is passed.

Definition at line 260 of file CGraphPartitioner_impl.h.

References ASSERT_, and THROW_EXCEPTION.

◆ getLogAsString() [1/2]

void COutputLogger::getLogAsString ( std::string & log_contents ) const

inherited

Fill the provided string with the contents of the logger's history in std::string representation.

Definition at line 154 of file COutputLogger.cpp.

◆ getLogAsString() [2/2]

std::string COutputLogger::getLogAsString ( ) const

inherited

Get the history of COutputLogger instance in a string representation.

Definition at line 159 of file COutputLogger.cpp.

Referenced by mrpt::graphslam::deciders::CICPCriteriaNRD< GRAPH_T >::getDescriptiveReport().

◆ getLoggerLastMsg() [1/2]

std::string COutputLogger::getLoggerLastMsg ( ) const

inherited

Return the last Tmsg instance registered in the logger history.

Definition at line 195 of file COutputLogger.cpp.

References mrpt::system::COutputLogger::TMsg::getAsString().

◆ getLoggerLastMsg() [2/2]

void COutputLogger::getLoggerLastMsg ( std::string & msg_str ) const

inherited

Fill inputtted string with the contents of the last message in history.

Definition at line 201 of file COutputLogger.cpp.

◆ getLoggerName()

std::string COutputLogger::getLoggerName ( ) const

inherited

Return the name of the COutputLogger instance.

See also: setLoggerName

Definition at line 143 of file COutputLogger.cpp.

◆ getMinLoggingLevel()

VerbosityLevel mrpt::system::COutputLogger::getMinLoggingLevel ( ) const

inlineinherited

See also: setMinLoggingLevel

Definition at line 200 of file system/COutputLogger.h.

References mrpt::system::COutputLogger::m_min_verbosity_level.

Referenced by mrpt::maps::CRandomFieldGridMap2D::isEnabledVerbose(), and mrpt::slam::CMetricMapBuilderRBPF::processActionObservation().

◆ isLoggingLevelVisible()

bool mrpt::system::COutputLogger::isLoggingLevelVisible ( VerbosityLevel level ) const

inlineinherited

Definition at line 201 of file system/COutputLogger.h.

References mrpt::system::COutputLogger::m_min_verbosity_level.

Referenced by mrpt::slam::CMetricMapBuilderRBPF::processActionObservation(), and mrpt::system::COutputLoggerStreamWrapper::~COutputLoggerStreamWrapper().

◆ logCond()

void COutputLogger::logCond	(	const VerbosityLevel	level,
		bool	cond,
		const std::string &	msg_str
	)		const

inherited

Log the given message only if the condition is satisfied.

See also: log, logFmt

Definition at line 131 of file COutputLogger.cpp.

◆ logDeregisterCallback()

bool COutputLogger::logDeregisterCallback ( output_logger_callback_t userFunc )

inherited

Returns: true if an entry was found and deleted.

Definition at line 290 of file COutputLogger.cpp.

References getAddress(), and mrpt::system::COutputLogger::m_listCallbacks.

◆ logFmt()

void COutputLogger::logFmt	(	const VerbosityLevel	level,
		const char *	fmt,
			...
	)		const

inherited

Alternative logging method, which mimics the printf behavior.

Handy for not having to first use mrpt::format to pass a std::string message to logStr

// instead of:
logStr(mrpt::format("Today is the %d of %s, %d", 15, "July", 2016));
// one can use:
logFmt("Today is the %d of %s, %d", 15, "July", 2016);

See also: logStr, logCond

Definition at line 91 of file COutputLogger.cpp.

Referenced by mrpt::graphslam::deciders::CICPCriteriaNRD< GRAPH_T >::CICPCriteriaNRD(), mrpt::hmtslam::CTopLCDetector_GridMatching::computeTopologicalObservationModel(), CGraphSlamHandler< GRAPH_T >::execute(), mrpt::math::CLevenbergMarquardtTempl< VECTORTYPE, USERPARAM >::execute(), CGraphSlamHandler< GRAPH_T >::initOutputDir(), CGraphSlamHandler< GRAPH_T >::initVisualization(), mrpt::nav::CNavigatorManualSequence::navigationStep(), mrpt::nav::CAbstractNavigator::performNavigationStepNavigating(), CGraphSlamHandler< GRAPH_T >::readConfigFname(), CGraphSlamHandler< GRAPH_T >::saveResults(), CGraphSlamHandler< GRAPH_T >::setResultsDirName(), mrpt::nav::CReactiveNavigationSystem::STEP1_InitPTGs(), and CGraphSlamHandler< GRAPH_T >::~CGraphSlamHandler().

◆ loggerReset()

void COutputLogger::loggerReset ( )

inherited

Reset the contents of the logger instance.

Called upon construction.

Definition at line 206 of file COutputLogger.cpp.

References mrpt::system::LVL_INFO.

◆ logging_levels_to_colors()

std::array< mrpt::system::TConsoleColor, NUMBER_OF_VERBOSITY_LEVELS > & COutputLogger::logging_levels_to_colors ( )

staticinherited

Map from VerbosityLevels to their corresponding mrpt::system::TConsoleColor.

Handy for coloring the input based on the verbosity of the message

Definition at line 47 of file COutputLogger.cpp.

References logging_levels_to_colors.

Referenced by mrpt::system::COutputLogger::TMsg::dumpToConsole().

◆ logging_levels_to_names()

std::array< std::string, NUMBER_OF_VERBOSITY_LEVELS > & COutputLogger::logging_levels_to_names ( )

staticinherited

Map from VerbosityLevels to their corresponding names.

Handy for printing the current message VerbosityLevel along with the actual content

Definition at line 60 of file COutputLogger.cpp.

References logging_levels_to_names.

Referenced by mrpt::system::COutputLogger::TMsg::getAsString().

◆ logRegisterCallback()

void COutputLogger::logRegisterCallback ( output_logger_callback_t userFunc )

inherited

Definition at line 277 of file COutputLogger.cpp.

References mrpt::system::COutputLogger::m_listCallbacks.

◆ logStr()

void COutputLogger::logStr	(	const VerbosityLevel	level,
		const std::string &	msg_str
	)		const

inherited

Main method to add the specified message string to the logger.

See also: logCond, logFmt

Definition at line 72 of file COutputLogger.cpp.

References mrpt::system::COutputLogger::TMsg::body, mrpt::system::COutputLogger::TMsg::dumpToConsole(), mrpt::system::COutputLogger::TMsg::level, mrpt::system::COutputLogger::TMsg::name, and mrpt::system::COutputLogger::TMsg::timestamp.

Referenced by mrpt::slam::PF_implementation< mrpt::math::TPose3D, CMonteCarloLocalization3D, mrpt::bayes::particle_storage_mode::VALUE >::PF_SLAM_implementation_pfAuxiliaryPFStandardAndOptimal(), mrpt::nav::CReactiveNavigationSystem::STEP1_InitPTGs(), and mrpt::system::COutputLoggerStreamWrapper::~COutputLoggerStreamWrapper().

◆ nCut()

template<class GRAPH_MATRIX , typename num_t >

num_t mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::nCut	(	const GRAPH_MATRIX &	in_A,
		const std::vector< uint32_t > &	in_part1,
		const std::vector< uint32_t > &	in_part2
	)

static

Returns the normaliced cut of a graph, given its adjacency matrix A and a bisection:

Definition at line 223 of file CGraphPartitioner_impl.h.

◆ RecursiveSpectralPartition()

template<class GRAPH_MATRIX , typename num_t >

void mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::RecursiveSpectralPartition	(	GRAPH_MATRIX &	in_A,
		std::vector< std::vector< uint32_t >> &	out_parts,
		num_t	threshold_Ncut = `1`,
		bool	forceSimetry = `true`,
		bool	useSpectralBisection = `true`,
		bool	recursive = `true`,
		unsigned	minSizeClusters = `1`,
		const bool	verbose = `false`
	)

static

Performs the spectral recursive partition into K-parts for a given graph.

The default threshold for the N-cut is 1, which correspond to a cut equal of the geometric mean of self-associations of each pair of groups.

Parameters

in_A	[IN] The weights matrix for the graph. It must be a square matrix, where element W_ij is the "likelihood" between nodes "i" and "j", and typically W_ii = 1.
out_parts	[OUT] An array of partitions, where each partition is represented as a vector of indexs for nodes.
threshold_Ncut	[IN] If it is desired to use other than the default threshold, it can be passed here.
forceSimetry	[IN] If set to true (default) the elements W_ij and W_ji are replaced by 0.5*(W_ij+W_ji). Set to false if matrix is known to be simetric.
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.
recursive	[IN] Default=true, recursive algorithm for finding N partitions. Set to false to force 1 bisection as maximum.
minSizeClusters	[IN] Default=1, Minimum size of partitions to be accepted.

See also: mrpt::math::CMatrix, SpectralBisection

Exceptions

Throws a std::logic_error if an invalid matrix is passed.

Definition at line 96 of file CGraphPartitioner_impl.h.

References mrpt::format(), MRPT_END, MRPT_START, and THROW_EXCEPTION.

Referenced by mrpt::pbmap::SemanticClustering::evalPartition().

◆ setLoggerName()

void COutputLogger::setLoggerName ( const std::string & name )

inherited

Set the name of the COutputLogger instance.

See also: getLoggerName

Definition at line 138 of file COutputLogger.cpp.

Referenced by mrpt::slam::CMetricMapBuilderICP::CMetricMapBuilderICP(), mrpt::slam::CMetricMapBuilderRBPF::CMetricMapBuilderRBPF(), mrpt::slam::CMonteCarloLocalization2D::CMonteCarloLocalization2D(), mrpt::slam::CMonteCarloLocalization3D::CMonteCarloLocalization3D(), and mrpt::graphslam::CWindowManager::initCWindowManager().

◆ setMinLoggingLevel()

void COutputLogger::setMinLoggingLevel ( const VerbosityLevel level )

inherited

Set the minimum logging level for which the incoming logs are going to be taken into account.

String messages with specified VerbosityLevel smaller than the min, will not be outputted to the screen and neither will a record of them be stored in by the COutputLogger instance

Definition at line 144 of file COutputLogger.cpp.

Referenced by mrpt::maps::CRandomFieldGridMap2D::enableVerbose(), mrpt::math::CLevenbergMarquardtTempl< VECTORTYPE, USERPARAM >::execute(), mrpt::hwdrivers::CHokuyoURG::initialize(), and mrpt::graphslam::deciders::CICPCriteriaNRD< GRAPH_T >::loadParams().

◆ setVerbosityLevel()

void COutputLogger::setVerbosityLevel ( const VerbosityLevel level )

inherited

alias of setMinLoggingLevel()

Definition at line 149 of file COutputLogger.cpp.

Referenced by mrpt::nav::CAbstractNavigator::CAbstractNavigator(), mrpt::slam::CMetricMapBuilderRBPF::CMetricMapBuilderRBPF(), mrpt::comms::CServerTCPSocket::CServerTCPSocket(), mrpt::slam::CMetricMapBuilderRBPF::processActionObservation(), and mrpt::math::ransac_detect_2D_lines().

◆ SpectralBisection()

template<class GRAPH_MATRIX , typename num_t >

void mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >::SpectralBisection	(	GRAPH_MATRIX &	in_A,
		std::vector< uint32_t > &	out_part1,
		std::vector< uint32_t > &	out_part2,
		num_t &	out_cut_value,
		bool	forceSimetry = `true`
	)

static

Performs the spectral bisection of a graph.

This method always perform the bisection, and a measure of the goodness for this cut is returned.

Parameters

in_A	[IN] The weights matrix for the graph. It must be a square matrix, where element W_ij is the "likelihood" between nodes "i" and "j", and typically W_ii = 1.
out_part1	[OUT] The indexs of the nodes that fall into the first group.
out_part2	[OUT] The indexs of the nodes that fall into the second group.
out_cut_value	[OUT] The N-cut value for the proposed cut, in the range [0-2].
forceSimetry	[IN] If set to true (default) the elements W_ij and W_ji are replaced by 0.5*(W_ij+W_ji). Set to false if matrix is known to be simetric.

See also: mrpt::math::CMatrix, RecursiveSpectralPartition

Exceptions

Throws a std::logic_error if an invalid matrix is passed.

Definition at line 20 of file CGraphPartitioner_impl.h.

References eigenValues(), eigenVectors(), mean(), and THROW_EXCEPTION.

◆ writeLogToFile()

void COutputLogger::writeLogToFile ( const std::string * fname_in = NULL ) const

inherited

Write the contents of the COutputLogger instance to an external file.

Upon call to this method, COutputLogger dumps the contents of all the logged commands so far to the specified external file. By default the filename is set to ${LOGGERNAME}.log except if the fname parameter is provided

See also: dumpToConsole, getAsString

Definition at line 165 of file COutputLogger.cpp.

References ASSERTMSG_, and mrpt::format().

Member Data Documentation

◆ logging_enable_console_output

bool mrpt::system::COutputLogger::logging_enable_console_output

inherited

[Default=true] Set it to false in case you don't want the logged messages to be dumped to the output automatically.

Definition at line 239 of file system/COutputLogger.h.

◆ logging_enable_keep_record

bool mrpt::system::COutputLogger::logging_enable_keep_record

inherited

[Default=false] Enables storing all messages into an internal list.

See also: writeLogToFile, getLogAsString

Definition at line 242 of file system/COutputLogger.h.

◆ m_min_verbosity_level

VerbosityLevel mrpt::system::COutputLogger::m_min_verbosity_level

protectedinherited

Provided messages with VerbosityLevel smaller than this value shall be ignored.

Definition at line 252 of file system/COutputLogger.h.

Referenced by mrpt::system::COutputLogger::getMinLoggingLevel(), and mrpt::system::COutputLogger::isLoggingLevelVisible().

Detailed Description

template<class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar> class mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >

Static Public Member Functions

Protected Attributes

Logging methods

Member Function Documentation

◆ dumpLogToConsole()

◆ exactBisection()

◆ getLogAsString() [1/2]

◆ getLogAsString() [2/2]

◆ getLoggerLastMsg() [1/2]

◆ getLoggerLastMsg() [2/2]

◆ getLoggerName()

◆ getMinLoggingLevel()

◆ isLoggingLevelVisible()

◆ logCond()

◆ logDeregisterCallback()

◆ logFmt()

◆ loggerReset()

◆ logging_levels_to_colors()

◆ logging_levels_to_names()

◆ logRegisterCallback()

◆ logStr()

◆ nCut()

◆ RecursiveSpectralPartition()

◆ setLoggerName()

◆ setMinLoggingLevel()

◆ setVerbosityLevel()

◆ SpectralBisection()

◆ writeLogToFile()

Member Data Documentation

◆ logging_enable_console_output

◆ logging_enable_keep_record

◆ m_min_verbosity_level

template<class GRAPH_MATRIX, typename num_t = typename GRAPH_MATRIX::Scalar>
class mrpt::graphs::CGraphPartitioner< GRAPH_MATRIX, num_t >