State-Space Coverage Estimator

The problem

It is difficult to know which parts of a complex system are most important to explore or test. This makes it hard to prioritize where to focus efforts.

What it does

It calculates a score for different parts of a system based on how reachable they are. It then provides an estimate of how much of the system has been covered.

Why it matters

It helps prioritize exploration by identifying which parts of a system are most significant to discover.

Validation

It was run inside an isolated container with no network access. This is the exact command and the real output it produced — captured process output, not written by a model.

$ python3 coverage_estimator.py
Reachability Scores: {0: 3, 1: 3, 2: 3, 3: 3}
Connectivity Density: 0.42
Estimated Coverage: 1.25

A screenshot of that run.

A clean run proves this does what is shown above, in a CPU-only sandbox. It is a small research demo — not a production tool, and nothing here was published anywhere.

The code

All of it — 59 lines, one file, standard library only.

# State-Space Coverage Estimator using Reachability-Based Coverage
from collections import deque

class StateSpaceCoverageEstimator:
    def __init__(self, edges):
        self.edges = edges
        self.nodes = set()
        for u, v in edges:
            self.nodes.add(u)
            self.nodes.add(v)
        self.graph = self._build_graph()

    def _build_graph(self):
        graph = {} 
        for node in self.nodes:
            graph[node] = []
        for u, v in self.edges:
            graph[u].append(v)
        return graph

    def calculate_reachability_scores(self):
        scores = {}
        for node in self.nodes:
            visited = set()
            queue = deque([node])
            visited.add(node)
            while queue:
                current = queue.popleft()
                for neighbor in self.graph.get(current, []):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            scores[node] = len(visited) - 1  # Exclude itself
        return scores

    def calculate_connectivity_density(self):
        total_possible_edges = len(self.nodes) * (len(self.nodes) - 1)
        actual_edges = sum(len(neighbors) for neighbors in self.graph.values())
        return actual_edges / total_possible_edges

    def estimate_coverage(self):
        scores = self.calculate_reachability_scores()
        density = self.calculate_connectivity_density()
        avg_score = sum(scores.values()) / len(scores)
        return avg_score * density

# Example Usage
if __name__ == "__main__":
    # Define state transitions as directed edges
    state_transitions = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]
    estimator = StateSpaceCoverageEstimator(state_transitions)
    print(f"Reachability Scores: {estimator.calculate_reachability_scores()}")
    print(f"Connectivity Density: {estimator.calculate_connectivity_density():.2f}")
    print(f"Estimated Coverage: {estimator.estimate_coverage():.2f}")

# How to run:
# 1. Save this as `coverage_estimator.py`
# 2. Run with Python 3: `python coverage_estimator.py`
# 3. Modify `state_transitions` to match your state machine's structure