Navigability

Landscape navigability, often closely related to peak accessibility, concerns the ease with which evolving populations can traverse a fitness landscape to discover and ascend fitness peaks, particularly those representing high or optimal fitness genotypes. It is a critical property influencing the rate and predictability of adaptation, as it determines whether populations can efficiently find beneficial evolutionary trajectories or become trapped on suboptimal solutions. The fundamental basis of navigability lies in the existence and nature of accessible paths—sequences of mutations where each step confers a non-decreasing, and typically increasing, fitness effect, which natural selection can favor.

In simple terms, it describes whether there are viable mutational routes that an evolving population can follow to reach higher fitness states without having to cross significant fitness valleys, which selection would typically prevent.

Overview

API	Purpose
local_optima_accessibility	Fraction of genotypes that can reach a given local optimum via monotonic paths.
global_optima_accessibility	Same, but specifically for the global optimum.
fdc	Spearman / Pearson correlation between fitness and distance-to-GO (FDC).
basin_fitness_correlation	Correlation between basin size and the fitness of its local optimum.
evolvability_enhancing_fraction	Fraction of observed directed mutations with a statistically supported EE effect.
mean_path_length_to_local_optima	Mean/variance of shortest path lengths from variants to specified peaks.
mean_path_length_to_global_optimum	Same, targeting the global optimum.
mean_distance_to_local_optima	Mean Hamming/edit distance from all variants to specified peaks.
mean_distance_to_global_optimum	Same, targeting the global optimum.

Peak Accessibility

Calculates the accessibility of one or more specified peak(s) in the fitness landscape.

This metric quantifies the proportion of all genotypes in the landscape that can reach a specified peak (or set of peaks) by following any path of monotonically increasing fitness (i.e., adaptive walks). It is equivalent to the size of the peak’s basin of attraction divided by the total number of genotypes in the landscape. In other words, it reflects how many variants fall within the basin of attraction of the given peak(s).

A higher accessibility indicates that more variants can access the peak(s) during evolution, whereas a low value indicates that the peak(s) is hardly accessible.

graphfla.analysis.local_optima_accessibility(
    landscape, lo: Union[int, List[int]]
) -> pd.DataFrame

Return accessibility fractions for the requested local optima.

ParametersReturnsExamplesNotesRaises

Parameters

landscape : Landscape

Built fitness landscape.

lo : int or list of int

Index of the local optimum to analyze, or a list of indices when analyzing multiple local optima.

Returns

accessibility : pandas.DataFrame

One row per requested local optimum, with columns:

• local_optimum : the local-optimum node index.

• accessibility : the fraction of configurations able to reach it monotonically (between 0.0 and 1.0), including the target itself.

A single lo yields a one-row frame (no scalar-vs-list polymorphism).

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import local_optima_accessibility
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> local_optima_accessibility(landscape, lo=3).accessibility.tolist()
[1.0]

This metric represents the fraction of configurations in the landscape that can reach the specified local optimum (or optima) via any monotonic, fitness-improving path.

The implementation uses graph traversal to find all nodes (configurations) that have a directed path to the local optimum in the landscape graph. These are the "ancestors" of the local optimum - configurations from which the LO can be reached by following fitness-improving moves.

Raises

RuntimeError

If the graph is not initialized.

ValueError

If any provided index is not a local optimum.

TypeError

If lo is not an int or a list of ints.

Calculates the accessibility of the global peak in the fitness landscape.

This metric quantifies the proportion of all genotypes in the landscape that can reach the global peak via any path of monotonically increasing fitness (i.e., adaptive walks). It is equivalent to the size of the selected global peak’s basin of attraction divided by the total number of genotypes in the landscape. In other words, it reflects how many variants fall within the basin of attraction of the global peak.

Since the global peak is the utmost goal of evolution, its accessibility can reflect the navigability of whole landscape.

graphfla.analysis.global_optima_accessibility(
    landscape,
) -> float

Return the fraction of configurations that can reach the global optimum.

ParametersReturnsExamplesNotesRaises

Parameters

landscape : Landscape

Built fitness landscape.

Returns

fraction : float

The fraction of configurations able to reach the global optimum monotonically (value between 0.0 and 1.0).

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import global_optima_accessibility
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> global_optima_accessibility(landscape)
1.0

This metric represents the fraction of configurations in the landscape that can reach the global optimum via any monotonic, fitness-improving path.

Use local_optima_accessibility with the selected global-optimum index; the target itself counts as reachable.

Raises

RuntimeError

If the global optimum has not been determined or the graph is not initialized.

Fitness Distance Correlation

Calculates the Fitness Distance Correlation (FDC) of a landscape.

This metric measures the navigability of a fitness landscape by quantifying the correlation between the fitness values of variants and their respective distances to the global peak. It assesses how informative the fitness landscape is in guiding the evolution towards prominent regions. A landscape where fitness reliably increases as evolution approaches the global peak (indicated by a strong negative FDC) is generally considered easier to navigate than one where the relationship is weak, random, or misleading (indicated by an FDC near zero or positive).

Automatic Distance Calculation

The function automatically attempts to calculate the distance to the global peak for each genotype if it's not already present in the landscape data . This will add new attributes for genotypes ("dist_go") that can be accessed via Landscape.graph or Landscape.get_data().

graphfla.analysis.fdc(
    landscape, method: str = "spearman"
) -> float

Return the correlation between fitness and distance to the global optimum.

ParametersReturnsExamplesRaises

Parameters

landscape : Landscape

Built fitness landscape. Distances to its selected global optimum are computed lazily when absent.

method : (spearman, pearson), default="spearman"

Correlation coefficient to calculate.

Returns

correlation : float

Correlation in [-1, 1], or NaN when undefined. Under maximization, a negative correlation means fitness tends to increase toward the selected global optimum.

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import fdc
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> round(fdc(landscape), 3)
-0.949

Raises

ValueError

If the method is invalid or Pearson correlation has fewer than two configurations.

Basin Size-Fitness Correlation

Calculates the correlation between the size of the basin of attraction and the fitness of peaks.

The size of the basin of attraction of a peak is defined as the total number of variants in the landscape from which the peak is accessible. The size of these basins can reveal important information about the landscape's structure and navigability. A common question is whether larger basins tend to be associated with fitter peaks, which could imply that fitter peaks are easier to be accessed. This function quantifies such a relationship by calculating the correlation between basin sizes and the fitness values of their corresponding peaks.

graphfla.analysis.basin_fitness_correlation(
    landscape, method: str = "spearman"
) -> float

Return the correlation between greedy basin size and local-optimum fitness.

ParametersReturnsExamplesRaises

Parameters

landscape : Landscape

Built fitness landscape.

method : (spearman, pearson), default="spearman"

The correlation measure to use.

Returns

correlation : float

Correlation between greedy basin size and local-optimum fitness in [-1, 1], or NaN when undefined. Basins are computed lazily when absent.

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import basin_fitness_correlation
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 3, 2, 1], verbose=False)
>>> round(basin_fitness_correlation(landscape), 3)
1.0

Raises

ValueError

If the method is invalid or Pearson correlation has fewer than two local optima.

Evolvability-enhancing Mutations

Background dependence can also change the opportunities for subsequent adaptation. A mutation may make other mutations more favorable, even when its own fitness effect is small or negative. Wagner (2023) describes such mutations as evolvability-enhancing (EE).

GraphFLA compares the mean fitness of the two mutational neighborhoods, excluding changes at the mutated position. For a beneficial mutation, the neighborhood increase must exceed its own fitness gain; for a neutral or deleterious mutation, it must exceed zero. The EE fraction counts statistically supported cases among all observed directed mutations. It measures local opportunities for adaptation, without guaranteeing that evolution will reach a fitter peak.

graphfla.analysis.evolvability_enhancing_fraction(
    landscape, *, fdr=0.01, effect_type="all"
) -> float

Return the fraction of evolvability-enhancing directed mutations.

See Also

• evolvability_effects — Per-mutation results, test definitions and neighborhood-variance conventions.

ParametersReturnsExamplesNotesRaises & Warns

Parameters

landscape : Landscape

Built landscape with unique, nonmissing configurations, finite fitness values and one-site neighbor pairs. Both orientations of each graph pair and retained neutral pair are evaluated once. Discarded vertices and neighbor pairs are not reconstructed. Fitness is negated when landscape.maximize=False so positive effects indicate improvement.

fdr : float, default=0.01

Benjamini-Hochberg false discovery rate, strictly between 0 and 1. Corrections use all ordered pairs, before selecting an effect type.

effect_type : (all, beneficial, deleterious, neutral), default="all"

Effects to include in the numerator, classified by the sign of the unrounded fitness change. The denominator always includes every represented ordered neighbor pair. "all" combines all three classes.

Returns

fraction : float

Significant EE mutations of the selected type divided by all ordered neighbor pairs. Untestable pairs remain in the denominator and are not counted as EE. The value lies in [0, 1] when defined; return NaN if no pair is testable. A type with no EE mutations returns zero if at least one pair in the full landscape is testable.

Examples

An additive landscape has no EE mutations: the neighborhood increase equals the focal mutation's own fitness benefit.

>>> from itertools import product
>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import evolvability_enhancing_fraction
>>> X = list(product([0, 1], repeat=3))
>>> landscape = BooleanLandscape()
>>> _ = landscape.build_from_data(X, [sum(x) for x in X], verbose=False)
>>> evolvability_enhancing_fraction(landscape)
0.0
>>> evolvability_enhancing_fraction(landscape, effect_type="beneficial")
0.0

A mutation is evolvability-enhancing (EE) when the increase in mean non-focal neighbor fitness significantly exceeds the larger of zero and its own fitness effect 1. A mutation may be any one-variable change represented in the landscape, including changes in nonbiological data.

References

[1] Wagner, A. Evolvability-enhancing mutations in the fitness landscapes of an RNA and a protein. Nat. Commun. 14, 3624 (2023). https://doi.org/10.1038/s41467-023-39321-8

Raises

graphfla.exceptions.NotBuiltError

If the landscape has not been built.

ValueError

If fdr or effect_type is invalid, configurations are missing or duplicated, fitness is nonfinite, or a pair does not differ at one site.

Warns

RuntimeWarning

If no pair has at least two non-focal neighbors at each endpoint.

See per-mutation EE results for the detailed output.

Length of Accessible Paths

Calculates the mean and variance of the shortest path lengths from variants to specified peaks.

In a perfectly smooth landscape, the length of the shortest accessible path from any one variant to a high fitness peak equals the genetic distance between the variant and the peak. In contrast, in a rugged landscape, even the shortest accessible path may meander through the landscape and thus be much longer than this genetic distance.

This function quantifies these path lengths, providing insights into the landscape's navigability by measuring the expected adaptive walk steps required to reach peaks. It computes the shortest path length from each variant (or a sample thereof) to one or more target peaks.

graphfla.analysis.mean_path_length_to_local_optima(
    landscape,
    lo: Optional[Union[int, List[int]]] = None,
    accessible: bool = True,
    n_samples: Optional[Union[int, float]] = None,
    seed: Optional[int] = None,
) -> pd.DataFrame

Return mean and variance of shortest path lengths to local optima.

ParametersReturnsExamplesNotesRaises

Parameters

landscape : Landscape

Built fitness landscape.

lo : int, list of int or None, default=None

Index of the local optimum to analyze, or a list of indices when analyzing multiple local optima. If None, uses the global optimum.

accessible : bool, default=True

If True, only consider monotonically accessible (fitness-improving) paths. If False, ignore the direction of existing graph edges. Retained neutral pairs are not added as path edges.

n_samples : (int, float or None), default=None

If provided, use sampling to approximate the results:

• If float in (0, 1]: Sample this fraction of configurations.

• If positive int: Sample at most this many configurations.

• If None: Compute for all configurations (with warning for large landscapes).

seed : int or None, default=None

Seed for sampling configurations. An integer makes the sample reproducible; None uses the global Python random state. Ignored when n_samples=None.

Returns

path_lengths : pandas.DataFrame

One row per target local optimum, with columns local_optimum, mean and variance of the shortest path lengths to it. When lo is None the single row is the global optimum. Infinite distances are excluded from the calculations (a row whose targets are all unreachable has mean/variance of NaN).

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import mean_path_length_to_local_optima
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> mean_path_length_to_local_optima(landscape, lo=3)["mean"].tolist()
[1.0]

This function computes the shortest path length from each configuration to the specified local optima. If accessible=True, only monotonically fitness-improving paths are considered (using OUT mode in distances). Otherwise, any path regardless of fitness is considered (using ALL mode).

For large landscapes, computing distances for all configurations can be computationally expensive. In such cases, a warning is raised, and the function can use sampling to approximate the results by setting n_samples.

Raises

RuntimeError

If the graph is not initialized or the target optima are not determined.

ValueError

If n_samples is invalid or any provided index is not a local optimum.

TypeError

If lo is not an int, a list of ints, or None.

Calculates the mean of the shortest path lengths from variants to the global peak.

This function computes the shortest path length from each variant (or a sample thereof) to the global peak of the landscape. It serves as a convenience wrapper around the more general mean_path_length_to_local_optima function, specifically targeting the global peak. The path lengths provide insights into the landscape's navigability by measuring the expected number of adaptive steps required to reach the global peak.

graphfla.analysis.mean_path_length_to_global_optimum(
    landscape,
    accessible: bool = True,
    n_samples: Optional[Union[int, float]] = None,
    seed: Optional[int] = None,
) -> float

Return the mean shortest path length to the global optimum.

ParametersReturnsExamplesNotesRaises

Parameters

landscape : Landscape

Built fitness landscape.

accessible : bool, default=True

If True, only consider monotonically accessible (fitness-improving) paths. If False, ignore the direction of existing graph edges. Retained neutral pairs are not added as path edges.

n_samples : (int, float or None), default=None

If provided, use sampling to approximate the results:

• If float in (0, 1]: Sample this fraction of configurations.

• If positive int: Sample at most this many configurations.

• If None: Compute for all configurations (with warning for large landscapes).

seed : int or None, default=None

Seed for sampling configurations. An integer makes the sample reproducible; None uses the global Python random state. Ignored when n_samples=None.

Returns

mean_length : float

The mean shortest path length to the global optimum. Infinite distances are excluded from the calculation.

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import mean_path_length_to_global_optimum
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> mean_path_length_to_global_optimum(landscape)
1.0

This function computes the shortest path length from each configuration to the global optimum. It extracts the mean returned by mean_path_length_to_local_optima.

Raises

RuntimeError

If the graph is not initialized or the global optimum is not determined.

ValueError

If n_samples is invalid.

Calculates the mean distance from all variants to one or more specified peak(s).

This function provides a measure of how "far" on average other points in the landscape are from specific peak(s), using a defined distance metric (e.g., Hamming distance or Edit distance). This can be useful for understanding the global structure of the landscape in relation to its peaks.

graphfla.analysis.mean_distance_to_local_optima(
    landscape,
    lo: Union[int, List[int]],
    distance_func: Optional[Callable] = None,
) -> pd.DataFrame

Return mean configuration distances to the requested local optima.

ParametersReturnsExamplesRaises

Parameters

landscape : Landscape

Built fitness landscape.

lo : int or list of int

Index of the local optimum to analyze, or a list of indices when analyzing multiple local optima.

distance_func : callable or None, default=None

Callable distance_func(configs, target, data_types) returning one distance per row of the encoded configuration array. If None, use the landscape default distance metric. The target contributes zero for standard distance functions.

Returns

distances : pandas.DataFrame

One row per requested local optimum, with columns local_optimum and mean_distance (the mean distance from all configurations to it). A single lo yields a one-row frame (no scalar-vs-list polymorphism).

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import mean_distance_to_local_optima
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> mean_distance_to_local_optima(landscape, lo=3).mean_distance.tolist()
[1.0]

Raises

RuntimeError

If the graph is not initialized or required attributes are missing.

ValueError

If any provided index is not a local optimum.

TypeError

If lo is not an int or a list of ints.

Calculates the mean distance from all variants to the global peak.

This function determines the average distance from every variant in the landscape to its global peak. It can utilize a pre-calculated 'dist_go' vertex attribute if available; otherwise, it computes these distances using the specified or default distance function. This metric helps characterize the overall spread or compactness of the landscape relative to its highest peak.

graphfla.analysis.mean_distance_to_global_optimum(
    landscape, distance_func: Optional[Callable] = None
) -> float

Return the mean configuration distance to the global optimum.

ParametersReturnsExamplesNotesRaises

Parameters

landscape : Landscape

Built fitness landscape.

distance_func : callable or None, default=None

Callable distance_func(configs, target, data_types) returning one distance per row of the encoded configuration array. If None, use the landscape default distance metric. The target contributes zero for standard distance functions.

Returns

mean_distance : float

The mean distance from all configurations to the global optimum.

Examples

>>> from graphfla.landscape import BooleanLandscape
>>> from graphfla.analysis import mean_distance_to_global_optimum
>>> landscape = BooleanLandscape().build_from_data(
...     ["00", "01", "10", "11"], [0, 1, 2, 4], verbose=False)
>>> mean_distance_to_global_optimum(landscape)
1.0

Reuse cached dist_go values only when distance_func=None. An explicit callable is always evaluated and does not replace the cache.

Raises

RuntimeError

If the graph is not initialized, required attributes are missing, or the global optimum has not been determined.