Saha Partition

This module provides a convenient interface to bispy.saha.saha.

Summary

SahaPartition	A convenient class to recompute incrementally the maximum bisimulation using Saha's algorithm.
saha	Returns an instance of the class SahaPartition which can be used to recompute the maximum bisimulation incrementally.

Code documentation

class SahaPartition(qblocks, vertexes, node_to_idx)

A convenient class to recompute incrementally the maximum bisimulation using Saha’s algorithm. Create instances using saha().

Parameters

• qblocks (List[_QBlock]) – The current partition of the nodes of the graph.

• qblocks – Nodes in the graph.

• node_to_idx (Dict[Any, int]) – A dict which maps nodes from the original graph to nodes of the isomorphic integer graph (see bispy.utilities.graph_normalization).

add_edge(edge, verbose=True)

Add a new edge to the graph, and recompute its maximum bisimulation incrementally.

Parameters

• edge (Tuple[Any, Any]) – The new edge (the first item is the source, the second item is the destination).

• verbose – If True, this methods returns the new maximum bisimulation after the addition of the new edge. Disabling this feature may increase performance (an additive factor \(\Theta(|V|)\) is saved). Defaults to True.

Return type

Optional[List[Tuple[Any]]]

Returns

The maximim bisimulation after the addition of the new edge if verbose is True.

add_edges(edges, verbose=True)

Add multiple edges and compute the maximum bisimulation incrementally.

Parameters

• edges (List[Tuple[Any, Any]]) – A list of edges, represented by 2-tuples.

• verbose (bool) – If True, the maximum bisimulation will be returned after the last iteration. Otherwise the method returns None. Defaults to True.

Return type

Optional[List[Tuple[Any]]]

Returns

The maximim bisimulation after the addition of the last edge if verbose is True.

saha(graph, initial_partition=None, is_integer_graph=False)

Returns an instance of the class SahaPartition which can be used to recompute the maximum bisimulation incrementally.

Parameters

• graph – The initial graph.

• is_integer_graph – If True, the function assumes that the graph is integer, and skips the integer check (may slightly improve performance). Defaults to False.

Initial_partition

The initial partition, or labeling set. This is not the partition from which we start, but an indication of which nodes cannot be bisimilar. Defaultsto None, in which case the trivial labeling set (one block which contains all the nodes) is used.

Return type

SahaPartition