Graph Algorithms

The graph algorithm plugin provides several algorithms used in graph theory based on the igraph framework. The netlist is converted to NetlistGraph object that encapsulates an igraph object. The primary advantage of translating the netlist into a native graph object before executing respective algorithms is speed, as libraries such as igraph are optimized to perform such operations even on huge graphs efficiently. The gates of the netlist represent the nodes/vertices and the nets between gates are make up the edges. Vertices are represented by a range of consecutive integers starting at 0.

The graph_algorithm plugin is built by default and can be excluded from the build process using the -DPL_GRAPH_ALGORITHM=0 flag in the cmake command.

Converting a Netlist to a Graph

Converting a HAL netlist into a netlist graph is straight-forward using the NetlistGraph.from_netlist function. It will automatically translate all gates into vertices and all nets into edges and return a NetlistGraph object to operate on.

from hal_plugins import graph_algorithm

graph = graph_algorithm.NetlistGraph.from_netlist(netlist)

Now you can, for example, get the number of vertices and edges of the graph to check whether the translation is correct. Please note that nets with many sources or destinations will be translated into multiple edges.

num_v = graph.get_num_vertices()
num_e = graph.get_num_edges()

Translating Between Vertices and Gates

The plugin comes with various short-hand functions to translate between gates and vertices. To convert vertices to gates, one can use get_gate_from_vertex and get_gates_from_vertices. For the inverse translation from gates to vertices, get_vertex_from_gate and get_vertices_from_gates may be used.

g = graph.get_gate_from_vertex(3)                  # get a HAL gate corresponding to the given vertex ID
gs = graph.get_gates_from_vertices({3, 6, 9})      # get a list of HAL gates corresponding to the given vertex IDs
v = graph.get_vertex_from_gate(g0)                 # get a vertex ID corresponding to the given HAL gate
vs = graph.get_vertices_from_gates({g0, g1, g2})   # get a list of vertex IDs corresponding to the given HAL gates

Creating User-Defined Edges

The user may opt to not convert all nets of the netlist to edges, for example because they want to create edges only between flip-flops that are connected through combinational logic to create a flip-flop abstraction of the netlist. In such a case, they can create a graph containing only the gates of the netlist as vertices, but no edges in between them at all, using NetlistGraph.from_netlist_no_edges. Then, the user can create only the desired edges using add_edges by providing either pairs of vertices or gates.

graph = graph_algorithm.NetlistGraph.from_netlist_no_edges(netlist)
graph.add_edges([(1, 3), (2, 7)])       # add edges by specifying vertex pairs
graph.add_edges([(g0, g4), (g3, g6)])   # add edges by specifying gate pairs

Similarly, edges can also be deleted from a graph using delete_edges by providing either pairs of vertices or gates.

graph.delete_edges([(1, 3)])
graph.delete_edges([(g0, g4)])

Executing Graph Algorithms

So far, the graph_algorithm plugin implements algorithms to compute:

• (strongly) connected components
• neighborhoods
• shortest paths
• subgraphs

(Strongly) Connected Component

To compute connected components or strongly connected components, get_connected_components may be used. It takes as argument the netlist graph object and strong=False for (weakly) connected components and strong=True for strongly connected components. It returns a list of components with each component being a list of vertices.

comp_w = graph_algorithm.get_connected_components(graph, strong=False)   # compute (weakly) connected components
comp_s = graph_algorithm.get_connected_components(graph, strong=True)    # compute strongly connected components

Neighborhoods

The k-th neighborhood of a vertex are all the vertices that can be reached from that vertex in at most k steps. To compute the neighborhood of a multiple vertices at the same time, get_neighborhood may be used. The function takes as input the graph, a list of either start gates or vertices from which the neighborhoods shall be computed, the order of the neighborhoods to compute aka. the parameter k, and the direction. When choosing graph_algorithm.NetlistGraph.Direction.IN, the neighborhoods are explored toward the vertex inputs, for graph_algorithm.NetlistGraph.Direction.OUT they are explored toward the outputs of each vertex. Also, graph_algorithm.NetlistGraph.Direction.ALL may be specified to treat the graph as undirected. Furthermore, a min_dist parameter may be provided to discard all gates that can be reached with less than min_dist steps. A list of neighborhoods is returned, one for each start gate or vertex. Each neighborhood consists of a list of vertices.

# returns neighborhoods of order 5 for g2 and g9
neighs_1 = graph_algorithm.get_neighborhood(graph, start_gates=[g2, g9], order=5, direction=graph_algorithm.NetlistGraph.Direction.IN)

# returns neighborhoods of order 3 for vertices 3 and 7 with including all vertices of a minimal distance of 2
neighs_2 = graph_algorithm.get_neighborhood(graph, start_vertices=[3, 7], order=3, direction=graph_algorithm.NetlistGraph.Direction.OUT, min_dist=2)

Shortest Paths

Either one or all shortest paths starting at a from_gate and leading to one or many to_gates can be computed using get_shortest_paths or get_all_shortest_paths. If multiple to_gates are given, one (or all) shortest path is returned for each of the to_gates. Instead of gates, vertices may also be provided. Furthermore, a direction must be specified similar to Neighborhoods. A list of shortest paths is returned with each shortest path being a list of vertices.

# two shortest paths will be returned, one from g2 to g7 and one from g2 to g9
sps_1 = graph_algorithm.get_shortest_paths(graph, g2, [g7, g9], direction=graph_algorithm.NetlistGraph.Direction.OUT)

# all shortest paths from vertex 3 to 9 will be returned
sps_2 = graph_algorithm.get_all_shortest_paths(graph, 3, [9], direction=graph_algorithm.NetlistGraph.Direction.OUT)

Subgraph

A subgraph from an existing netlist graph can be computed using get_subgraph and by providing a list/set of gates/vertices that make up the subgraph. In all cases, a new NetlistGraph object corresponding to the same netlist is returned.

sg1 = graph_algorithm.get_subgraph(graph, {3, 5, 7, 8})   # subgraph from a set of vertices
sg2 = graph_algorithm.get_subgraph(graph, [3, 5, 7, 8])   # subgraph from a list of vertices
sg3 = graph_algorithm.get_subgraph(graph, {g3, g4, g5})   # subgraph from a set of gates
sg4 = graph_algorithm.get_subgraph(graph, [g3, g4, g5])   # subgraph from a list of gates

Additional Algorithms

The igraph framework provides a rich set of other graph algorithms that have not yet been added to HAL. However, the graph_algorithm plugin can be easily extended since most of igraph's algorithms only require the graph object as input, which is already available from within the NetlistGraph object. Many of the other utility functions required to prepare the parameters for these not-yet-supported algorithms are also readily available.