Path Entropy

The problem

It is difficult to tell if a network's layout is organized or cluttered with unnecessary noise. You need a way to see if paths are following a clear structure or wandering aimlessly.

What it does

It looks at all possible routes in a network and calculates a score based on how much variety there is in their lengths. It identifies whether the paths are consistent or scattered.

Why it matters

It provides a clear way to measure the structural noise of a network's layout.

Validation

It was run in the sandbox and it failed. run output shows an error/traceback — the artifact does NOT run clean.

$ python3 path_entropy.py
File "/work/path_entropy.py", line 140
    if __name__ == "__main__":
TabError: inconsistent use of tabs and spaces in indentation

No screenshot — there is nothing working to show. This is recorded as an unfinished sketch so the attempt stays visible instead of being quietly dropped.

The code

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

#!/usr/bin/env python3
"""
Path Entropy Score — Shannon Entropy of Path Length Frequencies
===============================================================
Quantifies the structural noise in a graph by measuring how uniformly
path lengths are distributed across all-pairs shortest paths.

A graph where all paths have roughly the same length yields low entropy
(ordered, predictable). A graph with wide-ranging path lengths yields
high entropy (noisy, structurally diverse).

Input: adjacency list (nodes and their outgoing edges with weights)
Output: Path Entropy score [0, +inf), where:
  - 0 = all paths have identical length (zero noise)
  - high = uniform or chaotic distribution of path lengths

Interpretation bands:
  0.0 - 1.0  : highly ordered / deterministic routing
  1.0 - 2.0  : moderately structured
  2.0 - 3.0  : notable structural variance
  3.0+       : high structural noise / entropy

Run at bottom of this file or `python path_entropy.py`.
"""

import math
import heapq
from collections import Counter
from typing import Dict, List, Tuple


def dijkstra_all_pairs(
	graph: dict
) -> List[Tuple]:
	"""
	Compute the shortest path from every node to every other node.
	Returns list of (source, target, shortest_path_cost).
	"""
	results = []
	for source in graph:
		dist = {node: float("inf") for node in graph}
		dist[source] = 0.0
		pq = [(0.0, source)]
		while pq:
			d, u = heapq.heappop(pq)
			if d > dist[u]:
				continue
			for v, w in graph.get(u, []):
				nd = d + w
				if nd < dist[v]:
					dist[v] = nd
					heapq.heappush(pq, (nd, v))
		for target in graph:
			if target != source and dist[target] < float("inf"):
				results.append((source, target, dist[target]))
	return results


def path_length_frequencies(
	graph: Dict[str, List[Tuple[str, int]]]
) -> Tuple[Counter, int, List[Tuple]]:
	"""
	Run all-pairs shortest paths and bin path lengths into a frequency
	histogram. Returns (Counter of length->count, total_paths, all_results).
	"""
	all_pairs = dijkstra_all_pairs(graph)
	if not all_pairs:
		return Counter(), 0, all_pairs
	total = len(all_pairs)
	freq = Counter()
	for src, tgt, cost in all_pairs:
		freq[cost] += 1
	return freq, total, all_pairs


def shannon_entropy(frequencies: Counter, total: int) -> float:
	"""
	Compute Shannon Entropy over a discrete distribution: H = -sum(p * log2(p)).
	Boundary: returns 0.0 if total == 0.
	"""
	if total == 0:
		return 0.0
	entropy = 0.0
	for count in frequencies.values():
		p = count / total
		if p > 0:
			entropy -= p * math.log2(p)
	return entropy


def path_entropy_score(graph: dict) -> dict:
	"""
	Primary entry point. Compute Path Entropy Score from a weighted graph
	represented as an adjacency list.

	Graph format:
	{
		"A": [("B", 3), ("C", 1)],
		"B": [("D", 2)],
		"C": [("B", 1), ("D", 5)],
		"D": []
	}

	Each key is a node id; value is list of (neighbor, weight) tuples.
	Weights must be positive numbers.

	Returns dictionary with:
	  - "path_entropy_score": floats
	  - "total_paths": number of valid all-pairs shortest paths
	  - "unique_path_lengths": number of distinct path-length bins
	  - "length_bins": frequency of each path length
	  - "interpretation": human readable summary
	"""
	freq, total, all_results = path_length_frequencies(graph)
	entropy = shannon_entropy(freq, total)
	n_unique = len(freq)
	sorted_bins = dict(sorted(freq.items()))

	if entropy < 1.0:
		verdict = "low noise (highly structured)"
	elif entropy < 2.0:
		verdict = "moderate noise (predictable variation)"
	elif entropy < 3.0:
		verdict = "elevated noise (significant diversity)"
	else:
		verdict = "high noise (chaotic / deeply heterogeneous)"

	return {
		"path_entropy_score": round(entropy, 4),
		"total_paths_analyzed": total,
		"unique_path_lengths": n_unique,
		"length_bins": sorted_bins,
		"interpretation": f"Entropy={round(entropy, 4)} — {verdict}",
	}


        # ---------------------------------------------------------------------------
        # Main execution
        # ---------------------------------------------------------------------------
        if __name__ == "__main__":
            import json
            
            # Read graph from opencode.json
            with open('opencode.json', 'r') as f:
                graph = json.load(f)
            
            # Calculate and print entropy
            result = path_entropy_score(graph)
            # Verification: print the results
            print("=" * 60)
            print("PATH ENTROPY SCORE — Shannon Entropy of Path Length Frequencies")
            print("=" * 60)
            
            for k, v in result.items():
                print(f" {k}: {v}")