PaigeTarjan¶
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): 973989.
PaigeTarjan’s algorithm provides the first efficient algorithmic solution to the problem of the maximum bisimulation.
Summary¶
Compute the RSCP/maximum bisimulation of the given graph using PaigeTarjan's algorithm, with the given initial partition (or labeling set, two vertexes in different blocks of the initial partition cannot be bisimilar). 

Apply the PaigeTarjan algorithm to the partition \(Q\), which 

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

Given a block \(B \in Q\), construct the \(E^{1}(B)\). 

Given a block \(B \in Q\), generate the "exclusive counterimage" of \(B\), namely the set \(E^{1}(B)  E^{1}(SB)\), where \(E\) is the edge relation (\(\to\)) of the graph. 

Given a list of vertexes, use them as splitter set for the current partition \(Q\). 

After a block \(B \in Q\) has become a (noncompound) 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, \(SB\))) for each vertex in \(E^{1}(B)\). 

Perform a refinement step of the PaigeTarjan algorithm. 
Code documentation¶
 paige_tarjan(graph, initial_partition=None, is_integer_graph=False)¶
Compute the RSCP/maximum bisimulation of the given graph using PaigeTarjan’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 noninteger it is converted to an isomorphic integer graph automatically (unless is_integer_graph is True) and then reconverted 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 PaigeTarjan algorithm to the partition \(Q\), which
is considered a labeling set (namely two vertexes in different blocks of the initial partition cannot be bisimilar).
 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
 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.
 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}(SB)\), 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 ofbispy.utilities.graph_entities._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.
 update_counts(B_block_vertexes)¶
After a block \(B \in Q\) has become a (noncompound) 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, \(SB\))) 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 PaigeTarjan 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
 Returns
A tuple whose items are:
The new partition \(X\);
The new blocks of \(Q\) generated by the two split phases;