Graph Algorithms

The graph algorithm plugin provides several algorithms used in graph theory, based on the implementation of the igraph framework. All functions in this plugin handle the interactions with igraph, so the user does not have to deal with the internal igraph functions and structures. The netlist is internally converted to an directed igraph object, where the gates represent the nodes/vertices and the nets the edges. The plugin can be easily extended, since most algorithms of the igraph framework usually only require the graph object as input.

The graph algorithm plugin is build automatically and usually does not need any extra flags during the build process. However to explicitly build or not build the plugin the user can make use of the -DPL_GRAPH_ALGORITHM=1 flag.

Loading the Plugin

Similar to all other plugins, the graph algorithm plugin can be loaded using the following Python snippet:

from hal_plugins import graph_algorithm

pl_ga = hal_py.plugin_manager.get_plugin_instance("graph_algorithm")

Executing different graph algorithms

All available algorithms with their different input parameters can be found in the documentation ( C++ / python )

Strongly Connected Components

The following snippet identifies strongly connected components using the igraph implementation. The function returns a list of lists containing the identified components. The output can for example be used to generate modules or groupings:

from hal_plugins import graph_algorithm
graph_algorithms = hal_py.plugin_manager.get_plugin_instance("graph_algorithm")

# delete all existing modules
for m in netlist.get_modules(): netlist.delete_module(m)

# get all strongly connected components
scc = graph_algorithms.get_strongly_connected_components(netlist)

# generate modules
counter = 0
for component in scc:
    if len(component) < 2: continue # note that single nodes form - per definition - a strongly connected component
    counter += 1
    netlist.create_module("candidate " + str(counter), netlist.get_top_module(), list(component))