Graph decorator

decorate_nx_graph(graph, initial_partition=None, set_count=True, topological_sorted_images=True, compute_rank=True, set_xblock=True, preprocess=True)

Create the BisPy representation of the given graph.

Parameters

  • graph (Graph) – The graph, in NetworkX representation.

  • initial_partition (Optional[List[Tuple[int]]]) – The initial partition, or labeling set, imposed on the nodes of the graph. Defaults to the trivial labeling set (one block which contains all the nodes in the graph).

  • set_count (bool) – If True, we set the attribute count of each vertex to an appropriate instance of bispy.utilities.graph_entities._Count. If False, the attribute is set to None. Defaults to True.

  • topological_sorted_images (bool) – If True, the image of each vertex is computed using the function build_vertexes_image(). If False, the image is computed without any particular precautions. Defaults to True.

  • compute_rank (bool) – If True, the function computes the rank of each vertex. May be useless for some algorithms, like Paige-Tarjan’s, in which case performance can be slightly improved by setting this parameter to False. Defaults to True.

  • set_xblock (bool) – If True we set the attribute xblock of each block of the partition to an instance of bispy.utilities.graph_entities._XBlock (the same for each block). If False, we set the attribute to None. Defaults to True.

  • preprocess (bool) – Preprocess the initial partition to split blocks which contain both leafs and non-leafs. Fundamental for Paige-Tarjan’s algorithm, may be disabled for other algorithms.

Return type

Tuple[List[_Vertex], List[_QBlock]]

Returns

A tuple whose items are:

  1. List of vertexes of the graph;

  2. List of blocks of the initial partition.

Both items are in BisPy representation.

decorate_bispy_graph(vertexes, initial_partition=None, set_count=True, topological_sorted_images=True, compute_rank=True, preprocess=True)

Update the BisPy representation of the given graph with more information.

Parameters

  • vertexes (List[_Vertex]) – The vertexes of the graph, in BisPy representation.

  • initial_partition (Optional[List[Tuple[int]]]) – The initial partition, or labeling set, imposed on the nodes of the graph. Defaults to the trivial labeling set (one block which contains all the nodes in the graph).

  • set_count (bool) – If True, we set the attribute count of each vertex to an appropriate instance of bispy.utilities.graph_entities._Count. If False, the attribute is set to None. Defaults to True.

  • topological_sorted_images (bool) – If True, the image of each vertex is computed using the function build_vertexes_image(). If False, the image is computed without any particular precautions. Defaults to True.

  • compute_rank (bool) – If True, the function computes the rank of each vertex. May be useless for some algorithms, like Paige-Tarjan’s, in which case performance can be slightly improved by setting this parameter to False. Defaults to True.

  • preprocess (bool) – Preprocess the initial partition to split blocks which contain both leafs and non-leafs. Fundamental for Paige-Tarjan’s algorithm, may be disabled for other algorithms.

Return type

Optional[Tuple[List[_Vertex], List[_QBlock]]]

Returns

None if preprocess is False; otherwise a tuple whose items are:

  1. List of vertexes of the graph;

  2. List of blocks of the initial partition.

Both items are in BisPy representation.

to_tuple_list(qblocks)

Convert the given partition (represented by a list of bispy.utilities.graph_entities._QBlock) to a list of tuples. The blocks of the resulting partition contain the labels of the vertexes in the corresponding blocks of qblocks.

Parameters

qblocks (List[_QBlock]) – A partition.

Return type

List[Tuple]

preprocess_initial_partition(vertexes, initial_partition)

Preprocess the given partition to split blocks which contain both leafs and non-leafs. This is a fundamental hypothesis in order to make Paige-Tarjan’s algorithm work.

The attribute qblock of each vertex must already have been initialized.

Parameters

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

  • initial_partition (List[Tuple[int]]) – The initial partition, as a list of vertexes index.

Return type

List[_QBlock]

Returns

The preprocessed partition, as a list of bispy.utilities.graph_entities_QBlock.

counterimage_dfs(current_vertex_idx, vertexes, finishing_list, colors)

Recursively visit \(G^{-1}\) starting from the vertex in the position current_vertex_idx of the list vertexes. Meanwhile fill finishing_list everytime time the counterimage of a vertex is completely visited.

Parameters

  • current_vertex_idx (int) – The current vertex to be visited.

  • vertexes (List[_Vertex]) – List of vertexes in the graph.

  • finishing_list (List[_Vertex]) – List of vertexes in order of increasing finishing time. Must be passed (as an empty list) upon the first call of the function. The list will be filled when the function returns.

  • colors (List[int]) – List of color (one for each vertex) maintained by the algorithm to prevent visiting the same vertex more than once. Must be passed by the user (all values must be _WHITE) upon the first call of the function.

compute_counterimage_finishing_time_list(vertexes)

Compute the finishing time of each vertex of \(G\) for a DFS of \(G^{-1}\).

Parameters

vertexes (List[_Vertex]) – Vertexes of \(G\).

Return type

List[_Vertex]

as_bispy_graph(graph, initial_partition, build_image, set_count, set_xblock)

Create the BisPy representation of the given graph. There are several options to enable/disable depending on which algorithm in BisPy you plan to use.

Parameters

  • graph (Graph) – The graph.

  • initial_partition (List[Tuple[int]]) – The initial partition (or labeling set) imposed on vertexes of the graph. Used to divide nodes in blocks.

  • build_image – If True, we compute the image of each vertex.

  • set_count – If True, we set the attribute count of each vertex to an appropriate instance of bispy.utilities.graph_entities._Count.

  • set_xblock – If True we set the attribute xblock of each block of the partition to an instance of bispy.utilities.graph_entities._XBlock (the same for each block). If False, we set the attribute to None.

Return type

Tuple[List[_Vertex], List[_QBlock]]

Returns

A tuple whose items are:

  1. List of vertexes in the graph;

  2. List of blocks in the initial partition.

Both the items are in BisPy representation.

build_vertexes_image(finishing_time_list)

Build the image of each vertex in the graph in a convenient order to facilitate further computations (like the rank). Vertexes in the constructed image are arranged in inverse order of finishing time for a DFS on \(G^{-1}\).

Parameters

finishing_time_list (List[_Vertex]) – Vertexes of \(G\) in order of increasing finishing time for a DFS on \(G^{-1}\).