Classes
class	NetlistGraph
	A directed graph corresponding to a netlist. More...

Functions
Result< std::vector< std::vector< u32 > > >	get_connected_components (const NetlistGraph *graph, bool strong, u32 min_size=0)
	Compute the (strongly) connected components of the specified graph. More...

Result< std::vector< std::vector< u32 > > >	get_neighborhood (NetlistGraph graph, const std::vector< Gate > &start_gates, u32 order, NetlistGraph::Direction direction, u32 min_dist=0)
	Compute the neighborhood of the given order for each of the specified gates within the given netlist graph. More...

Result< std::vector< std::vector< u32 > > >	get_neighborhood (NetlistGraph *graph, const std::vector< u32 > &start_vertices, u32 order, NetlistGraph::Direction direction, u32 min_dist=0)
	Compute the neighborhood of the given order for each of the specified vertices within the given netlist graph. More...

Result< std::vector< std::vector< u32 > > >	get_neighborhood_igraph (NetlistGraph graph, const igraph_vector_int_t start_vertices, u32 order, NetlistGraph::Direction direction, u32 min_dist=0)
	Compute the neighborhood of the given order for each of the specified vertices within the given netlist graph. More...

Result< std::vector< std::vector< u32 > > >	get_shortest_paths (NetlistGraph graph, Gate from_gate, const std::vector< Gate * > &to_gates, NetlistGraph::Direction direction)
	Compute a shortest path from the specified `from_gate` to each of the given `to_gates` by traversing in the provided direction. More...

Result< std::vector< std::vector< u32 > > >	get_shortest_paths (NetlistGraph *graph, u32 from_vertex, const std::vector< u32 > &to_vertices, NetlistGraph::Direction direction)
	Compute a shortest path from the specified `from_vertex` to each of the given `to_vertices` by traversing in the provided direction. More...

Result< std::vector< std::vector< u32 > > >	get_shortest_paths_igraph (NetlistGraph graph, u32 from_vertex, const igraph_vector_int_t to_vertices, NetlistGraph::Direction direction)
	Compute a shortest path from the specified `from_vertex` to each of the given `to_vertices` by traversing in the provided direction. More...

Result< std::vector< std::vector< u32 > > >	get_all_shortest_paths (NetlistGraph graph, Gate from_gate, const std::vector< Gate * > &to_gates, NetlistGraph::Direction direction)
	Compute shortest paths from the specified `from_gate` to each of the given `to_gates` by traversing in the provided direction. More...

Result< std::vector< std::vector< u32 > > >	get_all_shortest_paths (NetlistGraph *graph, u32 from_vertex, const std::vector< u32 > &to_vertices, NetlistGraph::Direction direction)
	Compute shortest paths from the specified `from_vertex` to each of the given `to_vertices` by traversing in the provided direction. More...

Result< std::vector< std::vector< u32 > > >	get_all_shortest_paths_igraph (NetlistGraph graph, u32 from_vertex, const igraph_vector_int_t to_vertices, NetlistGraph::Direction direction)
	Compute shortest paths from the specified `from_vertex` to each of the given `to_vertices` by traversing in the provided direction. Returns all shortest paths for each end gate. Each shortest path is given as a vector of vertices in the order of traversal. More...

Result< std::unique_ptr< NetlistGraph > >	get_subgraph (const NetlistGraph graph, const std::vector< Gate > &subgraph_gates)
	Compute the subgraph induced by the specified gates, including all edges between the corresponding vertices. More...

Result< std::unique_ptr< NetlistGraph > >	get_subgraph (const NetlistGraph graph, const std::set< Gate > &subgraph_gates)
	Compute the subgraph induced by the specified gates, including all edges between the corresponding vertices. More...

Result< std::unique_ptr< NetlistGraph > >	get_subgraph (const NetlistGraph *graph, const std::vector< u32 > &subgraph_vertices)
	Compute the subgraph induced by the specified vertices, including all edges between these vertices. More...

Result< std::unique_ptr< NetlistGraph > >	get_subgraph (const NetlistGraph *graph, const std::set< u32 > &subgraph_vertices)
	Compute the subgraph induced by the specified vertices, including all edges between these vertices. More...

Result< std::unique_ptr< NetlistGraph > >	get_subgraph_igraph (const NetlistGraph graph, const igraph_vector_int_t subgraph_vertices)
	Compute the subgraph induced by the specified vertices, including all edges between these vertices. More...

Function Documentation

◆ get_all_shortest_paths() [1/2]

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_all_shortest_paths	(	NetlistGraph *	graph,
		Gate *	from_gate,
		const std::vector< Gate * > &	to_gates,
		NetlistGraph::Direction	direction
	)

Compute shortest paths from the specified from_gate to each of the given to_gates by traversing in the provided direction.

Returns all shortest paths for each end gate. Each shortest path is given as a vector of vertices in the order of traversal.

Parameters

[in]	graph	- The netlist graph.
[in]	from_gate	- The start gate of the shortest path.
[in]	to_gates	- A vector of end gates of the shortest path.
[in]	direction	- The direction in which to compute the shortest paths starting at the `from_gate`.

Returns: The shortest paths in order of the to_gates on success, an error otherwise.

Definition at line 152 of file shortest_path.cpp.

References direction, ERR, get_all_shortest_paths_igraph(), hal::graph_algorithm::NetlistGraph::get_vertex_from_gate(), and hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph().

Referenced by hal::PYBIND11_PLUGIN().

◆ get_all_shortest_paths() [2/2]

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_all_shortest_paths	(	NetlistGraph *	graph,
		u32	from_vertex,
		const std::vector< u32 > &	to_vertices,
		NetlistGraph::Direction	direction
	)

Compute shortest paths from the specified from_vertex to each of the given to_vertices by traversing in the provided direction.

Returns all shortest paths for each end gate. Each shortest path is given as a vector of vertices in the order of traversal.

Parameters

[in]	graph	- The netlist graph.
[in]	from_gate	- The start vertex of the shortest path.
[in]	to_gates	- A vector of end vertices of the shortest path.
[in]	direction	- The direction in which to compute the shortest paths starting at the `from_vertex`.

Returns: The shortest paths in order of the to_vertices on success, an error otherwise.

Definition at line 201 of file shortest_path.cpp.

References direction, ERR, and get_all_shortest_paths_igraph().

◆ get_all_shortest_paths_igraph()

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_all_shortest_paths_igraph	(	NetlistGraph *	graph,
		u32	from_vertex,
		const igraph_vector_int_t *	to_vertices,
		NetlistGraph::Direction	direction
	)

Compute shortest paths from the specified from_vertex to each of the given to_vertices by traversing in the provided direction. Returns all shortest paths for each end gate. Each shortest path is given as a vector of vertices in the order of traversal.

Parameters

[in]	graph	- The netlist graph.
[in]	from_gate	- The start vertex of the shortest path.
[in]	to_gates	- An igraph vector of end vertices of the shortest path.
[in]	direction	- The direction in which to compute the shortest paths starting at the `from_vertex`.

Returns: The shortest paths in order of the to_vertices on success, an error otherwise.

Definition at line 236 of file shortest_path.cpp.

References hal::graph_algorithm::NetlistGraph::ALL, direction, ERR, hal::graph_algorithm::NetlistGraph::get_graph(), hal::graph_algorithm::NetlistGraph::IN, hal::graph_algorithm::NetlistGraph::NONE, OK, and hal::graph_algorithm::NetlistGraph::OUT.

Referenced by get_all_shortest_paths().

◆ get_connected_components()

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_connected_components	(	const NetlistGraph *	graph,
		bool	strong,
		u32	min_size = `0`
	)

Compute the (strongly) connected components of the specified graph.

Returns each connected component as a vector of vertices in the netlist graph.

Parameters

[in]	graph	- The netlist graph.
[in]	strong	- Set `true` to compute strongly connected components, `false` otherwise.
[in]	min_size	- Minimal size of a connected component to be part of the result. Set to `0` to include all components. Defaults to `0`.

Returns: A vector of strongly connected components on success, an error otherwise.

Definition at line 11 of file components.cpp.

References ERR, hal::graph_algorithm::NetlistGraph::get_graph(), and OK.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_neighborhood() [1/2]

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_neighborhood	(	NetlistGraph *	graph,
		const std::vector< Gate * > &	start_gates,
		u32	order,
		NetlistGraph::Direction	direction,
		u32	min_dist = `0`
	)

Compute the neighborhood of the given order for each of the specified gates within the given netlist graph.

For order 0, only the vertex itself is returned. For order 1, the vertex itself and all vertices that are its direct predecessors and/or successors (depending on the specified direction). For order 2, the neighborhood of order 1 plus all direct predecessors and/or successors of the vertices in order 1 are returned, etc. Returns each neighborhood as a vector of vertices in the netlist graph.

Parameters

[in]	graph	- The netlist graph.
[in]	start_gates	- A vector of gates for which to compute the neighborhood.
[in]	order	- The order of the neighborhood to compute.
[in]	direction	- The direction in which the neighborhood should be computed.
[in]	min_dist	- The minimum distance of the vertices to include in the result.

Returns: A vector of neighborhoods of each of the provided start gates (in order) on success, an error otherwise.

Definition at line 9 of file neighborhood.cpp.

References direction, ERR, get_neighborhood_igraph(), and hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph().

Referenced by hal::PYBIND11_PLUGIN().

◆ get_neighborhood() [2/2]

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_neighborhood	(	NetlistGraph *	graph,
		const std::vector< u32 > &	start_vertices,
		u32	order,
		NetlistGraph::Direction	direction,
		u32	min_dist = `0`
	)

Compute the neighborhood of the given order for each of the specified vertices within the given netlist graph.

For order 0, only the vertex itself is returned. For order 1, the vertex itself and all vertices that are its direct predecessors and/or successors (depending on the specified direction). For order 2, the neighborhood of order 1 plus all direct predecessors and/or successors of the vertices in order 1 are returned, etc. Returns each neighborhood as a vector of vertices in the netlist graph.

Parameters

[in]	graph	- The netlist graph.
[in]	start_vertices	- A vector of vertices for which to compute the neighborhood.
[in]	order	- The order of the neighborhood to compute.
[in]	direction	- The direction in which the neighborhood should be computed.
[in]	min_dist	- The minimum distance of the vertices to include in the result.

Returns: A vector of neighborhoods of each of the provided start vertices (in order) on success, an error otherwise.

Definition at line 43 of file neighborhood.cpp.

References direction, ERR, and get_neighborhood_igraph().

◆ get_neighborhood_igraph()

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_neighborhood_igraph	(	NetlistGraph *	graph,
		const igraph_vector_int_t *	start_vertices,
		u32	order,
		NetlistGraph::Direction	direction,
		u32	min_dist = `0`
	)

Compute the neighborhood of the given order for each of the specified vertices within the given netlist graph.

For order 0, only the vertex itself is returned. For order 1, the vertex itself and all vertices that are its direct predecessors and/or successors (depending on the specified direction). For order 2, the neighborhood of order 1 plus all direct predecessors and/or successors of the vertices in order 1 are returned, etc. Returns each neighborhood as a vector of vertices in the netlist graph.

Parameters

[in]	graph	- The netlist graph.
[in]	start_vertices	- An igraph vector of vertices for which to compute the neighborhood.
[in]	order	- The order of the neighborhood to compute.
[in]	direction	- The direction in which the neighborhood should be computed.
[in]	min_dist	- The minimum distance of the vertices to include in the result.

Returns: A vector of neighborhoods of each of the provided start vertices (in order) on success, an error otherwise.

Definition at line 78 of file neighborhood.cpp.

References hal::graph_algorithm::NetlistGraph::ALL, direction, ERR, hal::graph_algorithm::NetlistGraph::get_graph(), hal::graph_algorithm::NetlistGraph::IN, hal::graph_algorithm::NetlistGraph::NONE, OK, and hal::graph_algorithm::NetlistGraph::OUT.

Referenced by get_neighborhood().

◆ get_shortest_paths() [1/2]

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_shortest_paths	(	NetlistGraph *	graph,
		Gate *	from_gate,
		const std::vector< Gate * > &	to_gates,
		NetlistGraph::Direction	direction
	)

Compute a shortest path from the specified from_gate to each of the given to_gates by traversing in the provided direction.

Returns one shortest path for each end gate, even if multiple shortest paths exist. Each shortest path is given as a vector of vertices in the order of traversal.

Parameters

[in]	graph	- The netlist graph.
[in]	from_gate	- The start gate of the shortest path.
[in]	to_gates	- A vector of end gates of the shortest path.
[in]	direction	- The direction in which to compute the shortest paths starting at the `from_gate`.

Returns: The shortest paths in order of the to_gates on success, an error otherwise.

Definition at line 10 of file shortest_path.cpp.

References direction, ERR, get_shortest_paths_igraph(), hal::graph_algorithm::NetlistGraph::get_vertex_from_gate(), and hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph().

Referenced by hal::PYBIND11_PLUGIN().

◆ get_shortest_paths() [2/2]

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_shortest_paths	(	NetlistGraph *	graph,
		u32	from_vertex,
		const std::vector< u32 > &	to_vertices,
		NetlistGraph::Direction	direction
	)

Compute a shortest path from the specified from_vertex to each of the given to_vertices by traversing in the provided direction.

Returns one shortest path for each end vertex, even if multiple shortest paths exist. Each shortest path is given as a vector of vertices in the order of traversal.

Parameters

[in]	graph	- The netlist graph.
[in]	from_gate	- The start vertex of the shortest path.
[in]	to_gates	- A vector of end vertices of the shortest path.
[in]	direction	- The direction in which to compute the shortest paths starting at the `from_vertex`.

Returns: The shortest paths in order of the to_vertices on success, an error otherwise.

Definition at line 59 of file shortest_path.cpp.

References direction, ERR, and get_shortest_paths_igraph().

◆ get_shortest_paths_igraph()

Result< std::vector< std::vector< u32 > > > hal::graph_algorithm::get_shortest_paths_igraph	(	NetlistGraph *	graph,
		u32	from_vertex,
		const igraph_vector_int_t *	to_vertices,
		NetlistGraph::Direction	direction
	)

Compute a shortest path from the specified from_vertex to each of the given to_vertices by traversing in the provided direction.

Returns one shortest path for each end vertex, even if multiple shortest paths exist. Each shortest path is given as a vector of vertices in the order of traversal.

Parameters

[in]	graph	- The netlist graph.
[in]	from_gate	- The start vertex of the shortest path.
[in]	to_gates	- An igraph vector of end vertices of the shortest path.
[in]	direction	- The direction in which to compute the shortest paths starting at the `from_vertex`.

Returns: The shortest paths in order of the to_vertices on success, an error otherwise.

Definition at line 94 of file shortest_path.cpp.

References hal::graph_algorithm::NetlistGraph::ALL, direction, ERR, hal::graph_algorithm::NetlistGraph::get_graph(), hal::graph_algorithm::NetlistGraph::IN, hal::graph_algorithm::NetlistGraph::NONE, OK, and hal::graph_algorithm::NetlistGraph::OUT.

Referenced by get_shortest_paths().

◆ get_subgraph() [1/4]

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::get_subgraph	(	const NetlistGraph *	graph,
		const std::set< Gate * > &	subgraph_gates
	)

Compute the subgraph induced by the specified gates, including all edges between the corresponding vertices.

Parameters

[in]	graph	- The netlist graph.
[in]	subgraph_gates	- A set of gates that make up the subgraph.

Returns: The subgraph as a new netlist graph on success, an error otherwise.

Definition at line 44 of file subgraph.cpp.

References ERR, get_subgraph_igraph(), and hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph().

◆ get_subgraph() [2/4]

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::get_subgraph	(	const NetlistGraph *	graph,
		const std::set< u32 > &	subgraph_vertices
	)

Compute the subgraph induced by the specified vertices, including all edges between these vertices.

Parameters

[in]	graph	- The netlist graph.
[in]	subgraph_vertices	- A set of vertices that make up the subgraph.

Returns: The subgraph as a new netlist graph on success, an error otherwise.

Definition at line 113 of file subgraph.cpp.

References ERR, and get_subgraph_igraph().

◆ get_subgraph() [3/4]

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::get_subgraph	(	const NetlistGraph *	graph,
		const std::vector< Gate * > &	subgraph_gates
	)

Compute the subgraph induced by the specified gates, including all edges between the corresponding vertices.

Parameters

[in]	graph	- The netlist graph.
[in]	subgraph_gates	- A vector of gates that make up the subgraph.

Returns: The subgraph as a new netlist graph on success, an error otherwise.

Definition at line 10 of file subgraph.cpp.

References ERR, get_subgraph_igraph(), and hal::graph_algorithm::NetlistGraph::get_vertices_from_gates_igraph().

Referenced by hal::PYBIND11_PLUGIN().

◆ get_subgraph() [4/4]

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::get_subgraph	(	const NetlistGraph *	graph,
		const std::vector< u32 > &	subgraph_vertices
	)

Compute the subgraph induced by the specified vertices, including all edges between these vertices.

Parameters

[in]	graph	- The netlist graph.
[in]	subgraph_vertices	- A vector of vertices that make up the subgraph.

Returns: The subgraph as a new netlist graph on success, an error otherwise.

Definition at line 78 of file subgraph.cpp.

References ERR, and get_subgraph_igraph().

◆ get_subgraph_igraph()

Result< std::unique_ptr< NetlistGraph > > hal::graph_algorithm::get_subgraph_igraph	(	const NetlistGraph *	graph,
		const igraph_vector_int_t *	subgraph_vertices
	)

Compute the subgraph induced by the specified vertices, including all edges between these vertices.

Parameters

[in]	graph	- The netlist graph.
[in]	subgraph_vertices	- An igraph vector of vertices that make up the subgraph.

Returns: The subgraph as a new netlist graph on success, an error otherwise.

Definition at line 150 of file subgraph.cpp.

References ERR, hal::graph_algorithm::NetlistGraph::get_gates_from_vertices_igraph(), hal::graph_algorithm::NetlistGraph::get_graph(), hal::graph_algorithm::NetlistGraph::get_netlist(), and OK.

Referenced by get_subgraph().

Classes

Functions

Function Documentation

◆ get_all_shortest_paths() [1/2]

◆ get_all_shortest_paths() [2/2]

◆ get_all_shortest_paths_igraph()

◆ get_connected_components()

◆ get_neighborhood() [1/2]

◆ get_neighborhood() [2/2]

◆ get_neighborhood_igraph()

◆ get_shortest_paths() [1/2]

◆ get_shortest_paths() [2/2]

◆ get_shortest_paths_igraph()

◆ get_subgraph() [1/4]

◆ get_subgraph() [2/4]

◆ get_subgraph() [3/4]

◆ get_subgraph() [4/4]

◆ get_subgraph_igraph()