Rank computation

compute_rank(vertexes, sccs=None)

Compute the rank of the given list of nodes. This function uses Kosaraju’s algorithm to compute strongly connected components (if they are not given).

Warning

The image of each node must be in topological order (see bispy.utilities.graph_decorator.decorate_nx_graph()), otherwise the computed rank may be wrong.

Parameters

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

  • sccs – SCCs of the graph. Defaults to None, in which case SCCs are computed using Kosaraju’s algorithm.

scc_finishing_time_list(sccs)

Perform a DFS on the given graph of strongly connected components, and return the finishing time of each SCC.

Parameters

sccs (List[_SCC]) – The graph of strongly connected components, as a list of SCCs.

Returns

A list of SCCs sorted by increasing finishing time.