BisPy 0.1.2

Description

BisPy is a Python package for the computation of the maximum bisimulation of directed graphs. At the moment it supports the following algorithms:

• Paige-Tarjan
• Dovier-Piazza-Policriti
• Saha

An brief introduction to the problem can be found here.

Usage

Paige-Tarjan, Dovier-Piazza-Policriti

Compute the maximum bisimulation of a graph (represented by an object of type networkx.DiGraph):

> import networkx as nx
> from bispy import paige_tarjan, dovier_piazza_policriti

# we create the graph
> graph = networkx.balanced_tree(2,3)

# Paige-Tarjan's algorithm
> paige_tarjan(graph)
[(7, 8, 9, 10, 11, 12, 13, 14), (3, 4, 5, 6), (1, 2), (0,)]

# and Dovier-Piazza-Policriti's algorithm
> dovier_piazza_policriti(graph)
[(7, 8, 9, 10, 11, 12, 13, 14), (3, 4, 5, 6), (1, 2), (0,)]

More about the available features (like using a labeling set) is discussed in the documentation for Paige-Tarjan's and Dovier-Piazza-Policriti's algorithms.

Saha

The interface for using Saha's algorithm is a little bit different since we do not want to rebuild the BisPy representation of the graph from scratch.

> import networkx as nx
> from bispy import decorate_nx_graph, to_tuple_list, paige_tarjan_qblocks, saha

# we create the graph
> graph = networkx.balanced_tree(2,3)

# we build its BisPy representation
> vertexes, qblocks = decorate_nx_graph(graph)
# compute the maximum bisimulation. `maximum_bisimulation is a list of `_QBlock` objects
> maximum_bisimulation = paige_tarjan_qblocks(qblocks)

# from now on we can update the maximum bisimulation incrementally, everytime
# we add a new edge to the graph
> new_edges_list = random_edges_generator()
> for edge in new_edges_list:
>    maximum_bisimulation = saha(maximum_bisimulation, vertexes, edge)
>    # print the current maximum bisimulation
>    print(to_tuple_list(maximum_bisimulation))

Note that Saha's algorithm must be applied on a maximum bisimulation, otherwise it is going to return wrong results. This is why we called paige_tarjan_qblocks (which is just a version of Paige-Tarjan's algorithm which can be applied to the variable qblocks) before the call to Saha's algorithm.

You can read more about Saha's algorithm and the module graph_decorator on the documentation.

Dependencies and installation

BisPy requires requires the modules llist, networkx. The code is tested for Python 3, while compatibility with Python 2 is not guaranteed. It can be installed using pip or directly from the source code.

Documentation

We used Sphinx and ReadTheDocs for code documentation. You can view the documentation here.

Authors and acknowledgements

BisPy is currently developed and mantained by Francesco Andreuzzi. You can contact me at:

• andreuzzi.francesco at gmail.com
• fandreuz at sissa.it

License

See the LICENSE file for license rights and limitations (MIT).