cprover
class_hierarchy_grapht Class Reference

Class hierarchy, represented using grapht and therefore suitable for use with generic graph algorithms. More...

#include <class_hierarchy.h>

Inheritance diagram for class_hierarchy_grapht:
[legend]
Collaboration diagram for class_hierarchy_grapht:
[legend]

Public Types

typedef std::unordered_map< irep_idt, node_indextnodes_by_namet
 Maps class identifiers onto node indices. More...
 
- Public Types inherited from grapht< class_hierarchy_graph_nodet >
typedef class_hierarchy_graph_nodet nodet
 
typedef nodet::edgest edgest
 
typedef std::vector< nodetnodest
 
typedef nodet::edget edget
 
typedef nodet::node_indext node_indext
 
typedef std::list< node_indextpatht
 

Public Member Functions

void populate (const symbol_tablet &)
 Populate the class hierarchy graph, such that there is a node for every struct type in the symbol table and an edge representing each superclass <-> subclass relationship, pointing from parent to child. More...
 
const nodes_by_nametget_nodes_by_class_identifier () const
 Get map from class identifier to node index. More...
 
- Public Member Functions inherited from grapht< class_hierarchy_graph_nodet >
node_indext add_node ()
 
void swap (grapht &other)
 
bool has_edge (node_indext i, node_indext j) const
 
const nodetoperator[] (node_indext n) const
 
nodetoperator[] (node_indext n)
 
void resize (node_indext s)
 
std::size_t size () const
 
bool empty () const
 
const edgestin (node_indext n) const
 
const edgestout (node_indext n) const
 
void add_edge (node_indext a, node_indext b)
 
void remove_edge (node_indext a, node_indext b)
 
edgetedge (node_indext a, node_indext b)
 
void add_undirected_edge (node_indext a, node_indext b)
 
void remove_undirected_edge (node_indext a, node_indext b)
 
void remove_in_edges (node_indext n)
 
void remove_out_edges (node_indext n)
 
void remove_edges (node_indext n)
 
void clear ()
 
void shortest_path (node_indext src, node_indext dest, patht &path) const
 
void shortest_loop (node_indext node, patht &path) const
 
void visit_reachable (node_indext src)
 
std::vector< node_indextget_reachable (node_indext src, bool forwards) const
 Run depth-first search on the graph, starting from a single source node. More...
 
std::vector< node_indextget_reachable (const std::vector< node_indext > &src, bool forwards) const
 Run depth-first search on the graph, starting from multiple source nodes. More...
 
void make_chordal ()
 
std::size_t connected_subgraphs (std::vector< node_indext > &subgraph_nr)
 
std::size_t SCCs (std::vector< node_indext > &subgraph_nr) const
 Computes strongly-connected components of a graph and yields a vector expressing a mapping from nodes to components indices. More...
 
bool is_dag () const
 
std::list< node_indexttopsort () const
 Find a topological order of the nodes if graph is DAG, return empty list for non-DAG or empty graph. More...
 
std::vector< node_indextget_successors (const node_indext &n) const
 
void output_dot (std::ostream &out) const
 
void for_each_successor (const node_indext &n, std::function< void(const node_indext &)> f) const
 

Private Attributes

nodes_by_namet nodes_by_name
 Maps class identifiers onto node indices. More...
 

Additional Inherited Members

- Protected Member Functions inherited from grapht< class_hierarchy_graph_nodet >
void shortest_path (node_indext src, node_indext dest, patht &path, bool non_trivial) const
 
void tarjan (class tarjant &t, node_indext v) const
 
- Protected Attributes inherited from grapht< class_hierarchy_graph_nodet >
nodest nodes
 

Detailed Description

Class hierarchy, represented using grapht and therefore suitable for use with generic graph algorithms.

Definition at line 89 of file class_hierarchy.h.

Member Typedef Documentation

◆ nodes_by_namet

Maps class identifiers onto node indices.

Definition at line 93 of file class_hierarchy.h.

Member Function Documentation

◆ get_nodes_by_class_identifier()

const nodes_by_namet& class_hierarchy_grapht::get_nodes_by_class_identifier ( ) const
inline

Get map from class identifier to node index.

Returns
map from class identifier to node index

Definition at line 99 of file class_hierarchy.h.

References nodes_by_name.

◆ populate()

void class_hierarchy_grapht::populate ( const symbol_tablet symbol_table)

Populate the class hierarchy graph, such that there is a node for every struct type in the symbol table and an edge representing each superclass <-> subclass relationship, pointing from parent to child.

Parameters
symbol_tableglobal symbol table, which will be searched for struct types.

Definition at line 58 of file class_hierarchy.cpp.

References grapht< class_hierarchy_graph_nodet >::add_edge(), grapht< class_hierarchy_graph_nodet >::add_node(), class_typet::bases(), dstringt::empty(), nodes_by_name, symbol_table_baset::symbols, to_class_type(), and to_symbol_type().

Referenced by create_static_initializer_wrappers().

Member Data Documentation

◆ nodes_by_name

nodes_by_namet class_hierarchy_grapht::nodes_by_name
private

Maps class identifiers onto node indices.

Definition at line 106 of file class_hierarchy.h.

Referenced by get_nodes_by_class_identifier(), and populate().


The documentation for this class was generated from the following files: