# `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.

## 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.