#include <ExTreeM.h>

Inheritance diagram for ttk::ExTreeM:

Classes
struct	Branch
	A branch consists of the saddle vertices lying on the branch, and the parentbranch from which it splits / joins. More...

Public Member Functions
	ExTreeM ()

int	preconditionTriangulation (ttk::AbstractTriangulation *triangulation) const

template<typename TT = ttk::AbstractTriangulation>
int	computeNumberOfLinkComponents (const std::array< SimplexId, 45 > &linkVertices, const int nLinkVertices, const TT *triangulation) const
	compute the number of connected components in the vertex link

int	computeIdArray (SimplexId *ids, const std::vector< std::vector< SimplexId > > &criticalPoints) const
	transfer the per-thread ids to a single array

int	mergeCriticalPointVectors (std::array< std::vector< SimplexId >, 4 > &criticalPoints, const std::array< std::vector< std::vector< SimplexId > >, 4 > &criticalPoints_) const
	merge the critical points from all threads

template<typename TT = ttk::AbstractTriangulation>
int	computeCriticalPoints (std::array< std::vector< std::vector< SimplexId > >, 4 > &cp, const SimplexId order, const SimplexId ascManifold, const SimplexId desManifold, const TT triangulation) const
	compute the critical points using the ascending and descending manifolds

int	constructPersistencePairs (std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &pairs, std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &maximaTriplets, std::vector< std::array< ttk::SimplexId, 45 > > &saddleTriplets, const std::vector< ttk::SimplexId > &maximaLocalToGlobal, const std::vector< ttk::SimplexId > &saddlesLocalToGlobal, ttk::SimplexId globalMin)
	compute the persistence pairs using ExTreeM

void	sortAndRemoveDuplicates (std::array< ttk::SimplexId, 45 > &triplet)
	Sorts the reachable maxima and removes duplicates, such that the first entry is the smallest maximum reachable from the saddle and the last entry is the number of reachable maxima.

int	constructMergeTree (std::vector< Branch > &branches, std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &maximaTriplets, const std::vector< ttk::SimplexId > &maximaLocalToGlobal, const std::vector< ttk::SimplexId > &saddlesLocalToGlobal, const ttk::SimplexId *order)
	compute the merge tree from the maximaTriplets

template<typename triangulationType >
int	constructSegmentation (ttk::SimplexId segmentation, char regionType, const std::map< ttk::SimplexId, int > &cpMap, const std::vector< Branch > &branches, const ttk::SimplexId order, ttk::SimplexId descendingManifold, ttk::SimplexId tempArray, const triangulationType triangulation)
	construct the merge tree segmentation

template<typename triangulationType >
int	findAscPaths (std::vector< std::array< ttk::SimplexId, 45 > > &saddleTriplets, std::vector< ttk::SimplexId > &maximaLocalToGlobal, std::vector< ttk::SimplexId > &saddlesLocalToGlobal, ttk::SimplexId maxima, ttk::SimplexId saddles, const ttk::SimplexId order, ttk::SimplexId descendingManifold, ttk::SimplexId tempArray, std::vector< ttk::SimplexId > &saveGlobalIds, const triangulationType triangulation, ttk::SimplexId nMaxima, ttk::SimplexId nSaddles)
	transform ids from global to local and compute the reachable maxima from each saddle

template<class triangulationType >
int	computePairs (std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &persistencePairs, std::map< ttk::SimplexId, int > &cpMap, std::vector< Branch > &branches, ttk::SimplexId segmentation, char regionType, ttk::SimplexId descendingManifold, ttk::SimplexId tempArray, const ttk::SimplexId order, const triangulationType triangulation, const char type)

Public Member Functions inherited from ttk::Debug
	Debug ()

	~Debug () override

virtual int	setDebugLevel (const int &debugLevel)

int	setWrapper (const Wrapper *wrapper) override

int	printMsg (const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const std::vector< std::string > &msgs, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printErr (const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const

int	printWrn (const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const

int	printMsg (const std::string &msg, const double &progress, const double &time, const int &threads, const double &memory, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const double &time, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const double &time, const int &threads, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const debug::Priority &priority, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const std::vector< std::vector< std::string > > &rows, const debug::Priority &priority=debug::Priority::INFO, const bool hasHeader=true, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const debug::Separator &separator, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::INFO, std::ostream &stream=std::cout) const

int	printMsg (const debug::Separator &separator, const debug::Priority &priority, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const debug::Separator &separator, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::INFO, std::ostream &stream=std::cout) const

void	setDebugMsgPrefix (const std::string &prefix)

Public Member Functions inherited from ttk::BaseClass
	BaseClass ()

virtual	~BaseClass ()=default

int	getThreadNumber () const

virtual int	setThreadNumber (const int threadNumber)

Additional Inherited Members
Protected Member Functions inherited from ttk::Debug
int	printMsgInternal (const std::string &msg, const std::string &right, const std::string &filler, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsgInternal (const std::string &msg, const debug::Priority &priority, const debug::LineMode &lineMode, std::ostream &stream=std::cout) const

int	welcomeMsg (std::ostream &stream)

Protected Attributes inherited from ttk::Debug
int	debugLevel_

std::string	debugMsgPrefix_

std::string	debugMsgNamePrefix_

Protected Attributes inherited from ttk::BaseClass
bool	lastObject_

int	threadNumber_

Wrapper *	wrapper_

Static Protected Attributes inherited from ttk::Debug
static COMMON_EXPORTS debug::LineMode	lastLineMode = ttk::debug::LineMode::NEW

Detailed Description

Author: Michael Will mswil.nosp@m.l@rh.nosp@m.rk.un.nosp@m.i-kl.nosp@m..de

Date: November 2022.

This module defines the ExTreeM class that computes the Saddle Maximum and the split tree using the ascending Segmentation and the critical points

Related publication
"ExTreeM: Scalable Augmented Merge Tree Computation via Extremum Graphs"
Lukasczyk et al.
IEEE VIS 2023

Online examples:

Merge Trees Via ExTreeM

Definition at line 662 of file ExTreeM.h.

Constructor & Destructor Documentation

◆ ExTreeM()

ttk::ExTreeM::ExTreeM ( )

Definition at line 3 of file ExTreeM.cpp.

Member Function Documentation

◆ computeCriticalPoints()

template<typename TT = ttk::AbstractTriangulation>

int ttk::ExTreeM::computeCriticalPoints	(	std::array< std::vector< std::vector< SimplexId > >, 4 > &	cp,
		const SimplexId *	order,
		const SimplexId *	ascManifold,
		const SimplexId *	desManifold,
		const TT *	triangulation
	)		const

inline

compute the critical points using the ascending and descending manifolds

Parameters

[out]	cp	an array of vectors of critical point vectors per thread per type
[in]	order	orderArray
[in]	ascManifold	ascending manifold
[in]	desManifold	descending manifold
[in]	triangulation	triangulation

Returns: 1 on success

Definition at line 820 of file ExTreeM.h.

◆ computeIdArray()

int ttk::ExTreeM::computeIdArray	(	SimplexId *	ids,
		const std::vector< std::vector< SimplexId > > &	criticalPoints
	)		const

inline

transfer the per-thread ids to a single array

Parameters

[out]	ids	a pointer of critical points
[in]	criticalPoints	a list of critical points per thread

Returns: 1 on success

Definition at line 755 of file ExTreeM.h.

◆ computeNumberOfLinkComponents()

template<typename TT = ttk::AbstractTriangulation>

int ttk::ExTreeM::computeNumberOfLinkComponents	(	const std::array< SimplexId, 45 > &	linkVertices,
		const int	nLinkVertices,
		const TT *	triangulation
	)		const

inline

compute the number of connected components in the vertex link

Template Parameters

triangulationType type of triangulation

Parameters

[in]	linkVertices	the vertices in the link
[in]	nLinkVertices	the number of vertices in the link
[in]	triangulation	triangulation

Returns: the number of connected components in the link

Definition at line 694 of file ExTreeM.h.

◆ computePairs()

template<class triangulationType >

int ttk::ExTreeM::computePairs	(	std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &	persistencePairs,
		std::map< ttk::SimplexId, int > &	cpMap,
		std::vector< Branch > &	branches,
		ttk::SimplexId *	segmentation,
		char *	regionType,
		ttk::SimplexId *	descendingManifold,
		ttk::SimplexId *	tempArray,
		const ttk::SimplexId *	order,
		const triangulationType *	triangulation,
		const char	type
	)

inline

Definition at line 1399 of file ExTreeM.h.

◆ constructMergeTree()

int ttk::ExTreeM::constructMergeTree	(	std::vector< Branch > &	branches,
		std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &	maximaTriplets,
		const std::vector< ttk::SimplexId > &	maximaLocalToGlobal,
		const std::vector< ttk::SimplexId > &	saddlesLocalToGlobal,
		const ttk::SimplexId *	order
	)

inline

compute the merge tree from the maximaTriplets

Parameters

[out]	branches	mergetree as vector of branch structs
[in]	maximaTriplets	vector representing for each maximum, the saddle to which it is paired and the largest maximum reachable from the saddle (in local ids)
[in]	maximaLocalToGlobal	vector to transfer local ids to global ids for maxima ( 1-num maxima -> 1-num vertices overall)
[in]	saddlesLocalToGlobal	vector to transfer local ids to global ids for saddles ( 1-num saddles -> 1-num vertices overall)
[in]	order	order array

Returns: 1 on success

Definition at line 1142 of file ExTreeM.h.

◆ constructPersistencePairs()

int ttk::ExTreeM::constructPersistencePairs	(	std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &	pairs,
		std::vector< std::pair< ttk::SimplexId, ttk::SimplexId > > &	maximaTriplets,
		std::vector< std::array< ttk::SimplexId, 45 > > &	saddleTriplets,
		const std::vector< ttk::SimplexId > &	maximaLocalToGlobal,
		const std::vector< ttk::SimplexId > &	saddlesLocalToGlobal,
		ttk::SimplexId	globalMin
	)

inline

compute the persistence pairs using ExTreeM

Parameters

[out]	pairs	a vector of persistencepairs (in global ids)
[out]	maximaTriplets	vector representing for each maximum, the saddle to which it is paired and the largest maximum reachable from the saddle (in local ids)
[in]	saddleTriplets	for each saddle, the maxima which can be reached from this saddle
[in]	maximaLocalToGlobal	vector to transfer local ids to global ids for maxima ( 1-num maxima -> 1-num vertices overall)
[in]	saddlesLocalToGlobal	vector to transfer local ids to global ids for saddles ( 1-num saddles -> 1-num vertices overall)
[in]	globalMin	id of the global minimum

Returns: 1 on success

Definition at line 934 of file ExTreeM.h.

◆ constructSegmentation()

template<typename triangulationType >

int ttk::ExTreeM::constructSegmentation	(	ttk::SimplexId *	segmentation,
		char *	regionType,
		const std::map< ttk::SimplexId, int > &	cpMap,
		const std::vector< Branch > &	branches,
		const ttk::SimplexId *	order,
		ttk::SimplexId *	descendingManifold,
		ttk::SimplexId *	tempArray,
		const triangulationType *	triangulation
	)

inline

construct the merge tree segmentation

Parameters

[out]	segmentation	segmentation array, representing the upper end of the branch for each vertex
[out]	regionType	type of the segmentation region, see FTMTree for more detail
[in]	cpMap	a point id -> critical type map
[in]	branches	mergetree as vector of branch structs
[in]	order	order array
[in]	descendingManifold	descending manifold
[in]	tempArray	array to transform from global to local id
[in]	triangulation	triangulation

Returns: 1 on success

Definition at line 1229 of file ExTreeM.h.

◆ findAscPaths()

template<typename triangulationType >

int ttk::ExTreeM::findAscPaths	(	std::vector< std::array< ttk::SimplexId, 45 > > &	saddleTriplets,
		std::vector< ttk::SimplexId > &	maximaLocalToGlobal,
		std::vector< ttk::SimplexId > &	saddlesLocalToGlobal,
		ttk::SimplexId *	maxima,
		ttk::SimplexId *	saddles,
		const ttk::SimplexId *	order,
		ttk::SimplexId *	descendingManifold,
		ttk::SimplexId *	tempArray,
		std::vector< ttk::SimplexId > &	saveGlobalIds,
		const triangulationType *	triangulation,
		ttk::SimplexId	nMaxima,
		ttk::SimplexId	nSaddles
	)

inline

transform ids from global to local and compute the reachable maxima from each saddle

Parameters

[out]	saddleTriplets	segmentation array, representing the upper end of the branch for each vertex
[out]	maximaLocalToGlobal	vector of bools, 1 if vertex is a leaf, 0 otherwise
[out]	saddlesLocalToGlobal	mergetree as vector of branch structs
[in]	maxima	maxima
[in]	saddles	saddles
[in]	order	order array
[in]	descendingManifold	descending manifold
[in]	tempArray	ascending manifold, used as a temp array to transform from global to local id
[in]	saveGlobalIds	array to save the global ids, to transform the tempArray back to the original data
[in]	triangulation	triangulation
[in]	nMaxima	number of maxima
[in]	nSaddles	number of saddles

Returns: 1 on success

Definition at line 1317 of file ExTreeM.h.

◆ mergeCriticalPointVectors()

int ttk::ExTreeM::mergeCriticalPointVectors	(	std::array< std::vector< SimplexId >, 4 > &	criticalPoints,
		const std::array< std::vector< std::vector< SimplexId > >, 4 > &	criticalPoints_
	)		const

inline

merge the critical points from all threads

Parameters

[out]	criticalPoints	an array of critical point vectors per type
[in]	criticalPoints_	an array of vectors of critical point vectors per thread per type

Returns: 1 on success

Definition at line 777 of file ExTreeM.h.

◆ preconditionTriangulation()

int ttk::ExTreeM::preconditionTriangulation ( ttk::AbstractTriangulation * triangulation ) const

inline

Compute necessary triangulation information

Definition at line 677 of file ExTreeM.h.

◆ sortAndRemoveDuplicates()

void ttk::ExTreeM::sortAndRemoveDuplicates ( std::array< ttk::SimplexId, 45 > & triplet )

inline

Sorts the reachable maxima and removes duplicates, such that the first entry is the smallest maximum reachable from the saddle and the last entry is the number of reachable maxima.

Parameters

[in,out] triplet reachable maxima from a saddle

Definition at line 1115 of file ExTreeM.h.

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

/home/julien/Pro/git/github/ttk-tierny/core/base/exTreeM/ExTreeM.h
/home/julien/Pro/git/github/ttk-tierny/core/base/exTreeM/ExTreeM.cpp

Classes

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ExTreeM()

Member Function Documentation

◆ computeCriticalPoints()

◆ computeIdArray()

◆ computeNumberOfLinkComponents()

◆ computePairs()

◆ constructMergeTree()

◆ constructPersistencePairs()

◆ constructSegmentation()

◆ findAscPaths()

◆ mergeCriticalPointVectors()

◆ preconditionTriangulation()

◆ sortAndRemoveDuplicates()