HLIBpro  2.5.1
TGraph Class Reference

Class for a undirected graph stored as adjacency matrix in CRS representation.

#include <TGraph.hh>

Inheritance diagram for TGraph:
TEWGraph

Classes

class  TAdjNodes
 
class  TAdjNodesWeights
 
struct  TNodes
 

Public Member Functions

 TGraph ()
 construct empty graph
 
 TGraph (const TSparseMatrix *S, const std::vector< bool > &nodemask)
 
virtual ~TGraph ()
 dtor
 
size_t nnodes () const noexcept
 return number of nodes in graph
 
size_t nedges () const noexcept
 return number of edges in graph
 
bool has_global_names () const noexcept
 return true, if graph stores global names
 
size_t degree (const node_t node) const noexcept
 return degree of node, e.g. number of incident edges
 
TNodes nodes () const noexcept
 return set of graph nodes
 
TAdjNodes adj_nodes (const node_t node) const noexcept
 return set of adjacent nodes in graph
 
TAdjNodesWeights adj_nodes_weights (const node_t node) const noexcept
 return set of adjacent nodes with edge weights in graph
 
virtual void init (const size_t annodes, const size_t anedges, const bool aglobal=false)
 
std::vector< node_t > & global_name () noexcept
 return global name data
 
node_t min_degree_node () const
 return node with minimal degree in given graph
 
node_t max_degree_node () const
 return node with maximal degree in given graph
 
void build_scc (std::list< TNodeSet > &scc, const std::vector< uint > &label, const uint mark) const
 compute strongly connected components and build graph for each component More...
 
void build_scc (std::list< TNodeSet > &scc) const
 compute strongly connected components and build nodeset for each component
 
auto restrict (const TNodeSet &nodes) const -> std::unique_ptr< TGraph >
 restrict graph to nodes in nodes and return resulting subgraph
 
void vertex_separator (std::vector< uint > &label, const TNodeSet &left, const TNodeSet &right, TNodeSet &vertex_sep, const uint if_label) const
 
virtual bool has_edge_weights () const noexcept
 return false to show that Graph has no edge weights
 
virtual weight_t edge_weight (const idx_t) const noexcept
 return edge weight for i'th edge
 
virtual void set_edge_weight (const idx_t, const weight_t)
 set edge weight for i'th edge
 
virtual weight_t min_edge_weight () const
 return the minimal absolute value of the edge weights of TEWGraph
 
void print (const std::string &filename, const bool global=false) const
 print graph in GraphViz format to filename
 
void print (const std::string &filename, const std::vector< uint > &label, const bool global=false) const
 print graph in GraphViz format to filename with labels in label
 
virtual void write (const std::string &filename) const
 export graph in Chaco/Jostle/Metis format to filename
 
TGraphoperator= (const TGraph &graph)
 copy operator
 
virtual TGraphcreate () const
 virtual constructor, e.g. return object of same type
 

Protected Attributes

std::vector< idx_t > _adj_list_ptr
 contains pointers into adjacency list for each node
 
std::vector< node_t_adj_nodes
 contains list of adjacent nodes for each node
 
std::vector< node_t_global_name
 global name of local nodes
 

Constructor & Destructor Documentation

◆ TGraph()

TGraph ( const TSparseMatrix S,
const std::vector< bool > &  nodemask 
)

construct graph using symmetrised sparsity pattern of matrix S; nodes marked in nodemask, i.e. nodemask[node] = true, will be excluded from graph

Member Function Documentation

◆ build_scc()

void build_scc ( std::list< TNodeSet > &  scc,
const std::vector< uint > &  label,
const uint  mark 
) const

compute strongly connected components but restrict computation to nodes marked by mark, where node marks are stored in label

◆ init()

virtual void init ( const size_t  annodes,
const size_t  anedges,
const bool  aglobal = false 
)
inlinevirtual

initialise graph for nnnodes nodes and nedges edges

  • if global is true, global names will also be initialised

Reimplemented in TEWGraph.

◆ vertex_separator()

void vertex_separator ( std::vector< uint > &  label,
const TNodeSet left,
const TNodeSet right,
TNodeSet vertex_sep,
const uint  if_label 
) const

compute vertex separator between subgraphs left and right (also defined by label) and put nodes into vertex_sep