A directed graph corresponding to a netlist. More...

#include <netlist_graph.h>

Collaboration diagram for hal::graph_algorithm::NetlistGraph:

Public Types
enum class	Direction { NONE , IN , OUT , ALL }
	The direction of exploration within the graph. More...

Public Member Functions
	NetlistGraph (Netlist nl, igraph_t &&graph, std::unordered_map< u32, Gate > &&nodes_to_gates)
	Construct a netlist graph from a netlist, an `igraph` graph object, and a map from graph nodes to HAL gates. More...

	~NetlistGraph ()
	Default destructor for `NetlistGraph`. More...

Result< std::unique_ptr< NetlistGraph > >	copy () const
	Create a deep copy of the netlist graph. More...

Netlist *	get_netlist () const
	Get the netlist associated with the netlist graph. More...

igraph_t *	get_graph () const
	Get the graph object of the netlist graph. More...

Result< std::vector< Gate * > >	get_gates_from_vertices (const std::vector< u32 > &vertices) const
	Get the gates corresponding to the specified vertices. More...

Result< std::vector< Gate * > >	get_gates_from_vertices (const std::set< u32 > &vertices) const
	Get the gates corresponding to the specified vertices. More...

Result< std::vector< Gate * > >	get_gates_from_vertices_igraph (const igraph_vector_int_t *vertices) const
	Get the gates corresponding to the specified vertices. More...

Result< std::set< Gate * > >	get_gates_set_from_vertices (const std::vector< u32 > &vertices) const
	Get the gates corresponding to the specified vertices. More...

Result< std::set< Gate * > >	get_gates_set_from_vertices (const std::set< u32 > &vertices) const
	Get the gates corresponding to the specified vertices. More...

Result< std::set< Gate * > >	get_gates_set_from_vertices_igraph (const igraph_vector_int_t *vertices) const
	Get the gates corresponding to the specified vertices. More...

Result< Gate * >	get_gate_from_vertex (const u32 vertex) const
	Get the gate corresponding to the specified vertex. More...

Result< std::vector< u32 > >	get_vertices_from_gates (const std::vector< Gate * > &gates) const
	Get the vertices corresponding to the specified gates. More...

Result< std::vector< u32 > >	get_vertices_from_gates (const std::set< Gate * > &gates) const
	Get the vertices corresponding to the specified gates. More...

Result< igraph_vector_int_t >	get_vertices_from_gates_igraph (const std::vector< Gate * > &gates) const
	Get the vertices corresponding to the specified gates. More...

Result< igraph_vector_int_t >	get_vertices_from_gates_igraph (const std::set< Gate * > &gates) const
	Get the vertices corresponding to the specified gates. More...

Result< u32 >	get_vertex_from_gate (Gate *g) const
	Get the vertex corresponding to the specified gate. More...

u32	get_num_vertices (bool only_connected=false) const
	Get the number of vertices in the netlist graph. More...

u32	get_num_edges () const
	Get the number of edges in the netlist graph. More...

Result< std::vector< u32 > >	get_vertices (bool only_connected=false) const
	Get the vertices in the netlist graph. More...

Result< std::vector< std::pair< u32, u32 > > >	get_edges () const
	Get the edges between vertices in the netlist graph. More...

Result< std::vector< std::pair< Gate , Gate > > >	get_edges_in_netlist () const
	Get the edges between gates in the netlist corresponding to the netlist graph. More...

Result< std::monostate >	add_edges (const std::vector< std::pair< Gate , Gate >> &edges)
	Add edges between the specified pairs of source and destination gates to the netlist graph. More...

Result< std::monostate >	add_edges (const std::vector< std::pair< u32, u32 >> &edges)
	Add edges between the specified pairs of source and destination vertices to the netlist graph. More...

Result< std::monostate >	add_edges (const std::map< Gate , std::set< Gate >> &edges)
	Add edges between the specified pairs of source and destination gates to the netlist graph. More...

Result< std::monostate >	delete_edges (const std::vector< std::pair< Gate , Gate >> &edges)
	Delete edges between the specified pairs of source and destination gates from the netlist graph. More...

Result< std::monostate >	delete_edges (const std::vector< std::pair< u32, u32 >> &edges)
	Delete edges between the specified pairs of source and destination vertices from the netlist graph. More...

void	print () const
	Print the edge list of the graph to stdout. More...

Static Public Member Functions
static Result< std::unique_ptr< NetlistGraph > >	from_netlist (Netlist nl, bool create_dummy_vertices=false, const std::function< bool(const Net )> &filter=nullptr)
	Create a directed graph from a netlist. More...

static Result< std::unique_ptr< NetlistGraph > >	from_netlist_no_edges (Netlist nl, const std::vector< Gate > &gates={})
	Create an empty directed graph from a netlist. More...

Detailed Description

A directed graph corresponding to a netlist.

This class holds all information on a netlist graph that corresponds to a gate-level netlist and provides functions to access and operate on it.

Definition at line 56 of file netlist_graph.h.

Member Enumeration Documentation

◆ Direction

enum hal::graph_algorithm::NetlistGraph::Direction

strong

The direction of exploration within the graph.

Enumerator
NONE	No direction, invalid default setting.
IN	Explore through the inputs of the current node, i.e., traverse backwards.
OUT	Explore through the outputs of the current node, i.e., traverse forwards.
ALL	Explore in both directions, i.e., treat the graph as undirected.

Definition at line 63 of file netlist_graph.h.

Constructor & Destructor Documentation

◆ NetlistGraph()

hal::graph_algorithm::NetlistGraph::NetlistGraph	(	Netlist *	nl,
		igraph_t &&	graph,
		std::unordered_map< u32, Gate * > &&	nodes_to_gates
	)

Construct a netlist graph from a netlist, an igraph graph object, and a map from graph nodes to HAL gates.

Parameters

[in]	nl	- The netlist.
[in]	graph	- The igrapg graph object.
[in]	nodes_to_gates	- A map from nodes to gates.

Definition at line 17 of file netlist_graph.cpp.

◆ ~NetlistGraph()

hal::graph_algorithm::NetlistGraph::~NetlistGraph ( )

Default destructor for NetlistGraph.

Definition at line 30 of file netlist_graph.cpp.

Member Function Documentation

◆ add_edges() [1/3]

Result< std::monostate > hal::graph_algorithm::NetlistGraph::add_edges ( const std::map< Gate *, std::set< Gate * >> & edges )

Add edges between the specified pairs of source and destination gates to the netlist graph.

The vertices must already exist in the graph.

Parameters

[in] edges - The edges to add as a map from source gate to its destination gates.

Returns: OK on success, an error otherwise.

Definition at line 732 of file netlist_graph.cpp.

References ERR, hal::Netlist::get_id(), and OK.

◆ add_edges() [2/3]

Result< std::monostate > hal::graph_algorithm::NetlistGraph::add_edges ( const std::vector< std::pair< Gate *, Gate * >> & edges )

Add edges between the specified pairs of source and destination gates to the netlist graph.

The gates must already correspond to vertices in the graph.

Parameters

[in] edges - The edges to add as pairs of gates.

Returns: OK on success, an error otherwise.

Definition at line 652 of file netlist_graph.cpp.

References ERR, hal::Netlist::get_id(), and OK.

◆ add_edges() [3/3]

Result< std::monostate > hal::graph_algorithm::NetlistGraph::add_edges ( const std::vector< std::pair< u32, u32 >> & edges )

Add edges between the specified pairs of source and destination vertices to the netlist graph.

The vertices must already exist in the graph.

Parameters

[in] edges - The edges to add as pairs of vertices.

Returns: OK on success, an error otherwise.

Definition at line 695 of file netlist_graph.cpp.

References ERR, hal::Netlist::get_id(), and OK.

◆ copy()

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::NetlistGraph::copy ( ) const

Create a deep copy of the netlist graph.

Returns: The copied netlist graph on success, an error otherwise.

Definition at line 189 of file netlist_graph.cpp.

References ERR, and OK.

◆ delete_edges() [1/2]

Result< std::monostate > hal::graph_algorithm::NetlistGraph::delete_edges ( const std::vector< std::pair< Gate *, Gate * >> & edges )

Delete edges between the specified pairs of source and destination gates from the netlist graph.

Parameters

[in] edges - The edges to delete as pairs of gates.

Returns: OK on success, an error otherwise.

Definition at line 786 of file netlist_graph.cpp.

References ERR, hal::Netlist::get_id(), and OK.

◆ delete_edges() [2/2]

Result< std::monostate > hal::graph_algorithm::NetlistGraph::delete_edges ( const std::vector< std::pair< u32, u32 >> & edges )

Delete edges between the specified pairs of source and destination vertices from the netlist graph.

Parameters

[in] edges - The edges to delete as pairs of vertices.

Returns: OK on success, an error otherwise.

Definition at line 842 of file netlist_graph.cpp.

References ERR, hal::Netlist::get_id(), and OK.

◆ from_netlist()

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::NetlistGraph::from_netlist	(	Netlist *	nl,
		bool	create_dummy_vertices = `false`,
		const std::function< bool(const Net *)> &	filter = `nullptr`
	)

static

Create a directed graph from a netlist.

Optionally create dummy vertices at nets missing a source or destination. An optional filter can be applied to exclude undesired edges.

Parameters

[in]	nl	- The netlist.
[in]	create_dummy_vertices	- Set `true` to create dummy vertices, `false` otherwise. Defaults to `false`.
[in]	filter	- An optional filter that is evaluated on every net of the netlist. Defaults to `nullptr`.

Returns: The netlist graph on success, an error otherwise.

Definition at line 35 of file netlist_graph.cpp.

References ERR, test_plugin::g, net, and OK.

Referenced by hal::PYBIND11_PLUGIN().

◆ from_netlist_no_edges()

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::NetlistGraph::from_netlist_no_edges	(	Netlist *	nl,
		const std::vector< Gate * > &	gates = `{}`
	)

static

Create an empty directed graph from a netlist.

Vertices for all gates are created, but no edges are added.

Parameters

[in]	nl	- The netlist.
[in]	gates	- The gates to include in the graph. If omitted, all gates of the netlist will be included.

Returns: The netlist graph on success, an error otherwise.

Definition at line 160 of file netlist_graph.cpp.

References ERR, test_plugin::g, and OK.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_edges()

Result< std::vector< std::pair< u32, u32 > > > hal::graph_algorithm::NetlistGraph::get_edges ( ) const

Get the edges between vertices in the netlist graph.

Returns: A vector of edges on success, an error otherwise.

Definition at line 573 of file netlist_graph.cpp.

References ERR, and OK.

◆ get_edges_in_netlist()

Result< std::vector< std::pair< Gate *, Gate * > > > hal::graph_algorithm::NetlistGraph::get_edges_in_netlist ( ) const

Get the edges between gates in the netlist corresponding to the netlist graph.

Returns: A vector of edges on success, an error otherwise.

Definition at line 601 of file netlist_graph.cpp.

References ERR, log_warning, and OK.

◆ get_gate_from_vertex()

Result< Gate * > hal::graph_algorithm::NetlistGraph::get_gate_from_vertex ( const u32 vertex ) const

Get the gate corresponding to the specified vertex.

Parameters

[in] vertex - A vertex.

Returns: A gates on success, an error otherwise.

Definition at line 360 of file netlist_graph.cpp.

References ERR, get_gates_from_vertices(), and OK.

◆ get_gates_from_vertices() [1/2]

Result< std::vector< Gate * > > hal::graph_algorithm::NetlistGraph::get_gates_from_vertices ( const std::set< u32 > & vertices ) const

Get the gates corresponding to the specified vertices.

The result may contain nullptr for dummy vertices.

Parameters

[in] vertices - A set of vertices.

Returns: A vector of gates on success, an error otherwise.

Definition at line 238 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), log_warning, and OK.

◆ get_gates_from_vertices() [2/2]

Result< std::vector< Gate * > > hal::graph_algorithm::NetlistGraph::get_gates_from_vertices ( const std::vector< u32 > & vertices ) const

Get the gates corresponding to the specified vertices.

The result may contain nullptr for dummy vertices.

Parameters

[in] vertices - A vector of vertices.

Returns: A vector of gates on success, an error otherwise.

Definition at line 215 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), log_warning, and OK.

Referenced by get_gate_from_vertex().

◆ get_gates_from_vertices_igraph()

Result< std::vector< Gate * > > hal::graph_algorithm::NetlistGraph::get_gates_from_vertices_igraph ( const igraph_vector_int_t * vertices ) const

Get the gates corresponding to the specified vertices.

The result may contain nullptr for dummy vertices.

Parameters

[in] vertices - An igraph vector of vertices.

Returns: A vector of gates on success, an error otherwise.

Definition at line 261 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), log_warning, and OK.

Referenced by hal::graph_algorithm::get_subgraph_igraph().

◆ get_gates_set_from_vertices() [1/2]

Result< std::set< Gate * > > hal::graph_algorithm::NetlistGraph::get_gates_set_from_vertices ( const std::set< u32 > & vertices ) const

Get the gates corresponding to the specified vertices.

Parameters

[in] vertices - A set of vertices.

Returns: A set of gates on success, an error otherwise.

Definition at line 310 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), log_warning, and OK.

◆ get_gates_set_from_vertices() [2/2]

Result< std::set< Gate * > > hal::graph_algorithm::NetlistGraph::get_gates_set_from_vertices ( const std::vector< u32 > & vertices ) const

Get the gates corresponding to the specified vertices.

Parameters

[in] vertices - A vector of vertices.

Returns: A set of gates on success, an error otherwise.

Definition at line 286 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), log_warning, and OK.

◆ get_gates_set_from_vertices_igraph()

Result< std::set< Gate * > > hal::graph_algorithm::NetlistGraph::get_gates_set_from_vertices_igraph ( const igraph_vector_int_t * vertices ) const

Get the gates corresponding to the specified vertices.

Parameters

[in] vertices - An igraph vector of vertices.

Returns: A set of gates on success, an error otherwise.

Definition at line 334 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), log_warning, and OK.

◆ get_graph()

igraph_t * hal::graph_algorithm::NetlistGraph::get_graph ( ) const

Get the graph object of the netlist graph.

Returns: The graph object.

Definition at line 210 of file netlist_graph.cpp.

Referenced by hal::graph_algorithm::get_all_shortest_paths_igraph(), hal::graph_algorithm::get_connected_components(), hal::graph_algorithm::get_neighborhood_igraph(), hal::graph_algorithm::get_shortest_paths_igraph(), and hal::graph_algorithm::get_subgraph_igraph().

◆ get_netlist()

Netlist * hal::graph_algorithm::NetlistGraph::get_netlist ( ) const

Get the netlist associated with the netlist graph.

Returns: The netlist.

Definition at line 205 of file netlist_graph.cpp.

Referenced by hal::graph_algorithm::get_subgraph_igraph(), and hal::PYBIND11_PLUGIN().

◆ get_num_edges()

u32 hal::graph_algorithm::NetlistGraph::get_num_edges ( ) const

Get the number of edges in the netlist graph.

Returns: The number of edges in the netlist graph.

Definition at line 522 of file netlist_graph.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_num_vertices()

u32 hal::graph_algorithm::NetlistGraph::get_num_vertices ( bool only_connected = false ) const

Get the number of vertices in the netlist graph.

Parameters

[in] only_connected - Set true to only count vertices connected to at least one edge, false otherwise. Defaults to false.

Returns: The number of vertices in the netlist graph.

Definition at line 489 of file netlist_graph.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_vertex_from_gate()

Result< u32 > hal::graph_algorithm::NetlistGraph::get_vertex_from_gate ( Gate * g ) const

Get the vertex corresponding to the specified gate.

Parameters

[in] g - A gate.

Returns: A vertex on success, an error otherwise.

Definition at line 478 of file netlist_graph.cpp.

References ERR, test_plugin::g, get_vertices_from_gates(), and OK.

Referenced by hal::graph_algorithm::get_all_shortest_paths(), and hal::graph_algorithm::get_shortest_paths().

◆ get_vertices()

Result< std::vector< u32 > > hal::graph_algorithm::NetlistGraph::get_vertices ( bool only_connected = false ) const

Get the vertices in the netlist graph.

Parameters

[in] only_connected - Set true to only return vertices connected to at least one edge, false otherwise. Defaults to false.

Returns: A vector of vertices on success, an error otherwise.

Definition at line 527 of file netlist_graph.cpp.

References ERR, and OK.

◆ get_vertices_from_gates() [1/2]

Result< std::vector< u32 > > hal::graph_algorithm::NetlistGraph::get_vertices_from_gates ( const std::set< Gate * > & gates ) const

Get the vertices corresponding to the specified gates.

Parameters

[in] gates - A set of gates.

Returns: A vector of vertices on success, an error otherwise.

Definition at line 395 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), and OK.

◆ get_vertices_from_gates() [2/2]

Result< std::vector< u32 > > hal::graph_algorithm::NetlistGraph::get_vertices_from_gates ( const std::vector< Gate * > & gates ) const

Get the vertices corresponding to the specified gates.

Parameters

[in] gates - A vector of gates.

Returns: A vector of vertices on success, an error otherwise.

Definition at line 371 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), and OK.

Referenced by get_vertex_from_gate().

◆ get_vertices_from_gates_igraph() [1/2]

Result< igraph_vector_int_t > hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph ( const std::set< Gate * > & gates ) const

Get the vertices corresponding to the specified gates.

Parameters

[in] gates - A set of gates.

Returns: An igraph vector of vertices on success, an error otherwise.

Definition at line 446 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), and OK.

◆ get_vertices_from_gates_igraph() [2/2]

Result< igraph_vector_int_t > hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph ( const std::vector< Gate * > & gates ) const

Get the vertices corresponding to the specified gates.

Parameters

[in] gates - A vector of gates.

Returns: An igraph vector of vertices on success, an error otherwise.

Definition at line 417 of file netlist_graph.cpp.

References ERR, test_plugin::g, hal::Netlist::get_id(), and OK.

Referenced by hal::graph_algorithm::get_all_shortest_paths(), hal::graph_algorithm::get_neighborhood(), hal::graph_algorithm::get_shortest_paths(), and hal::graph_algorithm::get_subgraph().

◆ print()

void hal::graph_algorithm::NetlistGraph::print ( ) const

Print the edge list of the graph to stdout.

Definition at line 890 of file netlist_graph.cpp.

Referenced by hal::PYBIND11_PLUGIN().

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

/home/runner/work/hal/hal/plugins/graph_algorithm/include/graph_algorithm/netlist_graph.h
/home/runner/work/hal/hal/plugins/graph_algorithm/src/netlist_graph.cpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ Direction

Constructor & Destructor Documentation

◆ NetlistGraph()

◆ ~NetlistGraph()

Member Function Documentation

◆ add_edges() [1/3]

◆ add_edges() [2/3]

◆ add_edges() [3/3]

◆ copy()

◆ delete_edges() [1/2]

◆ delete_edges() [2/2]

◆ from_netlist()

◆ from_netlist_no_edges()

◆ get_edges()

◆ get_edges_in_netlist()

◆ get_gate_from_vertex()

◆ get_gates_from_vertices() [1/2]

◆ get_gates_from_vertices() [2/2]

◆ get_gates_from_vertices_igraph()

◆ get_gates_set_from_vertices() [1/2]

◆ get_gates_set_from_vertices() [2/2]

◆ get_gates_set_from_vertices_igraph()

◆ get_graph()

◆ get_netlist()

◆ get_num_edges()

◆ get_num_vertices()

◆ get_vertex_from_gate()

◆ get_vertices()

◆ get_vertices_from_gates() [1/2]

◆ get_vertices_from_gates() [2/2]

◆ get_vertices_from_gates_igraph() [1/2]

◆ get_vertices_from_gates_igraph() [2/2]

◆ print()