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

#include </home/runner/work/hal/hal/plugins/graph_algorithm/include/graph_algorithm/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...

	NetlistGraph (const NetlistGraph &)=delete

NetlistGraph &	operator= (const NetlistGraph &)=delete

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 59 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 66 of file netlist_graph.h.

Constructor & Destructor Documentation

◆ NetlistGraph() [1/2]

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 34 of file netlist_graph.cpp.

◆ NetlistGraph() [2/2]

hal::graph_algorithm::NetlistGraph::NetlistGraph ( const NetlistGraph & )

delete

igraph_t is a plain C struct holding heap pointers, so the implicitly generated copy operations would bitwise-copy m_graph and leave two NetlistGraph objects aliasing the same graph internals – the destructor would then call igraph_destroy() on them twice, and the copy's m_graph_ptr would still point into the source object. Every factory hands out a std::unique_ptr<NetlistGraph>, so nothing is meant to copy a graph in the first place; deleting the copy operations makes that invariant explicit and enforced at compile time instead of relying on convention.

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 746 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 666 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 709 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 202 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 800 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 856 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 44 of file netlist_graph.cpp.

References ERR, net, and OK.

Referenced by hal::hawkeye::RoundCandidate::from_register_candidate(), and 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 171 of file netlist_graph.cpp.

References ERR, and OK.

Referenced by hal::hawkeye::detect_candidates(), and 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 587 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 615 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 374 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 252 of file netlist_graph.cpp.

References ERR, 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 229 of file netlist_graph.cpp.

References ERR, 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 275 of file netlist_graph.cpp.

References ERR, 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 324 of file netlist_graph.cpp.

References ERR, 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 300 of file netlist_graph.cpp.

References ERR, 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 348 of file netlist_graph.cpp.

References ERR, 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 224 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 219 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 536 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 503 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 492 of file netlist_graph.cpp.

References ERR, 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 541 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 409 of file netlist_graph.cpp.

References ERR, 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 385 of file netlist_graph.cpp.

References ERR, 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 460 of file netlist_graph.cpp.

References ERR, 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 431 of file netlist_graph.cpp.

References ERR, 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().

◆ operator=()

NetlistGraph& hal::graph_algorithm::NetlistGraph::operator= ( const NetlistGraph & )

delete

◆ print()

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

Print the edge list of the graph to stdout.

Definition at line 904 of file netlist_graph.cpp.

Referenced by hal::PYBIND11_PLUGIN().

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

plugins/graph_algorithm/include/graph_algorithm/netlist_graph.h
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() [1/2]

◆ ~NetlistGraph()

◆ NetlistGraph() [2/2]

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]

◆ operator=()

◆ print()