Enhances algebraic clustering by nested dissection.

#include <TAlgCTBuilder.hh>

Inheritance diagram for TAlgNDCTBuilder:

Classes
class	TOptClusterSize
	Controls optimal cluster size per tree level. More...

Public Member Functions
	TAlgNDCTBuilder (const TAlgCTBuilder *alg_ct_builder, const uint n_min=CFG::Cluster::nmin, const uint min_leaf_lvl=0)
	construct cluster tree builder with alg_ct_builder as base algorithm

virtual	~TAlgNDCTBuilder ()
	dtor

void	sync_interface_depth (const bool b)
	set mode for handling interface cluster tree depth, e.g. synchronise with domain clusters

virtual std::unique_ptr< TCluster >	divide (const TGraph &graph, const uint lvl, TPermutation &perm, const idx_t idx_ofs, const uint n_min, const TSparseMatrix *S, const uint max_lvl) const

virtual void	partition (const TGraph &graph, TNodeSet &left, TNodeSet &right) const
	partition graph using base algorithm

Public Member Functions inherited from TAlgCTBuilder
	TAlgCTBuilder (TAlgPartStrat *part_strat, const uint n_min=CFG::Cluster::nmin, const uint min_leaf_lvl=0)
	construct cluster tree builder with given partition strategy and tree parameters

virtual	~TAlgCTBuilder ()
	dtor

void	set_high_deg_fac (const uint fac)
	activate/deactivate (if fac = 0) high degree node separation

void	set_edge_weights_mode (const edge_weights_mode_t edge_weights_mode)
	set mode for edge weights

virtual std::unique_ptr< TClusterTree >	build (const TSparseMatrix *S, const idx_t idx_ofs=0) const
	build cluster tree using connectivity in sparse matrix S

Protected Member Functions
std::unique_ptr< TCluster >	divide_if (const TGraph &graph, const TNodeSet &surrounding, const TNodeSet &vtxsep, const uint lvl, const idx_t idx_ofs, TPermutation &perm, const uint max_lvl, const uint n_min, const TOptClusterSize &csize) const
	divide vertex separator vtxsep using connectivity defined by graph

std::unique_ptr< TCluster >	divide_if (const TGraph &graph, const uint lvl, TPermutation &perm, const idx_t idx_ofs, const uint n_min, const TSparseMatrix *S, const uint max_lvl, const TOptClusterSize &csize) const
	build cluster tree for vertex separator graph

virtual std::unique_ptr< TCluster >	build_leaf (const TGraph &graph, const TNodeSet &nodes, const idx_t idx_ofs, TPermutation &perm) const
	build leaf node for indices in nodes

virtual void	partition (const TGraph &graph, const TNodeSet &surrounding, const TNodeSet &vtxsep, TNodeSet &left, TNodeSet &right, TNodeSet &loc_sur) const
	graph partitioning algorithm for vertex separators

virtual void	build_vtx_sep (const TGraph &graph, TNodeSet &left, TNodeSet &right, TNodeSet &vtxsep) const
	build vertex separator vtxsep between left and right

virtual uint	bfs_vtxsep (const TGraph &graph, TNodeSet &start, TNodeSet &last, std::vector< bool > &visited, const std::vector< char > &label, const uint max_nnodes) const

virtual void	bfs_step (const TGraph &graph, TNodeSet &nodes, TNodeSet &succ, std::vector< bool > &visited, const std::vector< char > &label, const char local) const

virtual void	restrict_vtx (TNodeSet &nodes, const std::vector< char > &label) const
	restrict node set nodes to nodes in vertex separator, defined by label

virtual void	build_scc (const TGraph &graph, const TNodeSet &surrounding, std::list< TNodeSet > &scc) const
	build strongly connected components of graph restricted to surrounding

virtual std::unique_ptr< TCluster >	build_leaf (const TGraph &graph, const idx_t idx_ofs, TPermutation &perm) const
	build leaf node for indices in graph

Protected Member Functions inherited from TAlgCTBuilder
virtual void	scc_partition (const TGraph &graph, TNodeSet &left, TNodeSet &right) const
	same as More...

virtual std::unique_ptr< TCluster >	build_leaf (const TGraph &graph, const idx_t idx_ofs, TPermutation &perm) const
	build leaf node for indices in graph

virtual uint	adjust_n_min (const TSparseMatrix *S) const
	adjust n_min based on sparse matrix if default value of 0 was given in constructor

virtual void	check_flow (const TGraph &graph, TNodeSet &left, TNodeSet &right, const TSparseMatrix *S) const
	analyze connections between sub graphs left and right and swap if necessary

Member Function Documentation

◆ bfs_step()

virtual void bfs_step	(	const TGraph &	graph,
		TNodeSet &	nodes,
		TNodeSet &	succ,
		std::vector< bool > &	visited,
		const std::vector< char > &	label,
		const char	local
	)		const

protectedvirtual

collect successors to nodes in nodes

search is restricted to nodes with label == local

◆ bfs_vtxsep()

virtual uint bfs_vtxsep	(	const TGraph &	graph,
		TNodeSet &	start,
		TNodeSet &	last,
		std::vector< bool > &	visited,
		const std::vector< char > &	label,
		const uint	max_nnodes
	)		const

protectedvirtual

do a complete BFS starting at start in graph but finish if max_nnodes "VERTEX_SEP" nodes have been visited

visited == true is assumed for all nonlocal nodes

◆ divide()

virtual std::unique_ptr< TCluster > divide	(	const TGraph &	graph,
		const uint	lvl,
		TPermutation &	perm,
		const idx_t	idx_ofs,
		const uint	n_min,
		const TSparseMatrix *	S,
		const uint	max_lvl
	)		const

virtual

divide graph graph and build corresponding cluster tree (instead of bipartition, also build vertex separator son)

Reimplemented from TAlgCTBuilder.

Classes

Public Member Functions

Protected Member Functions

Member Function Documentation

◆ bfs_step()

◆ bfs_vtxsep()

◆ divide()