cprover
Loading...
Searching...
No Matches
call_grapht::directed_grapht Class Reference

Directed graph representation of this call graph. More...

#include <call_graph.h>

Inheritance diagram for call_grapht::directed_grapht:
Collaboration diagram for call_grapht::directed_grapht:

Public Types

typedef std::unordered_map< irep_idt, node_indextnodes_by_namet
 Type of the node name -> node index map.
Public Types inherited from grapht< function_nodet >
typedef function_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

std::optional< node_indextget_node_index (const irep_idt &function) const
 Find the graph node by function name.
const nodes_by_nametget_nodes_by_name () const
 Get the node name -> node index map.
Public Member Functions inherited from grapht< function_nodet >
node_indext add_node (arguments &&... values)
void swap (grapht &other)
bool has_edge (node_indext i, node_indext j) const
const nodetoperator[] (node_indext n) const
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.
void disconnect_unreachable (node_indext src)
 Removes any edges between nodes in a graph that are unreachable from a given start node.
std::vector< typename function_nodet::node_indext > depth_limited_search (typename function_nodet::node_indext src, std::size_t limit) const
 Run recursive depth-limited search on the graph, starting from multiple source nodes, to find the nodes reachable within n steps.
void make_chordal ()
 Ensure a graph is chordal (contains no 4+-cycles without an edge crossing the cycle) by adding extra edges.
std::size_t connected_subgraphs (std::vector< node_indext > &subgraph_nr)
 Find connected subgraphs in an undirected graph.
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.
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.
std::vector< node_indextget_predecessors (const node_indext &n) const
std::vector< node_indextget_successors (const node_indext &n) const
void output_dot (std::ostream &out) const
void for_each_predecessor (const node_indext &n, std::function< void(const node_indext &)> f) const
void for_each_successor (const node_indext &n, std::function< void(const node_indext &)> f) const

Private Attributes

std::unordered_map< irep_idt, node_indextnodes_by_name
 Maps function names onto node indices.

Friends

class call_grapht

Additional Inherited Members

Protected Member Functions inherited from grapht< function_nodet >
void tarjan (class tarjant &t, node_indext v) const
Protected Attributes inherited from grapht< function_nodet >
nodest nodes

Detailed Description

Directed graph representation of this call graph.

Definition at line 139 of file call_graph.h.

Member Typedef Documentation

◆ nodes_by_namet

Type of the node name -> node index map.

Definition at line 153 of file call_graph.h.

Member Function Documentation

◆ get_node_index()

std::optional< std::size_t > call_grapht::directed_grapht::get_node_index ( const irep_idt & function) const

Find the graph node by function name.

Parameters
functionfunction to find
Returns
none if function is not in this graph, or some index otherwise.

Definition at line 300 of file call_graph.cpp.

◆ get_nodes_by_name()

const nodes_by_namet & call_grapht::directed_grapht::get_nodes_by_name ( ) const
inline

Get the node name -> node index map.

Returns
node-by-name map

Definition at line 157 of file call_graph.h.

◆ call_grapht

friend class call_grapht
friend

Definition at line 141 of file call_graph.h.

Member Data Documentation

◆ nodes_by_name

std::unordered_map<irep_idt, node_indext> call_grapht::directed_grapht::nodes_by_name
private

Maps function names onto node indices.

Definition at line 144 of file call_graph.h.


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