MLPACK
1.0.7
|
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree. More...
Classes | |
struct | SortEdgesHelper |
For sorting the edge list after the computation. More... | |
Public Member Functions | |
DualTreeBoruvka (const typename TreeType::Mat &dataset, const bool naive=false, const size_t leafSize=1, const MetricType metric=MetricType()) | |
Create the tree from the given dataset. More... | |
DualTreeBoruvka (TreeType *tree, const typename TreeType::Mat &dataset, const MetricType metric=MetricType()) | |
Create the DualTreeBoruvka object with an already initialized tree. More... | |
~DualTreeBoruvka () | |
Delete the tree, if it was created inside the object. More... | |
void | ComputeMST (arma::mat &results) |
Iteratively find the nearest neighbor of each component until the MST is complete. More... | |
Private Member Functions | |
void | AddAllEdges () |
Adds all the edges found in one iteration to the list of neighbors. More... | |
void | AddEdge (const size_t e1, const size_t e2, const double distance) |
Adds a single edge to the edge list. More... | |
void | Cleanup () |
The values stored in the tree must be reset on each iteration. More... | |
void | CleanupHelper (TreeType *tree) |
This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes. More... | |
void | EmitResults (arma::mat &results) |
Unpermute the edge list and output it to results. More... | |
Private Attributes | |
UnionFind | connections |
Connections. More... | |
TreeType::Mat & | data |
Reference to the data (this is what should be used for accessing data). More... | |
TreeType::Mat | dataCopy |
Copy of the data (if necessary). More... | |
std::vector< EdgePair > | edges |
Edges. More... | |
MetricType | metric |
The instantiated metric. More... | |
bool | naive |
Indicates whether or not O(n^2) naive mode will be used. More... | |
arma::vec | neighborsDistances |
List of edge distances. More... | |
arma::Col< size_t > | neighborsInComponent |
List of edge nodes. More... | |
arma::Col< size_t > | neighborsOutComponent |
List of edge nodes. More... | |
std::vector< size_t > | oldFromNew |
Permutations of points during tree building. More... | |
bool | ownTree |
Indicates whether or not we "own" the tree. More... | |
struct mlpack::emst::DualTreeBoruvka::SortEdgesHelper | SortFun |
double | totalDist |
Total distance of the tree. More... | |
TreeType * | tree |
Pointer to the root of the tree. More... | |
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree.
For more information on the algorithm, see the following citation:
General usage of this class might be like this:
More advanced usage of the class can use different types of trees, pass in an already-built tree, or compute the MST using the O(n^2) naive algorithm.
MetricType | The metric to use. IMPORTANT: this hasn't really been tested with anything other than the L2 metric, so user beware. Note that the tree type needs to compute bounds using the same metric as the type specified here. |
TreeType | Type of tree to use. Should use DTBStat as a statistic. |
mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::DualTreeBoruvka | ( | const typename TreeType::Mat & | dataset, |
const bool | naive = false , |
||
const size_t | leafSize = 1 , |
||
const MetricType | metric = MetricType() |
||
) |
Create the tree from the given dataset.
This copies the dataset to an internal copy, because tree-building modifies the dataset.
data | Dataset to build a tree for. |
naive | Whether the computation should be done in O(n^2) naive mode. |
leafSize | The leaf size to be used during tree construction. |
mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::DualTreeBoruvka | ( | TreeType * | tree, |
const typename TreeType::Mat & | dataset, | ||
const MetricType | metric = MetricType() |
||
) |
Create the DualTreeBoruvka object with an already initialized tree.
This will not copy the dataset, and can save a little processing power. Naive mode is not available as an option for this constructor; instead, to run naive computation, construct a tree with all the points in one leaf (i.e. leafSize = number of points).
tree | Pre-built tree. |
dataset | Dataset corresponding to the pre-built tree. |
mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::~DualTreeBoruvka | ( | ) |
Delete the tree, if it was created inside the object.
|
private |
Adds all the edges found in one iteration to the list of neighbors.
|
private |
Adds a single edge to the edge list.
|
private |
The values stored in the tree must be reset on each iteration.
|
private |
This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes.
void mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::ComputeMST | ( | arma::mat & | results | ) |
Iteratively find the nearest neighbor of each component until the MST is complete.
The results will be a 3xN matrix (with N equal to the number of edges in the minimum spanning tree). The first row will contain the lesser index of the edge; the second row will contain the greater index of the edge; and the third row will contain the distance between the two edges.
results | Matrix which results will be stored in. |
|
private |
Unpermute the edge list and output it to results.
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |