lti::minimumSpanningTree< K, V, Distantor > Class Template Reference

This class computes minimum spanning trees. More...

#include <ltiMinimumSpanningTree.h>

Inheritance diagram for lti::minimumSpanningTree< K, V, Distantor >:

[legend]

Collaboration diagram for lti::minimumSpanningTree< K, V, Distantor >:

[legend]

List of all members.

Classes
class	parameters
	the parameters for the class minimumSpanningTree More...
Public Types
typedef Distantor::distance_type	distance_type
Public Member Functions
	minimumSpanningTree ()
	minimumSpanningTree (const parameters &par)
	minimumSpanningTree (const minimumSpanningTree &other)
virtual	~minimumSpanningTree ()
virtual const char *	getTypeName () const
virtual bool	apply (const std::vector< K > &src, const std::vector< V > &datas, weightedGraph< K, V, distance_type > &graph) const
virtual bool	apply (const weightedGraph< K, V, distance_type > &src, weightedGraph< K, V, distance_type > &dest) const
virtual bool	apply (weightedGraph< K, V, distance_type > &srcDest) const
minimumSpanningTree &	copy (const minimumSpanningTree &other)
minimumSpanningTree &	operator= (const minimumSpanningTree &other)
virtual functor *	clone () const
const parameters &	getParameters () const
Protected Types
typedef K::value_type	key_value_type
typedef weightedGraph< K, V, distance_type >::node	node_type
Protected Member Functions
bool	buildGraph (const std::vector< K > &src, const std::vector< V > &datas, weightedGraph< K, V, distance_type > &graph) const
bool	buildCompleteGraph (const std::vector< K > &src, const std::vector< V > &datas, weightedGraph< K, V, distance_type > &graph) const
Protected Attributes
Distantor	distantor

---

Detailed Description

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>
class lti::minimumSpanningTree< K, V, Distantor >

This class computes minimum spanning trees.

There are two ways two compute a minimum spanning trees. Either reduce a given weighted graph to its minimum spanning tree or compute the minimum spanning tree direct from a given data set. If you only want to reduce a weighted graph, just use the apply methods. If you want to compute the tree from a given data set (keys and values), there a three possibilities.

1. The keys (data points) are elements of a std::vector Then use the apply method of this class.
2. A matrix where each row represents one key (data point). Use the class minimumSpanningTreeOfKeyValuetype
3. A matrix where each element represents one key (data point). In this case use the class minimumSpanningTreeOfKeytype

A minimum spanning tree has the following template types:

• K: the key used for building the MST
• V: the value or data contained in each node of the tree default is int for an id.
• Distantor: policy class for the calculation of the distance between two keys in the tree (see below). Default is the square of the L2 distance lti::l2SquareDistantor.

The Distantor must implement the operator() which takes two arguments of type K and calculates their distance. It must define a type Distantor::distance_type which is also the return type of the operator. See lti::l2SquareDistantor for an example.

---

Member Typedef Documentation

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

typedef Distantor::distance_type lti::minimumSpanningTree< K, V, Distantor >::distance_type

return type of a call to the distantor, Distantor::distance_type

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

typedef K::value_type lti::minimumSpanningTree< K, V, Distantor >::key_value_type [protected]

The value type of the key type.

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

typedef weightedGraph<K,V,distance_type>::node lti::minimumSpanningTree< K, V, Distantor >::node_type [protected]

the type of a node of the weightedGraph used in the MST

---

Constructor & Destructor Documentation

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

lti::minimumSpanningTree< K, V, Distantor >::minimumSpanningTree

(

)

default constructor

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

lti::minimumSpanningTree< K, V, Distantor >::minimumSpanningTree

(

const parameters &

par

)

Construct a functor using the given parameters.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

lti::minimumSpanningTree< K, V, Distantor >::minimumSpanningTree

(

const minimumSpanningTree< K, V, Distantor > &

other

)

copy constructor

Parameters:

other

the object to be copied

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

virtual lti::minimumSpanningTree< K, V, Distantor >::~minimumSpanningTree

(

)

[virtual]

destructor

---

Member Function Documentation

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

virtual bool lti::minimumSpanningTree< K, V, Distantor >::apply

(

weightedGraph< K, V, distance_type > &

srcDest

)

const [virtual]

Computes the minimum spanning tree from the given Graph.

The resulting tree is returned in this graph.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

virtual bool lti::minimumSpanningTree< K, V, Distantor >::apply	(	const weightedGraph< K, V, distance_type > &	src,
		weightedGraph< K, V, distance_type > &	dest
	)			const [virtual]

Computes the minimum spanning tree from the given Graph.

The resulting tree is returned in graph dest.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

virtual bool lti::minimumSpanningTree< K, V, Distantor >::apply	(	const std::vector< K > &	src,
		const std::vector< V > &	datas,
		weightedGraph< K, V, distance_type > &	graph
	)			const [virtual]

Computes the minimum spanning tree from the given data.

The resulting tree is returned in this graph.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

bool lti::minimumSpanningTree< K, V, Distantor >::buildCompleteGraph	(	const std::vector< K > &	src,
		const std::vector< V > &	datas,
		weightedGraph< K, V, distance_type > &	graph
	)			const [protected]

Builds a complete graph of the input data.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

bool lti::minimumSpanningTree< K, V, Distantor >::buildGraph	(	const std::vector< K > &	src,
		const std::vector< V > &	datas,
		weightedGraph< K, V, distance_type > &	graph
	)			const [protected]

Builds up a graph that can be used for computing the minimum spanning tree.

This graph is not complete. But in most cases the edges that this graph contains, are all edges that are needed for finding the correct minimum spanning tree. The advantage of this version is that searching for the minimum spanning tree will be much faster. For this tree all points are connected with their neighbors. The number of neighbors it is connected to can be set by the parameter nbNeighbors. After that it is guaranteed that the graph is a connected graph.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

virtual functor* lti::minimumSpanningTree< K, V, Distantor >::clone

(

)

const [virtual]

returns a pointer to a clone of this functor.

Implements lti::functor.

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

minimumSpanningTree& lti::minimumSpanningTree< K, V, Distantor >::copy

(

const minimumSpanningTree< K, V, Distantor > &

other

)

copy data of "other" functor.

Parameters:

other

the functor to be copied

Returns:

a reference to this functor object

Reimplemented from lti::functor.

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

const parameters& lti::minimumSpanningTree< K, V, Distantor >::getParameters

(

)

const

returns used parameters

Reimplemented from lti::functor.

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

virtual const char* lti::minimumSpanningTree< K, V, Distantor >::getTypeName

(

)

const [virtual]

returns the name of this type ("minimumSpanningTree")

Reimplemented from lti::functor.

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

minimumSpanningTree& lti::minimumSpanningTree< K, V, Distantor >::operator=

(

const minimumSpanningTree< K, V, Distantor > &

other

)

alias for copy member

Parameters:

other

the functor to be copied

Returns:

a reference to this functor object

Reimplemented from lti::functor.

Reimplemented in lti::minimumSpanningTreeOfKeytype< K, V, Distantor >, and lti::minimumSpanningTreeOfKeyValuetype< K, V, Distantor >.

---

Member Data Documentation

template<class K, class V = int, class Distantor = l2SquareDistantor<K>>

Distantor lti::minimumSpanningTree< K, V, Distantor >::distantor [protected]

Distantor.

---

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

• ltiMinimumSpanningTree.h