Graph Algorithms

Graph algorithms based on igraph operating on a netlist graph abstraction.

graph_algorithm.get_all_shortest_paths(*args, **kwargs)

Overloaded function.

1. get_all_shortest_paths(graph: graph_algorithm.NetlistGraph, from_gate: hal_py.Gate, to_gates: List[hal_py.Gate], direction: graph_algorithm.NetlistGraph.Direction) -> Optional[List[List[int]]]

   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 list of vertices in the order of traversal.

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param hal_py.Gate from_gate

   The start gate of the shortest path.

   param list[hal_py.Gate] to_gates

   A list of end gates of the shortest path.

   param graph_algorithm.NetlistGraph.Direction 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.

   rtype

   list[list[int]] or None

2. get_all_shortest_paths(graph: graph_algorithm.NetlistGraph, from_vertex: int, to_vertices: List[int], direction: graph_algorithm.NetlistGraph.Direction) -> Optional[List[List[int]]]

   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 list of vertices in the order of traversal.

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param int from_vertex

   The start vertex of the shortest path.

   param list[int] to_vertices

   A list of end vertices of the shortest path.

   param graph_algorithm.NetlistGraph.Direction 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.

   rtype

   list[list[int]] or None

graph_algorithm.get_connected_components(graph: graph_algorithm.NetlistGraph, strong: bool, min_size: int = 0) → Optional[List[List[int]]]

Compute the (strongly) connected components of the specified graph. Returns each connected component as a list of vertices in the netlist graph.

Parameters

• graph (graph_algorithm.NetlistGraph) – The netlist graph.

• strong (bool) – Set True to compute strongly connected components, False otherwise.

• min_size (int) – Minimal size of a connected component to be part of the result. Set to 0 to include all components. Defaults to 0.

Returns

A list of strongly connected components on success, None otherwise.

Return type

list[list[int]] or None

graph_algorithm.get_neighborhood(*args, **kwargs)

Overloaded function.

1. get_neighborhood(graph: graph_algorithm.NetlistGraph, start_gates: List[hal_py.Gate], order: int, direction: graph_algorithm.NetlistGraph.Direction, min_dist: int = 0) -> Optional[List[List[int]]]

   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 list of vertices in the netlist graph.

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param list[hal_py.Gate] start_gates

   A list of gates for which to compute the neighborhood.

   param int order

   The order of the neighborhood to compute.

   param graph_algorithm.NetlistGraph.Direction direction

   The direction in which the neighborhood should be computed.

   param int min_dist

   The minimum distance of the vertices to include in the result.

   returns

   A list of neighborhoods of each of the provided start gates (in order) on success, None otherwise.

   rtype

   list[list[int]] or None

2. get_neighborhood(graph: graph_algorithm.NetlistGraph, start_vertices: List[int], order: int, direction: graph_algorithm.NetlistGraph.Direction, min_dist: int = 0) -> Optional[List[List[int]]]

   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 list of vertices in the netlist graph.

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param list[int] start_vertices

   A list of vertices for which to compute the neighborhood.

   param int order

   The order of the neighborhood to compute.

   param graph_algorithm.NetlistGraph.Direction direction

   The direction in which the neighborhood should be computed.

   param int min_dist

   The minimum distance of the vertices to include in the result.

   returns

   A list of neighborhoods of each of the provided start vertices (in order) on success, None otherwise.

   rtype

   list[list[int]] or None

graph_algorithm.get_shortest_paths(*args, **kwargs)

Overloaded function.

1. get_shortest_paths(graph: graph_algorithm.NetlistGraph, from_gate: hal_py.Gate, to_gates: List[hal_py.Gate], direction: graph_algorithm.NetlistGraph.Direction) -> Optional[List[List[int]]]

   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 list of vertices in the order of traversal.

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param hal_py.Gate from_gate

   The start gate of the shortest path.

   param list[hal_py.Gate] to_gates

   A list of end gates of the shortest path.

   param graph_algorithm.NetlistGraph.Direction 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.

   rtype

   list[list[int]] or None

2. get_shortest_paths(graph: graph_algorithm.NetlistGraph, from_vertex: int, to_vertices: List[int], direction: graph_algorithm.NetlistGraph.Direction) -> Optional[List[List[int]]]

   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 list of vertices in the order of traversal.

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param int from_vertex

   The start vertex of the shortest path.

   param list[int] to_vertices

   A list of end vertices of the shortest path.

   param graph_algorithm.NetlistGraph.Direction 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.

   rtype

   list[list[int]] or None

graph_algorithm.get_subgraph(*args, **kwargs)

Overloaded function.

1. get_subgraph(graph: graph_algorithm.NetlistGraph, subgraph_gates: List[hal_py.Gate]) -> Optional[graph_algorithm.NetlistGraph]

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

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param list[hal_py.Gate] subgraph_gates

   A list of gates that make up the subgraph.

   returns

   The subgraph as a new netlist graph on success, None otherwise.

   rtype

   graph_algorithm.NetlistGraph or None

2. get_subgraph(graph: graph_algorithm.NetlistGraph, subgraph_gates: Set[hal_py.Gate]) -> Optional[graph_algorithm.NetlistGraph]

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

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param set[hal_py.Gate] subgraph_gates

   A set of gates that make up the subgraph.

   returns

   The subgraph as a new netlist graph on success, None otherwise.

   rtype

   graph_algorithm.NetlistGraph or None

3. get_subgraph(graph: graph_algorithm.NetlistGraph, subgraph_vertices: List[int]) -> Optional[graph_algorithm.NetlistGraph]

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

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param list[int] subgraph_vertices

   A list of vertices that make up the subgraph.

   returns

   The subgraph as a new netlist graph on success, None otherwise.

   rtype

   graph_algorithm.NetlistGraph or None

4. get_subgraph(graph: graph_algorithm.NetlistGraph, subgraph_vertices: Set[int]) -> Optional[graph_algorithm.NetlistGraph]

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

   param graph_algorithm.NetlistGraph graph

   The netlist graph.

   param set[int] subgraph_vertices

   A set of vertices that make up the subgraph.

   returns

   The subgraph as a new netlist graph on success, None otherwise.

   rtype

   graph_algorithm.NetlistGraph or None

class graph_algorithm.NetlistGraph

Holds a directed graph corresponding to a netlist.

class Direction

The direction of exploration within the graph.

Members:

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.

property name

add_edges(*args, **kwargs)

Overloaded function.

1. add_edges(self: graph_algorithm.NetlistGraph, edges: List[Tuple[hal_py.Gate, hal_py.Gate]]) -> bool

   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.

   param list[tuple(hal_py.Gate,hal_py.Gate)] edges

   The edges to add as pairs of gates.

   returns

   True on success, False otherwise.

   rtype

   bool

2. add_edges(self: graph_algorithm.NetlistGraph, edges: List[Tuple[int, int]]) -> bool

   Add edges between the specified pairs of source and destination vertices to the netlist graph. The vertices must already exist in the graph.

   param list[tuple(int,int)] edges

   The edges to add as pairs of vertices.

   returns

   True on success, False otherwise.

   rtype

   bool

3. add_edges(self: graph_algorithm.NetlistGraph, edges: Dict[hal_py.Gate, Set[hal_py.Gate]]) -> bool

   Add edges between the specified pairs of source and destination gates to the netlist graph. The vertices must already exist in the graph.

   param dict[hal_py.Gate,set[hal_py.Gate]] edges

   The edges to add as a dict from source gate to its destination gates.

   returns

   True on success, False otherwise.

   rtype

   bool

copy(self: graph_algorithm.NetlistGraph) → graph_algorithm.NetlistGraph

Create a deep copy of the netlist graph.

Returns

The copied netlist graph on success, None otherwise.

Return type

graph_algorithm.NetlistGraph or None

delete_edges(*args, **kwargs)

Overloaded function.

1. delete_edges(self: graph_algorithm.NetlistGraph, edges: List[Tuple[hal_py.Gate, hal_py.Gate]]) -> bool

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

   param list[tuple(hal_py.Gate,hal_py.Gate)] edges

   The edges to delete as pairs of gates.

   returns

   True on success, False otherwise.

   rtype

   bool

2. delete_edges(self: graph_algorithm.NetlistGraph, edges: List[Tuple[int, int]]) -> bool

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

   param list[tuple(int,int)] edges

   The edges to delete as pairs of vertices.

   returns

   True on success, False otherwise.

   rtype

   bool

static from_netlist(nl: hal_py.Netlist, create_dummy_vertices: bool = False, filter: Callable[[hal_py.Net], bool] = None) → graph_algorithm.NetlistGraph

Create a directed graph from a netlist. Optionally create dummy nodes at nets missing a source or destination. An optional filter can be applied to exclude undesired edges.

param hal_py.Netlist nl

The netlist.

param bool create_dummy_vertices

Set True to create dummy vertices, False otherwise. Defaults to False.

param lambda filter

An optional filter that is evaluated on every net of the netlist. Defaults to None.

returns

The netlist graph on success, None otherwise.

rtype

graph_algorithm.NetlistGraph or None

static from_netlist_no_edges(nl: hal_py.Netlist, gates: List[hal_py.Gate] = []) → graph_algorithm.NetlistGraph

Create an empty directed graph from a netlist, i.e., vertices for all gates are created, but no edges are added.

param hal_py.Netlist nl

The netlist.

param list[hal_py.Gate] gates

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

returns

The netlist graph on success, None otherwise.

rtype

graph_algorithm.NetlistGraph or None

get_edges(self: graph_algorithm.NetlistGraph) → Optional[List[Tuple[int, int]]]

Get the edges between vertices in the netlist graph.

Returns

A list of edges on success, None otherwise.

Return type

list[tuple(int,int)] or None

get_edges_in_netlist(self: graph_algorithm.NetlistGraph) → Optional[List[Tuple[hal_py.Gate, hal_py.Gate]]]

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

Returns

A list of edges on success, None otherwise.

Return type

list[tuple(hal_py.Gate,hal_py.Gate)] or None

get_gate_from_vertex(self: graph_algorithm.NetlistGraph, vertex: int) → hal_py.Gate

Get the gates corresponding to the specified vertex.

Parameters

vertex (int) – A vertex.

Returns

A gate on success, None otherwise.

Return type

hal_py.Gate or None

get_gates_from_vertices(*args, **kwargs)

Overloaded function.

1. get_gates_from_vertices(self: graph_algorithm.NetlistGraph, vertices: List[int]) -> Optional[List[hal_py.Gate]]

   Get the gates corresponding to the specified list of vertices. The result may contain None for dummy vertices.

   param list[int] vertices

   A list of vertices.

   returns

   A list of gates on success, None otherwise.

   rtype

   list[hal_py.Gate] or None

2. get_gates_from_vertices(self: graph_algorithm.NetlistGraph, vertices: Set[int]) -> Optional[List[hal_py.Gate]]

   Get the gates corresponding to the specified set of vertices. The result may contain None for dummy vertices.

   param set[int] vertices

   A set of vertices.

   returns

   A list of gates on success, None otherwise.

   rtype

   list[hal_py.Gate] or None

get_gates_set_from_vertices(*args, **kwargs)

Overloaded function.

1. get_gates_set_from_vertices(self: graph_algorithm.NetlistGraph, vertices: List[int]) -> Optional[Set[hal_py.Gate]]

   Get the gates corresponding to the specified list of vertices.

   param list[int] vertices

   A list of vertices.

   returns

   A list of gates on success, None otherwise.

   rtype

   set[hal_py.Gate] or None

2. get_gates_set_from_vertices(self: graph_algorithm.NetlistGraph, vertices: Set[int]) -> Optional[Set[hal_py.Gate]]

   Get the gates corresponding to the specified set of vertices.

   param set[int] vertices

   A set of vertices.

   returns

   A list of gates on success, None otherwise.

   rtype

   set[hal_py.Gate] or None

get_netlist(self: graph_algorithm.NetlistGraph) → hal_py.Netlist

Get the netlist associated with the netlist graph.

Returns

The netlist.

Return type

hal_py.Netlist

get_num_edges(self: graph_algorithm.NetlistGraph) → int

Get the number of edges in the netlist graph.

Returns

The number of edges in the netlist graph.

Return type

int

get_num_vertices(self: graph_algorithm.NetlistGraph, only_connected: bool = False) → int

Get the number of vertices in the netlist graph.

Parameters

only_connected (bool) – 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.

Return type

int

get_vertex_from_gate(self: graph_algorithm.NetlistGraph, g: hal_py.Gate) → Optional[int]

Get the vertex corresponding to the specified gate.

Parameters

g (hal_py.Gate) – A gate.

Returns

A vertex on success, None otherwise.

Return type

int or None

get_vertices(self: graph_algorithm.NetlistGraph, only_connected: bool = False) → Optional[List[int]]

Get the vertices in the netlist graph.

Parameters

only_connected (bool) – Set True to only return vertices connected to at least one edge, False otherwise. Defaults to False.

Returns

A list of vertices on success, None otherwise.

Return type

list[int] or None

get_vertices_from_gates(*args, **kwargs)

Overloaded function.

1. get_vertices_from_gates(self: graph_algorithm.NetlistGraph, gates: List[hal_py.Gate]) -> Optional[List[int]]

   Get the vertices corresponding to the specified list of gates.

   param list[hal_py.Gate] gates

   A list of gates.

   returns

   A list of vertices on success, None otherwise.

   rtype

   list[int] or None

2. get_vertices_from_gates(self: graph_algorithm.NetlistGraph, gates: Set[hal_py.Gate]) -> Optional[List[int]]

   Get the vertices corresponding to the specified set of gates.

   param set[hal_py.Gate] gates

   A set of gates.

   returns

   A list of vertices on success, None otherwise.

   rtype

   list[int] or None

print(self: graph_algorithm.NetlistGraph) → None

Print the edge list of the graph to stdout.

class graph_algorithm.GraphAlgorithmPlugin

property dependencies

A set of plugin names that this plugin depends on.

Type

set[str]

property description

The description of the plugin.

Type

str

get_dependencies(self: graph_algorithm.GraphAlgorithmPlugin) → Set[str]

Get a set of plugin names that this plugin depends on.

Returns

A set of plugin names that this plugin depends on.

Return type

set[str]

get_description(self: graph_algorithm.GraphAlgorithmPlugin) → str

Get the description of the plugin.

Returns

The description of the plugin.

Return type

str

get_name(self: graph_algorithm.GraphAlgorithmPlugin) → str

Get the name of the plugin.

Returns

The name of the plugin.

Return type

str

get_version(self: graph_algorithm.GraphAlgorithmPlugin) → str

Get the version of the plugin.

Returns

The version of the plugin.

Return type

str

property name

The name of the plugin.

Type

str

property version

The version of the plugin.

Type

str