ragraph.analysis.heuristics._johnson#

Donald B. Johnson’s nested circuit finding algorithm.

Module Contents#

Functions#

circuit_finding_algorithm(→ Generator[Union[List[str], ...)

Donald B. Johnson's nested circuit finding algorithm. A circuit is a cycle in a
ragraph.analysis.heuristics._johnson.circuit_finding_algorithm(graph: ragraph.graph.Graph, nodes: Optional[List[ragraph.node.Node]] = None, names: bool = False, inherit: bool = True, **kwargs) → Generator[Union[List[str], List[ragraph.node.Node]], None, None]#

Donald B. Johnson’s nested circuit finding algorithm. A circuit is a cycle in a graph, circuits can overlap or contain duplicate parts.

Parameters:

  • graph – Graph to find circuits in.

  • nodes – Nodes to consider during circuit search.

  • inherit – Whether to take into account (inherit) edges between children during SCC calculations.

Yields:

Node circuit lists.

Note

Cannot cluster a graph directly since circuits may overlap in all sorts of ways. Therefore, it gives you cluster-related information, but no clear hierarchy.

Reference:
Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph.

In SIAM J. COMPUT (Vol. 4). https://doi.org/10.1137/0204007