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 ofbispy.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 functionbuild_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 ofbispy.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
- Returns
A tuple whose items are:
List of vertexes of the graph;
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 ofbispy.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 functionbuild_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
- Returns
None if preprocess is False; otherwise a tuple whose items are:
List of vertexes of the graph;
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.
- 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}\).
- 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
- Returns
A tuple whose items are:
List of vertexes in the graph;
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}\).