ragraph.analysis.heuristics#

Heuristics are combinations of algorithms available in the other subpackages or have an output that does not strictly fit one of the other categories. Not all heuristics have a common argument structure because of their more diverse nature.

Available heuristics#

The following heuristics are directly available after importing ragraph.analysis.heuristics:

  • johnson(): Johnson’s circuit finding algorithm. Generates all cycles in a graph, including overlapping and nested cycles.

  • markov_gamma(): Combination of Gamma bus detection and (Hierarchical) Markov Clustering. Detects a tree structure with buses on global or local levels.

Submodules#

Package Contents#

Functions#

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

Donald B. Johnson's nested circuit finding algorithm. A circuit is a cycle in a

markov_gamma(→ Union[List[ragraph.graph.Node], ...)

Cluster a given graph hierarchically with buses on a local level or globally.
ragraph.analysis.heuristics.johnson(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

ragraph.analysis.heuristics.markov_gamma(graph: ragraph.graph.Graph, root: Optional[Union[str, ragraph.graph.Node]] = None, leafs: Optional[Union[List[ragraph.graph.Node], List[str]]] = None, inherit: bool = True, loops: bool = False, edge_weights: Optional[List[str]] = None, alpha: int = markov_gamma_params['alpha'].default, beta: float = markov_gamma_params['beta'].default, mu: float = markov_gamma_params['mu'].default, gamma: float = markov_gamma_params['gamma'].default, local_buses: bool = markov_gamma_params['local_buses'].default, max_iter: int = markov_gamma_params['max_iter'].default, symmetrize: bool = markov_gamma_params['symmetrize'].default, inplace: bool = True, names: bool = False, safe: bool = True, **kwargs) → Union[List[ragraph.graph.Node], Tuple[ragraph.graph.Graph, List[ragraph.graph.Node]]]#

Cluster a given graph hierarchically with buses on a local level or globally.