kruskal-inl.h File Reference

#include <gtsam/base/DSFMap.h>
#include <gtsam/base/FastMap.h>
#include <gtsam/base/types.h>
#include <gtsam/inference/VariableIndex.h>
#include <algorithm>
#include <numeric>
#include <vector>

Include dependency graph for kruskal-inl.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
std::vector< size_t >	gtsam::utils::sortedIndices (const std::vector< double > &weights)
template<class FACTOR >
std::vector< size_t >	gtsam::utils::kruskal (const FactorGraph< FACTOR > &fg, const std::vector< double > &weights)

Detailed Description

Date

Dec 31, 2009

Author

Frank Dellaert

Yong-Dian Jian

Ankur Roy Chowdhury

Function Documentation

kruskal()

template<class FACTOR >

std::vector< size_t > gtsam::utils::kruskal	(	const FactorGraph< FACTOR > &	fg,
		const std::vector< double > &	weights
	)

Compute the minimum spanning tree (MST) using Kruskal's algorithm

Parameters

fg	Factor graph
weights	Weights of the edges/factors in the factor graph

Returns

Edge/factor indices spanning the MST

Note

Only binary factors are considered while constructing the spanning tree

The indices of 'weights' should match the indices of the edges in the factor graph