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))

Clustering algorithms

We implemented several wrappers for a wide range of different clustering algorithm. We currently support the louvain method, spinglass, multilevel and fast greedy.

Implementing further algorithms

The implementation of further algorithms based on the igraph representation is straightforward and 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 created, then the call to the igraph framework 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).