Classes
struct	Cuts

struct	GenericFactor2D

struct	GenericFactor3D

struct	GenericNode2D

struct	GenericNode3D

struct	GenericUnaryFactor

struct	MetisResult

class	NestedDissection

struct	WorkSpace

Typedefs
typedef std::vector< sharedGenericFactor2D >	GenericGraph2D

typedef std::vector< sharedGenericFactor3D >	GenericGraph3D

typedef std::vector< sharedGenericUnaryFactor >	GenericUnaryGraph

typedef std::vector< int >	PartitionTable

typedef std::shared_ptr< GenericFactor2D >	sharedGenericFactor2D

typedef std::shared_ptr< GenericFactor3D >	sharedGenericFactor3D

typedef std::shared_ptr< GenericUnaryFactor >	sharedGenericUnaryFactor

typedef boost::shared_array< idx_t >	sharedInts

Enumerations
enum	GenericNode2DType { NODE_POSE_2D, NODE_LANDMARK_2D }

enum	GenericNode3DType { NODE_POSE_3D, NODE_LANDMARK_3D }

Functions
template<class GenericGraph >
void	addLandmarkToPartitionResult (const GenericGraph &graph, const std::vector< size_t > &landmarkKeys, MetisResult &partitionResult, WorkSpace &workspace)

void	checkSingularity (const GenericGraph2D &graph, const std::vector< size_t > &frontals, WorkSpace &workspace, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)

void	checkSingularity (const GenericGraph3D &graph, const std::vector< size_t > &frontals, WorkSpace &workspace, const size_t minNrConstraintsPerCamera, const size_t minNrConstraintsPerLandmark)

DSFVector	createDSF (const GenericGraph3D &graph, const vector< size_t > &keys, const WorkSpace &workspace)

std::pair< int, sharedInts >	edgeMetis (idx_t n, const sharedInts &xadj, const sharedInts &adjncy, const sharedInts &adjwgt, bool verbose)

template<class GenericGraph >
std::optional< MetisResult >	edgePartitionByMetis (const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose)

list< vector< size_t > >	findIslands (const GenericGraph2D &graph, const vector< size_t > &keys, WorkSpace &workspace, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)

std::list< std::vector< size_t > >	findIslands (const GenericGraph2D &graph, const std::vector< size_t > &keys, WorkSpace &workspace, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)

std::list< std::vector< size_t > >	findIslands (const GenericGraph3D &graph, const std::vector< size_t > &keys, WorkSpace &workspace, const size_t minNrConstraintsPerCamera, const size_t minNrConstraintsPerLandmark)

list< vector< size_t > >	findIslands (const GenericGraph3D &graph, const vector< size_t > &keys, WorkSpace &workspace, const size_t minNrConstraintsPerCamera, const size_t minNrConstraintsPerLandmark)

template<class GenericGraph >
std::optional< MetisResult >	findPartitoning (const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose, const std::optional< std::vector< Symbol > > &int2symbol, const bool reduceGraph)

template<class GenericGraph >
int	findSeparator (const GenericGraph &graph, const std::vector< size_t > &keys, const int minNodesPerMap, WorkSpace &workspace, bool verbose, const std::optional< std::vector< Symbol > > &int2symbol, const bool reduceGraph, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)

void	findSingularCamerasLandmarks (const GenericGraph3D &graph, const WorkSpace &workspace, const vector< bool > &isCamera, const vector< bool > &isLandmark, set< size_t > &singularCameras, set< size_t > &singularLandmarks, vector< int > &nrConstraints, bool &foundSingularCamera, bool &foundSingularLandmark, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)

int	getNrCommonLandmarks (const vector< size_t > &landmarks1, const vector< size_t > &landmarks2)

bool	hasCommonCamera (const std::set< size_t > &cameras1, const std::set< size_t > &cameras2)

bool	isLargerIsland (const std::vector< size_t > &island1, const std::vector< size_t > &island2)

bool	isSingular (const set< size_t > &singularCameras, const set< size_t > &singularLandmarks, const GenericNode3D &node)

void	modefied_EdgeComputeSeparator (idx_t nvtxs, idx_t xadj, idx_t adjncy, idx_t vwgt, idx_t adjwgt, idx_t options, idx_t edgecut, idx_t part)

template<class GenericGraph >
void	prepareMetisGraph (const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, sharedInts ptr_xadj, sharedInts ptr_adjncy, sharedInts *ptr_adjwgt)

void	print (const GenericGraph2D &graph, const std::string name)

void	print (const GenericGraph3D &graph, const std::string name)

void	printIsland (const std::vector< size_t > &island)

void	printIslands (const std::list< std::vector< size_t > > &islands)

void	printNumCamerasLandmarks (const std::vector< size_t > &keys, const std::vector< Symbol > &int2symbol)

void	reduceGenericGraph (const GenericGraph2D &graph, const std::vector< size_t > &cameraKeys, const std::vector< size_t > &landmarkKeys, const std::vector< int > &dictionary, GenericGraph2D &reducedGraph)

void	reduceGenericGraph (const GenericGraph3D &graph, const std::vector< size_t > &cameraKeys, const std::vector< size_t > &landmarkKeys, const std::vector< int > &dictionary, GenericGraph3D &reducedGraph)

std::pair< int, sharedInts >	separatorMetis (idx_t n, const sharedInts &xadj, const sharedInts &adjncy, const sharedInts &adjwgt, bool verbose)

template<class GenericGraph >
std::optional< MetisResult >	separatorPartitionByMetis (const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose)

Typedef Documentation

◆ GenericGraph2D

typedef std::vector<sharedGenericFactor2D> gtsam::partition::GenericGraph2D

Definition at line 49 of file GenericGraph.h.

◆ GenericGraph3D

typedef std::vector<sharedGenericFactor3D> gtsam::partition::GenericGraph3D

Definition at line 97 of file GenericGraph.h.

◆ GenericUnaryGraph

typedef std::vector<sharedGenericUnaryFactor> gtsam::partition::GenericUnaryGraph

Definition at line 130 of file GenericGraph.h.

◆ PartitionTable

typedef std::vector<int> gtsam::partition::PartitionTable

Definition at line 16 of file PartitionWorkSpace.h.

◆ sharedGenericFactor2D

typedef std::shared_ptr<GenericFactor2D> gtsam::partition::sharedGenericFactor2D

graph is a collection of factors

Definition at line 48 of file GenericGraph.h.

◆ sharedGenericFactor3D

typedef std::shared_ptr<GenericFactor3D> gtsam::partition::sharedGenericFactor3D

graph is a collection of factors

Definition at line 96 of file GenericGraph.h.

◆ sharedGenericUnaryFactor

typedef std::shared_ptr<GenericUnaryFactor> gtsam::partition::sharedGenericUnaryFactor

graph is a collection of factors

Definition at line 129 of file GenericGraph.h.

◆ sharedInts

typedef boost::shared_array<idx_t> gtsam::partition::sharedInts

Definition at line 33 of file FindSeparator-inl.h.

Enumeration Type Documentation

◆ GenericNode2DType

enum gtsam::partition::GenericNode2DType

Enumerator
NODE_POSE_2D
NODE_LANDMARK_2D

Definition at line 25 of file GenericGraph.h.

◆ GenericNode3DType

enum gtsam::partition::GenericNode3DType

Enumerator
NODE_POSE_3D
NODE_LANDMARK_3D

Definition at line 71 of file GenericGraph.h.

Function Documentation

◆ addLandmarkToPartitionResult()

template<class GenericGraph >

void gtsam::partition::addLandmarkToPartitionResult	(	const GenericGraph &	graph,
		const std::vector< size_t > &	landmarkKeys,
		MetisResult &	partitionResult,
		WorkSpace &	workspace
	)

Definition at line 394 of file FindSeparator-inl.h.

◆ checkSingularity() [1/2]

void gtsam::partition::checkSingularity	(	const GenericGraph2D &	graph,
		const std::vector< size_t > &	frontals,
		WorkSpace &	workspace,
		const int	minNrConstraintsPerCamera,
		const int	minNrConstraintsPerLandmark
	)

inline

check whether the 2D graph is singular (under constrained) , Dummy function for 2D

Definition at line 62 of file GenericGraph.h.

◆ checkSingularity() [2/2]

void gtsam::partition::checkSingularity	(	const GenericGraph3D &	graph,
		const std::vector< size_t > &	frontals,
		WorkSpace &	workspace,
		const size_t	minNrConstraintsPerCamera,
		const size_t	minNrConstraintsPerLandmark
	)

check whether the 3D graph is singular (under constrained)

Definition at line 407 of file GenericGraph.cpp.

◆ createDSF()

DSFVector gtsam::partition::createDSF	(	const GenericGraph3D &	graph,
		const vector< size_t > &	keys,
		const WorkSpace &	workspace
	)

Definition at line 130 of file GenericGraph.cpp.

◆ edgeMetis()

std::pair<int, sharedInts> gtsam::partition::edgeMetis	(	idx_t	n,
		const sharedInts &	xadj,
		const sharedInts &	adjncy,
		const sharedInts &	adjwgt,
		bool	verbose
	)

Return the number of edge cuts and the partition indices {part} Part [j] is 0 or 1, depending on whether node j is in the left part of the graph or the right part respectively

Definition at line 129 of file FindSeparator-inl.h.

◆ edgePartitionByMetis()

template<class GenericGraph >

std::optional<MetisResult> gtsam::partition::edgePartitionByMetis	(	const GenericGraph &	graph,
		const std::vector< size_t > &	keys,
		WorkSpace &	workspace,
		bool	verbose
	)

Definition at line 292 of file FindSeparator-inl.h.

◆ findIslands() [1/4]

list<vector<size_t> > gtsam::partition::findIslands	(	const GenericGraph2D &	graph,
		const vector< size_t > &	keys,
		WorkSpace &	workspace,
		const int	minNrConstraintsPerCamera,
		const int	minNrConstraintsPerLandmark
	)

Note: Need to be able to handle a graph with factors that involve variables not in the given {keys}

Definition at line 23 of file GenericGraph.cpp.

◆ findIslands() [2/4]

std::list<std::vector<size_t> > gtsam::partition::findIslands	(	const GenericGraph2D &	graph,
		const vector< size_t > &	keys,
		WorkSpace &	workspace,
		const int	minNrConstraintsPerCamera,
		const int	minNrConstraintsPerLandmark
	)

merge nodes in DSF using constraints captured by the given graph

Note: Need to be able to handle a graph with factors that involve variables not in the given {keys}

Definition at line 23 of file GenericGraph.cpp.

◆ findIslands() [3/4]

std::list<std::vector<size_t> > gtsam::partition::findIslands	(	const GenericGraph3D &	graph,
		const std::vector< size_t > &	keys,
		WorkSpace &	workspace,
		const size_t	minNrConstraintsPerCamera,
		const size_t	minNrConstraintsPerLandmark
	)

merge nodes in DSF using constraints captured by the given graph

Definition at line 240 of file GenericGraph.cpp.

◆ findIslands() [4/4]

list<vector<size_t> > gtsam::partition::findIslands	(	const GenericGraph3D &	graph,
		const std::vector< size_t > &	keys,
		WorkSpace &	workspace,
		const size_t	minNrConstraintsPerCamera,
		const size_t	minNrConstraintsPerLandmark
	)

merge nodes in DSF using constraints captured by the given graph

Definition at line 240 of file GenericGraph.cpp.

◆ findPartitoning()

template<class GenericGraph >

std::optional<MetisResult> gtsam::partition::findPartitoning	(	const GenericGraph &	graph,
		const std::vector< size_t > &	keys,
		WorkSpace &	workspace,
		bool	verbose,
		const std::optional< std::vector< Symbol > > &	int2symbol,
		const bool	reduceGraph
	)

Definition at line 442 of file FindSeparator-inl.h.

◆ findSeparator()

template<class GenericGraph >

int gtsam::partition::findSeparator	(	const GenericGraph &	graph,
		const std::vector< size_t > &	keys,
		const int	minNodesPerMap,
		WorkSpace &	workspace,
		bool	verbose,
		const std::optional< std::vector< Symbol > > &	int2symbol,
		const bool	reduceGraph,
		const int	minNrConstraintsPerCamera,
		const int	minNrConstraintsPerLandmark
	)

return the number of submaps and the parition table of the partitioned graph (stored in workspace.partitionTable). return 0 if failed Note that the original output of Metis is 0,1 for submap, and 2 for the separator.

Definition at line 488 of file FindSeparator-inl.h.

◆ findSingularCamerasLandmarks()

void gtsam::partition::findSingularCamerasLandmarks	(	const GenericGraph3D &	graph,
		const WorkSpace &	workspace,
		const vector< bool > &	isCamera,
		const vector< bool > &	isLandmark,
		set< size_t > &	singularCameras,
		set< size_t > &	singularLandmarks,
		vector< int > &	nrConstraints,
		bool &	foundSingularCamera,
		bool &	foundSingularLandmark,
		const int	minNrConstraintsPerCamera,
		const int	minNrConstraintsPerLandmark
	)

Definition at line 196 of file GenericGraph.cpp.

◆ getNrCommonLandmarks()

int gtsam::partition::getNrCommonLandmarks	(	const vector< size_t > &	landmarks1,
		const vector< size_t > &	landmarks2
	)

inline

Definition at line 336 of file GenericGraph.cpp.

◆ hasCommonCamera()

bool gtsam::partition::hasCommonCamera	(	const std::set< size_t > &	cameras1,
		const std::set< size_t > &	cameras2
	)

inline

Definition at line 135 of file GenericGraph.h.

◆ isLargerIsland()

bool gtsam::partition::isLargerIsland	(	const std::vector< size_t > &	island1,
		const std::vector< size_t > &	island2
	)

Definition at line 364 of file FindSeparator-inl.h.

◆ isSingular()

bool gtsam::partition::isSingular	(	const set< size_t > &	singularCameras,
		const set< size_t > &	singularLandmarks,
		const GenericNode3D &	node
	)

inline

Definition at line 184 of file GenericGraph.cpp.

◆ modefied_EdgeComputeSeparator()

void gtsam::partition::modefied_EdgeComputeSeparator	(	idx_t *	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	adjwgt,
		idx_t *	options,
		idx_t *	edgecut,
		idx_t *	part
	)

Definition at line 81 of file FindSeparator-inl.h.

◆ prepareMetisGraph()

template<class GenericGraph >

void gtsam::partition::prepareMetisGraph	(	const GenericGraph &	graph,
		const std::vector< size_t > &	keys,
		WorkSpace &	workspace,
		sharedInts *	ptr_xadj,
		sharedInts *	ptr_adjncy,
		sharedInts *	ptr_adjwgt
	)

Prepare the data structure {xadj} and {adjncy} required by metis xadj always has the size equal to the no. of the nodes plus 1 adjncy always has the size equal to two times of the no. of the edges in the Metis graph

Definition at line 178 of file FindSeparator-inl.h.

◆ print() [1/2]

void gtsam::partition::print	(	const GenericGraph2D &	graph,
		const std::string	name = `"GenericGraph2D"`
	)

print the graph

Definition at line 114 of file GenericGraph.cpp.

◆ print() [2/2]

void gtsam::partition::print	(	const GenericGraph3D &	graph,
		const std::string	name = `"GenericGraph3D"`
	)

print the graph

Definition at line 121 of file GenericGraph.cpp.

◆ printIsland()

void gtsam::partition::printIsland ( const std::vector< size_t > & island )

Definition at line 370 of file FindSeparator-inl.h.

◆ printIslands()

void gtsam::partition::printIslands ( const std::list< std::vector< size_t > > & islands )

Definition at line 377 of file FindSeparator-inl.h.

◆ printNumCamerasLandmarks()

void gtsam::partition::printNumCamerasLandmarks	(	const std::vector< size_t > &	keys,
		const std::vector< Symbol > &	int2symbol
	)

Definition at line 382 of file FindSeparator-inl.h.

◆ reduceGenericGraph() [1/2]

void gtsam::partition::reduceGenericGraph	(	const GenericGraph2D &	graph,
		const std::vector< size_t > &	cameraKeys,
		const std::vector< size_t > &	landmarkKeys,
		const std::vector< int > &	dictionary,
		GenericGraph2D &	reducedGraph
	)

inline

eliminate the sensors from generic graph

Definition at line 56 of file GenericGraph.h.

◆ reduceGenericGraph() [2/2]

void gtsam::partition::reduceGenericGraph	(	const GenericGraph3D &	graph,
		const std::vector< size_t > &	cameraKeys,
		const std::vector< size_t > &	landmarkKeys,
		const std::vector< int > &	dictionary,
		GenericGraph3D &	reducedGraph
	)

eliminate the sensors from generic graph

Definition at line 353 of file GenericGraph.cpp.

◆ separatorMetis()

std::pair<int, sharedInts> gtsam::partition::separatorMetis	(	idx_t	n,
		const sharedInts &	xadj,
		const sharedInts &	adjncy,
		const sharedInts &	adjwgt,
		bool	verbose
	)

Return the size of the separator and the partiion indices {part} Part [j] is 0, 1, or 2, depending on whether node j is in the left part of the graph, the right part, or the separator, respectively

Definition at line 42 of file FindSeparator-inl.h.

◆ separatorPartitionByMetis()

template<class GenericGraph >

std::optional< MetisResult > gtsam::partition::separatorPartitionByMetis	(	const GenericGraph &	graph,
		const std::vector< size_t > &	keys,
		WorkSpace &	workspace,
		bool	verbose
	)

use Metis library to partition, return the size of separator and the optional partition table the size of dictionary mush be equal to the number of variables in the original graph (the largest one)

Definition at line 240 of file FindSeparator-inl.h.

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ GenericGraph2D

◆ GenericGraph3D

◆ GenericUnaryGraph

◆ PartitionTable

◆ sharedGenericFactor2D

◆ sharedGenericFactor3D

◆ sharedGenericUnaryFactor

◆ sharedInts

Enumeration Type Documentation

◆ GenericNode2DType

◆ GenericNode3DType

Function Documentation

◆ addLandmarkToPartitionResult()

◆ checkSingularity() [1/2]

◆ checkSingularity() [2/2]

◆ createDSF()

◆ edgeMetis()

◆ edgePartitionByMetis()

◆ findIslands() [1/4]

◆ findIslands() [2/4]

◆ findIslands() [3/4]

◆ findIslands() [4/4]

◆ findPartitoning()

◆ findSeparator()

◆ findSingularCamerasLandmarks()

◆ getNrCommonLandmarks()

◆ hasCommonCamera()

◆ isLargerIsland()

◆ isSingular()

◆ modefied_EdgeComputeSeparator()

◆ prepareMetisGraph()

◆ print() [1/2]

◆ print() [2/2]

◆ printIsland()

◆ printIslands()

◆ printNumCamerasLandmarks()

◆ reduceGenericGraph() [1/2]

◆ reduceGenericGraph() [2/2]

◆ separatorMetis()

◆ separatorPartitionByMetis()