Trace-Decay_Path_Weighting

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 trace_decay.py
Found 2 paths from A to End: 

Path: ['A', 'B', 'D', 'End'], 
 Score: 3.44

Path: ['A', 'C', 'D', 'End'], 
 Score: 6.84

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 — 125 lines, one file, standard library only.

# Trace-Decay Path Weighting v2 — Path Ranking & Optimal Selection

from collections import defaultdict


DEFAULT_GRAPH = None


def _get_default_graph():
    from collections import defaultdict
    graph = defaultdict(dict)
    graph['A']['B'] = 2
    graph['A']['C'] = 3
    graph['B']['D'] = 1
    graph['C']['D'] = 4
    graph['D']['End'] = 1
    return graph


def find_all_paths(graph, start, end, path=None, visited=None):
    """
    DFS to find all paths between start and end nodes
    """
    if graph is None:
        graph = _get_default_graph()
    if path is None:
        path = []
    if visited is None:
        visited = set()
    path = path + [start]
    visited = visited | {start}
    if start == end:
        return [path]

    paths = []
    for node in graph[start]:
        if node not in visited:
            new_paths = find_all_paths(graph, node, end, path, visited)
            for new_path in new_paths:
                paths.append(new_path)
    return paths


def calculate_path_score(path, graph=None, decay_factor=0.8):
    """
    Calculate path score with exponential decay for each step
    """
    if graph is None:
        graph = _get_default_graph()
    score = 0
    for i, node in enumerate(path[:-1]):
        next_node = path[i + 1]
        edge_weight = graph[node][next_node]
        score += edge_weight * (decay_factor ** i)
    return score


def rank_paths(paths, graph=None, decay_factor=0.8):
    """
    Rank all paths by their decayed score (lowest first = best).
    Returns a list of (path, score) tuples sorted best-to-worst.
    """
    if graph is None:
        graph = _get_default_graph()
    scored = [(p, calculate_path_score(p, graph, decay_factor)) for p in paths]
    scored.sort(key=lambda x: x[1])
    return scored


def select_optimal_path(paths, graph=None, decay_factor=0.8):
    """
    Return the single optimal (lowest-score) path and its score.
    """
    if not paths:
        return None, None
    if graph is None:
        graph = _get_default_graph()
    scored = rank_paths(paths, graph, decay_factor)
    return scored[0]


def main():
    """
    Example usage with a sample graph — v2 shows ranking + optimal path.
    """
    graph = defaultdict(dict)
    graph['A']['B'] = 2      # Start node → B (cost 2)
    graph['A']['C'] = 3      # Start node → C (cost 3)
    graph['B']['D'] = 1      # B → D (cost 1)
    graph['C']['D'] = 4      # C → D (cost 4)
    graph['D']['End'] = 1    # D → End (cost 1)

    start_node = 'A'
    end_node = 'End'
    decay_factor = 0.8       # Adjustable decay rate (0 < factor < 1)

    paths = find_all_paths(graph, start_node, end_node)

    print(f"Found {len(paths)} paths from {start_node} to {end_node}:\n")
    for path in paths:
        score = calculate_path_score(path, graph, decay_factor)
        print(f"  Path: {path}, Score: {score:.2f}")

    # --- v2: ranking ---
    print("\n" + "=" * 44)
    print("v2 — Ranked Paths (lowest decayed score first)")
    print("=" * 44 + "\n")

    ranked = rank_paths(paths, graph, decay_factor)
    for rank, (path, score) in enumerate(ranked, 1):
        label = "★ OPTIMAL" if rank == 1 else ""
        print(f"  #{rank} {label}".rstrip())
        print(f"      Path: {path}")
        print(f"      Score: {score:.2f}\n")

    # --- v2: optimal path highlight
    optimal_path, optimal_score = select_optimal_path(paths, graph, decay_factor)
    print("-" * 44)
    print(f"Selected optimal path: {optimal_path}")
    print(f"Optimal score:         {optimal_score:.2f}")
    print("-" * 44)


if __name__ == "__main__":
    main()