`ragraph.analysis.cluster._tarjan`#

Tarjan’s strongly connected components algorithm.

Reference:

Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms.: SIAM Journal on Computing, 1(2), 146-160. https://doi.org/10.1137/0201010

Module Contents#

`tarjans_scc_clustering`(→ Tuple[ragraph.graph.Graph, ...)
`tarjans_scc_algorithm`(→ List[List[ragraph.node.Node]])	Tarjan's strongly connected components algorithm.

ragraph.analysis.cluster._tarjan.tarjans_scc_clustering(graph: ragraph.graph.Graph, root: Optional[Union[str, ragraph.node.Node]] = None, leafs: Optional[Union[List[ragraph.node.Node], List[str]]] = None, inherit: bool = True, loops: bool = False, edge_weights: Optional[List[str]] = None, inplace: bool = True, names: bool = False, safe: bool = True, **kwargs) → Tuple[ragraph.graph.Graph, Union[List[ragraph.node.Node], List[str]]]#

ragraph.analysis.cluster._tarjan.tarjans_scc_algorithm(graph: ragraph.graph.Graph, nodes: List[ragraph.node.Node], inherit: bool) → List[List[ragraph.node.Node]]#

Tarjan’s strongly connected components algorithm.

Parameters:

graph – Graph to detect SCC’s in (cycles).
nodes – List of nodes (components) to detect SCC’s for.
inherit – Whether to take into account (inherit) edges between children during calculations.

Returns:

Lists of strongly connected components.

Reference:

Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms.: SIAM Journal on Computing, 1(2), 146-160. https://doi.org/10.1137/0201010