MinimumSpanningTreeAlgorithm Class Reference

#include <ImFusion/Graph/MinimumSpanningTreeAlgorithm.h>

Algorithm to compute the Minimum Spanning Tree (MST) of an undirected cyclic graph, i.e. More...

Inheritance diagram for MinimumSpanningTreeAlgorithm:

Detailed Description

Algorithm to compute the Minimum Spanning Tree (MST) of an undirected cyclic graph, i.e.

extracts a subset of edges that connects all vertices without forming cycles and with minimum total edge weight. This implementation is based on Kruskal's Algorithm and applies to undirected graphs only.

Note

When using UserDefined weights, note that edges with lower weights will be favored in the MST computation

Public Types
enum class	WeightMode : int { EdgeLength = 0 , LabelDiameter = 1 , WeightedDiameterEdgeLength = 2 , UserDefined = 3 }
Public Types inherited from Algorithm
enum	Status {   Unknown = -1 , Success = 0 , Error = 1 , InvalidInput ,   IncompleteInput , OutOfMemoryHost , OutOfMemoryGPU , UnsupportedGPU ,   UnknownAction , AbortedByUser , User = 1000 }
	Status codes. More...

Public Member Functions
	MinimumSpanningTreeAlgorithm (Graph &graph, SharedImageSet *distanceImage=nullptr)
void	setReduction (std::function< double(const std::vector< double > &)> reduction)
	Setting the reduction only has an effect for UserDefined Mode.
Public Member Functions inherited from Algorithm
	Algorithm ()
	Default constructor will registers a single "compute" action that calls compute() and returns status().
virtual void	setProgress (Progress *progress)
	Sets a Progress interface the algorithm can use to notify observers about its computing progress.
Progress *	progress () const
	Returns the progress interface if set.
virtual int	status () const
	Indicates the status of the last call to compute().
virtual bool	survivesDataDeletion (const Data *) const
	Indicates whether the algorithm can handle (partial) deletion of the specified data, by default this checks whether the data is in the input list.
const FactoryInfo &	factoryInfo () const
	Returns the record describing how this Algorithm was instantiated by the AlgorithmFactory.
void	setFactoryInfo (const FactoryInfo &value)
	Sets the record describing how this Algorithm was instantiated by the AlgorithmFactory.
Status	runAction (const std::string &id)
	Run the action with name id if it exists.
const std::vector< Action > &	actions ()
	Get a mapping from Action id to Action as registered in this algorithm.
Public Member Functions inherited from Configurable
virtual void	configure (const Properties *p)
	Configure this object instance by de-serializing the given Properties.
virtual void	configuration (Properties *p) const
	Serialize the current object configuration into the given Properties object.
virtual void	configureDefaults ()
	Retrieve the properties of this object, replaces values with their defaults and sets it again.
void	registerParameter (ParameterBase *param)
	Register the given Parameter or SubProperty, so that it will be configured during configure()/configuration().
void	unregisterParameter (const ParameterBase *param)
	Remove the given Parameter or SubProperty from the list of registered parameters.
	Configurable (const Configurable &rhs)
	Configurable (Configurable &&rhs) noexcept
Configurable &	operator= (const Configurable &)
Configurable &	operator= (Configurable &&) noexcept

Public Attributes
Parameter< WeightMode >	p_weightMode = {"weightMode", WeightMode::EdgeLength, this}
	Determines how edge weights are computed.
Parameter< bool >	p_pruneBySegment = {"pruneBySegment", false, this}
	If enabled not single edges but segments, i.e. connected 2nd degree nodes, are removed.
Public Attributes inherited from Algorithm
Signal	signalOutputChanged
	Signal should be emitted by Algorithms when their output/result has changed.
Signal	signalParametersChanged
	Signal should be emitted by Algorithms when their parameter configuration has changed.
Public Attributes inherited from Configurable
Signal	signalParametersChanged
	Emitted whenever one of the registered Parameters' or SubPropertys' signalValueChanged signal was emitted.

Methods implementing the algorithm interface
void	compute () override
	Execute the algorithm.
OwningDataList	takeOutput () override
	Return any new Data that was created by the Algorithm during the last call to compute().
static bool	createCompatible (const DataList &data, Algorithm **a=nullptr)

Additional Inherited Members
Static Public Member Functions inherited from Algorithm
static bool	createCompatible (const DataList &data, Algorithm **a=nullptr)
	Factory function to check algorithm compatibility with input data and optionally instantiate it.
Protected Member Functions inherited from Algorithm
void	loadDefaults ()
void	registerAction (const std::string &id, const std::string &guiName, const std::function< Algorithm::Status(void)> &action)
	Register an action to be run via runAction.
template<typename D>
void	registerAction (const std::string &id, const std::string &guiName, Algorithm::Status(D::*action)(void))
	Template version of runAction that can be used with a pointer to a member function.
void	registerAction (const Action &action)
	Register an action.
Protected Attributes inherited from Algorithm
std::string	m_name
	Algorithm name.
Progress *	m_progress = nullptr
	Non-owing pointer to a progress interface. May be a nullptr.
FactoryInfo	m_factoryInfo = {}
	Record describing how this algorithm was instantiated by the AlgorithmFactory.
int	m_status = Status::Unknown
	Algorithm status after last call to compute()
std::vector< Action >	m_actions
	Map of key given by the id of the action, of the available actions of this algorithm.
Protected Attributes inherited from Configurable
std::vector< Param >	m_params
	List of all registered Parameter and SubProperty instances.

Member Enumeration Documentation

WeightMode

enum class WeightMode : int

strong

Enumerator
EdgeLength	Use edge length as the weight. Prefers longer paths.
LabelDiameter	Use the inverse of the diameter of the associated label map. Prefers thicker paths.
WeightedDiameterEdgeLength	Uses a normalized combination of edge length and inverse diameter. Balances between path length and thickness.
UserDefined	Use pre-assigned edge weights. Allows for custom user-defined weighting.

Member Function Documentation

compute()

void compute ( )

overridevirtual

Execute the algorithm.

Implements Algorithm.

takeOutput()

OwningDataList takeOutput ( )

overridevirtual

Return any new Data that was created by the Algorithm during the last call to compute().

The default implementation will return an empty list.

Note

Since ownership of the data is transferred, you can call this method only once between calls to compute().

Reimplemented from Algorithm.

---

The documentation for this class was generated from the following file:

• ImFusion/Graph/MinimumSpanningTreeAlgorithm.h