Enhances algebraic clustering by nested dissection.

#include <TAlgCTBuilder.hh>

Inheritance diagram for TNDAlgCTBuilder:

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

Public Member Functions
	TNDAlgCTBuilder (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	~TNDAlgCTBuilder ()
	dtor
void	set_sync_depth (const bool b)
virtual 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_use_edge_weights (const bool use_edge_weights, const bool sym_edge_weights)
virtual TClusterTree *	build (const TSparseMatrix *S, const idx_t idx_ofs=0) const
	build cluster tree using connectivity in sparse matrix S

Protected Member Functions
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
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 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
Protected Member Functions inherited from TAlgCTBuilder
virtual void	scc_partition (const TGraph &graph, TNodeSet &left, TNodeSet &right) const
	same as
virtual 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

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

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

virtual 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.

void set_sync_depth ( const bool b )

inline

activate/deactivate synchronisation of depth of interface tree with domain trees

Classes

Public Member Functions

Protected Member Functions

Member Function Documentation