Graph entities

class _Vertex(label)

BisPy representation of a vertex. Contains several data structures which provide \(O(1)\) access to the \(E(\textit{vertex})\) and \(E^{-1}(\textit{vertex})\), as well as attributes to store temporary information used among different parts of the algorithm (make sure to reset them when they are not needed anymore).

Parameters

label (int) – A unique integer ID which identifies this vertex.

property label

The current label assigned to this _Vertex instance. May change if a method like scale_label() is called.

property original_label

The original label assigned to this _Vertex instance. Does not change (ever!).

property qblock

The _QBlock instance that this _Vertex belongs to at the moment.

property scc

The _SCC instance that this _Vertex belongs to at the moment.

property rank: Union[int, float]

The rank of this vertex (associated with the rank of the corresponding SCC).

Return type

Union[int, float]

property wf: bool

True if this vertex is well-founded, False otherwise.

Return type

bool

scale_label(scaled_label)

Change the label of this vertex to scaled_label. This is usually done when we want to apply an algorithm like Paige-Tarjan to a subgraph of \(G\), therefore we need to “scale” the vertexes in that subgraph in order to make the subgraph integer (for a reference about this topic have a look at the module bispy.utilities.graph_normalization).

The old label is stored in original_label(), and can be recovered using back_to_original_label().

Parameters

scaled_label (int) – The new label.

back_to_original_label()

Undo the result of a call to scale_label().

restrict_to_subgraph(validation)

Restrict the image and counterimage only to vertexes that satisfy the given validation function, and resets the value of the associated _Count instanced.

Also sets _original_img, _original_counterimg, _original_count, which can then be recovered using back_to_original_graph().

Parameters

validation (Callable[[_Vertex], bool]) – A function which returns True when the vertex given as argument is accepted in the subgraph.

back_to_original_graph()

Recover the original image, counterimage and associated values of _Count, must be called after a call to restrict_to_subgraph().

class _Edge(source, destination)

Represents an edge between two instances of _Vertex.

Parameters

• source (_Vertex) – The source of the edge.

• destination (_Vertex) – The destination of the edge.

property count

Holds the value \(|E({\textit{source}}) \cap S|\), where \(S\) is the block of the partition \(X\) that destination belongs to.

class _QBlock(vertexes, xblock)

A block of the partition \(Q\). This is also used as a general-purpose block by Dovier-Piazza-Policriti’s and Saha’s algorithms.

This class uses a Doubly-Linked-List to store the set vertexes inside the block, therefore we are able to remove a node in \(O(1)\).

Parameters

• vertexes (List[_Vertex]) – Vertexes in the block.

• xblock (_XBlock) – The block of \(X\) that this block belongs to.

property rank: int

The rank of all the vertexes in this block (note that in general one may create a _QBlock from an arbitrary set of vertexes, in that case we cannot say in general that those vertexes have all the same rank).

Return type

int

property xblock

The block of \(X\) this block belongs to.

append_vertex(vertex)

Append a new vertex to this block. This also sets the attributes vertex._dllistnode and vertex._qblock, and updates the attribute size.

Parameters

vertex (_Vertex) – The new vertex to be added.

remove_vertex(vertex)

Remove a vertex to this block. This also resets the attribute vertex._qblock, and updates the attribute size.

This function uses the attribute vertex._dllistnode to modify the Doubly-Linked-List in the attribute vertexes in \(O(1)\).

Parameters

vertex (_Vertex) – The new vertex to be added.

merge(block2)

Add all the vertexes in block2 to this block, and then set the attribute block2.deteached to True.

Parameters

block2 (_QBlock) – The block to be merged into self.

fast_mitosis(extract_vertexes)

Extract a subset of vertexes from this block to create a new block.

Parameters

extract_vertexes (List[_Vertex]) – The subset of vertexes to be extracted.

Returns

The new block which contains the vertexes in extract_vertexes.

Return type

_QBlock

class _XBlock

A block of the partition \(X\).

This class uses a Doubly-Linked-List to store the set vertexes inside the block, therefore we are able to remove a block in \(O(1)\).

property size

The number of blocks of \(Q\) in this block of \(X\).

append_qblock(qblock)

Insert a new block of \(Q\) in this block. This also sets the attributes qblock.dllistnode and qblock.xblock.

Param

The block of \(Q\) to be inserted.

Returns

self, to allow chain insertions.

Return type

_XBlock

remove_qblock(qblock)

Remove a block of \(Q\) from this block. This also resets the attribute qblock.xblock to None.

Param

The block of \(Q\) to be removed.

class _SCC(label)

Represents a strongly connected component. This is used to compute rank.

Parameters

label (int) – A unique ID.

property label: int

The unique ID which represents this SCC.

Return type

int

property image

The overall image of the SCC. The function compute_image() must be called beforehand.

property counterimage

The overall counterimage of the SCC. The function compute_counterimage() must be called beforehand.

property wf: bool

True if the SCC is well-founded (an SCC may be well-founded if there is only one vertex in the component, but this is not guaranteed).

Return type

bool

property rank: Union[int, float]

The rank of the vertexes in this SCC.

Return type

Union[int, float]

add_vertex(vertex)

Add a new vertex to this SCC.

Parameters

vertex (_Vertex) – The vertex to be added.

mark_leaf()

Mark this SCC as a leaf of the graph.

mark_scc_leaf()

Mark this SCC as a leaf of the graph of strongly connected components.

compute_image()

Compute the image of this SCC.

compute_counterimage()

Compute the counterimage of this SCC.

destroy()

Destroy this SCC (image, counterimage and vertexes set).

join(other)

Merge other into this SCC, and destroy other.

Parameters

other (_SCC) – The SCC to be merged into self.