HLIBpro  2.7
TAlgNDCTBuilder Class Reference

Enhances algebraic clustering by nested dissection.

#include <TAlgCTBuilder.hh>

Inheritance diagram for TAlgNDCTBuilder:
TAlgCTBuilder

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< TClusterdivide (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< TClusterTreebuild (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< TClusterdivide_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< TClusterdivide_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< TClusterbuild_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 More...
 
virtual std::unique_ptr< TClusterbuild_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.