Paige-Tarjan

To implement the algorithm we followed the pseudocode and the analysis provided in the following paper:

Paige, Robert, and Robert E. Tarjan.
"Three partition refinement algorithms."
SIAM Journal on Computing 16.6 (1987): 973-989.

Paige-Tarjan’s algorithm provides the first efficient algorithmic solution to the problem of the maximum bisimulation.

Summary

paige_tarjan	Compute the RSCP/maximum bisimulation of the given graph using Paige-Tarjan's algorithm, with the given initial partition (or labeling set, two vertexes in different blocks of the initial partition cannot be bisimilar).
paige_tarjan_qblocks	Apply the Paige-Tarjan algorithm to the partition \(Q\), which
extract_splitter	Given a compound block in the X partition, extract one of the blocks of the partition Q inside (the smallest among the first two blocks in the list).
build_block_counterimage	Given a block \(B \in Q\), construct the \(E^{-1}(B)\).
build_exclusive_B_counterimage	Given a block \(B \in Q\), generate the "exclusive counterimage" of \(B\), namely the set \(E^{-1}(B) - E^{-1}(S-B)\), where \(E\) is the edge relation (\(\to\)) of the graph.
split	Given a list of vertexes, use them as splitter set for the current partition \(Q\).
update_counts	After a block \(B \in Q\) has become a (non-compound) block of \(X\) on its own (it was removed from a compound block of \(X\)) we need to decrease by one the quantity count(x, \(S\)) (which is now count(x, \(S-B\))) for each vertex in \(E^{-1}(B)\).
refine	Perform a refinement step of the Paige-Tarjan algorithm.

Code documentation

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

Compute the RSCP/maximum bisimulation of the given graph using Paige-Tarjan’s algorithm, with the given initial partition (or labeling set, two vertexes in different blocks of the initial partition cannot be bisimilar).

>>> graph = networkx.balanced_tree(2,3)
>>> paige_tarjan(graph)
[(7, 8, 9, 10, 11, 12, 13, 14), (3, 4, 5, 6), (1, 2), (0,)]

This function works with integer graph (nodes are integers starting from 0 and form an interval without holes). If the given graph is non-integer it is converted to an isomorphic integer graph automatically (unless is_integer_graph is True) and then re-converted to its original form after the end of the computation. For this reason nodes of graph must be hashable objects.

Warning

Using a non integer graph and setting is_integer_graph to True will probably make the function fail with an exception, or, even worse, return a wrong output.

Parameters

• graph (Graph) – The input graph.

• initial_partition (Optional[Iterable[Iterable[int]]]) – The initial partition (or labeling set). Defaults to None, in which case the trivial labeling set (one block which contains all the nodes) is used.

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

Return type

List[Tuple]

Returns

The RSCP/maximum bisimulation of the given labeling set as a list of tuples, each of which contains bisimilar nodes.

paige_tarjan_qblocks(q_partition)

Apply the Paige-Tarjan algorithm to the partition \(Q\), which

is considered a labeling set (namely two vertexes in different blocks of the initial partition cannot be bisimilar).

Parameters

q_partition (List[_QBlock]) – The initial partition (labeling set).

Return type

List[_QBlock]

Returns

The RSCP/maximum bisimulation of the given labeling set.

extract_splitter(compound_block)

Given a compound block in the X partition, extract one of the blocks of the partition Q inside (the smallest among the first two blocks in the list). The chosen block is removed from the compound block and returned.

compound_block: A compound block in the partition X.

Return type

_QBlock

build_block_counterimage(B_qblock)

Given a block \(B \in Q\), construct the \(E^{-1}(B)\). This function also sets vertex.aux_count and increases it by one for each visited vertex in order to find the value \(|B \cap E({vertex})|\), where \(E\) is the edge relation (\(\to\)) of the graph.

Parameters

B_qblock (_QBlock) – A block of \(Q\).

Return type

List[_Vertex]

build_exclusive_B_counterimage(B_qblock_vertexes)

Given a block \(B \in Q\), generate the “exclusive counterimage” of \(B\), namely the set \(E^{-1}(B) - E^{-1}(S-B)\), where \(E\) is the edge relation (\(\to\)) of the graph. It’s fundamental that this function is called after build_block_counterimage(), since it uses the field aux_count set by that function in instances of bispy.utilities.graph_entities._Vertex.

Parameters

B_qblock_vertexes (List[_Vertex]) – A block of \(Q\) represented by the list of its vertexes.

Return type

List[_Vertex]

split(vertexes)

Given a list of vertexes, use them as splitter set for the current partition \(Q\). This function doesn’t modify the partition.

Parameters

vertexes (List[_Vertex]) – A list of vertexes.

Return type

Tuple[List[_QBlock], List[_XBlock], List[_QBlock]]

Returns

A tuple whose items are:

0. The new blocks of \(Q\);

1. The new compound blocks of \(X\);

2. The modified (but not new) blocks of \(Q\).

update_counts(B_block_vertexes)

After a block \(B \in Q\) has become a (non-compound) block of \(X\) on its own (it was removed from a compound block of \(X\)) we need to decrease by one the quantity count(x, \(S\)) (which is now count(x, \(S-B\))) for each vertex in \(E^{-1}(B)\).

Parameters

B_block_vertexes (List[_Vertex]) – A block of \(Q\) which is also a block of \(S\), represented by its vertexes.

refine(compound_xblocks, xblocks)

Perform a refinement step of the Paige-Tarjan algorithm.

Parameters

• compound_xblocks (CompoundXBlocksContainer) –

  Compound blocks in the partition \(X\). This parameter expects an object of type bispy.paige_tarjan.compound_xblocks_container .CompoundXBlocksContainer, but it is possible to subclass this class in order to support a different ordering of compound blocks.

  See also

  modules bispy.saha.ranked_pta

• xblocks (List[_XBlock]) – The partition \(X\).

Return type

Tuple[List[_XBlock], List[_QBlock]]

Returns

A tuple whose items are:

0. The new partition \(X\);

1. The new blocks of \(Q\) generated by the two split phases;