Graph Algorithms

The graph algorithm plugin provides several algorithms used in graph theory based on the igraph framework's implementation. 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 a directed igraph object, where the gates represent the nodes/vertices and the nets the edges. The plugin can be easily extended since most of the igraph framework's algorithms usually only require the graph object as input.

The graph algorithm plugin is built 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 use 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))

Clustering algorithms

We implemented several wrappers for a wide range of different clustering algorithms. We currently support the louvain method, spinglass, multilevel and fast greedy. See the documentation for more calls.

Implementing further algorithms

The implementation of further algorithms based on the igraph representation is straightforward. It always follows the same pattern (example). The wrapper has to be implemented in C++ but can be called from python by implementing a pybind.

First, the igraph object has to be created, then the call to the igraph framework is prepared, and finally, the igraph output has to mapped back to the HAL. For easy conversion between the igraph and HAL world we provide helper functions (see get_igraph_directed and get_memberships_for_hal in plugin_graph_algorithm.h). Finally to use the function from the python shell or editor a pybind has to be added (see python_binding.cpp).