HLIBpro  2.1
Classes | Public Member Functions | Protected Attributes | List of all members
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  TIterator
 Class for iterating through adjacent nodes. More...
 

Public Member Functions

 TGraph ()
 construct empty graph
 
 TGraph (const TSparseMatrix *S, const std::vector< bool > &nodemask)
 
virtual ~TGraph ()
 dtor
 
size_t n_nodes () const
 return number of nodes in graph
 
size_t n_edges () const
 return number of edges in graph
 
bool has_global_names () const
 return true, if graph stores global names
 
size_t degree (const node_t node) const
 return degree of node, e.g. number of incident edges
 
TIterator adj_nodes_iter (const node_t node) const
 return iterator to adjacent nodes of node
 
virtual void init (const size_t nnodes, const size_t nedges, const bool global=false)
 
std::vector< node_t > & adj_nodes ()
 return adjacency data
 
std::vector< idx_t > & adj_list_ptr ()
 return adjacency pointer data
 
std::vector< node_t > & global_name ()
 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
 
virtual TGraphrestrict (const TNodeSet &nodes) const
 restrict graph to nodes in nodes and store result in subgraph More...
 
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
 return false to show that Graph has no edge weights
 
virtual weight_t edge_weight (const idx_t) const
 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 ( 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

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

virtual void init ( const size_t  nnodes,
const size_t  nedges,
const bool  global = false 
)
inlinevirtual

initialise graph for nnnodes nodes and nedges edges

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

Reimplemented in TEWGraph.

virtual TGraph* restrict ( const TNodeSet nodes) const
virtual

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

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