Donald B. Johnson’s nested circuit finding algorithm.
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.
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.
Node circuit lists.
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.
- 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