copycat/slipnet_analysis/compute_letter_paths.py

"""
Compute minimum hops from each node to the nearest letter node (a-z) in the slipnet.
Like Erdos number, but starting from letter nodes.
Adds 'minPathToLetter' field to each node in the JSON.
"""

import json
import networkx as nx

def load_slipnet(filepath):
    with open(filepath, 'r') as f:
        return json.load(f)

def save_slipnet(data, filepath):
    with open(filepath, 'w') as f:
        json.dump(data, f, indent=2)

def build_graph(data):
    """Build an undirected unweighted NetworkX graph from slipnet JSON."""
    G = nx.Graph()  # Undirected graph - edges work both ways

    # Add all nodes
    for node in data['nodes']:
        G.add_node(node['name'])

    # Add edges (unweighted - each edge counts as 1 hop)
    for link in data['links']:
        G.add_edge(link['source'], link['destination'])

    return G

def get_letter_nodes():
    """Return set of letter nodes (a-z)."""
    return set(chr(i) for i in range(ord('a'), ord('z') + 1))

def compute_min_hops_to_letters(G, letter_nodes):
    """
    Compute minimum hops from each node to the nearest letter node.
    Like Erdos number but for letters.
    Returns dict: node_name -> {hops, path, nearest_letter}
    """
    results = {}

    # For each node, find shortest path (by hop count) to any letter
    for node in G.nodes():
        if node in letter_nodes:
            # Letters have 0 hops to themselves
            results[node] = {
                'hops': 0,
                'path': [node],
                'nearestLetter': node
            }
        else:
            min_hops = float('inf')
            min_path = None
            nearest_letter = None

            for letter in letter_nodes:
                try:
                    # Find shortest path by hop count (no weight parameter)
                    path = nx.shortest_path(G, source=node, target=letter)
                    hops = len(path) - 1  # Number of edges = nodes - 1
                    if hops < min_hops:
                        min_hops = hops
                        min_path = path
                        nearest_letter = letter
                except nx.NetworkXNoPath:
                    continue

            if min_path is not None:
                results[node] = {
                    'hops': min_hops,
                    'path': min_path,
                    'nearestLetter': nearest_letter
                }
            else:
                results[node] = {
                    'hops': None,
                    'path': None,
                    'nearestLetter': None
                }

    return results

def main():
    filepath = r'C:\Users\alexa\copycat\slipnet_analysis\slipnet.json'

    # Load the slipnet
    data = load_slipnet(filepath)
    print(f"Loaded slipnet with {data['nodeCount']} nodes and {data['linkCount']} links")

    # Build the graph
    G = build_graph(data)
    print(f"Built graph with {G.number_of_nodes()} nodes and {G.number_of_edges()} edges")

    # Get letter nodes
    letter_nodes = get_letter_nodes()
    print(f"Letter nodes: {sorted(letter_nodes)}")

    # Compute minimum hops to letters
    path_results = compute_min_hops_to_letters(G, letter_nodes)

    # Find max hops among reachable nodes
    max_hops = max(r['hops'] for r in path_results.values() if r['hops'] is not None)
    unreachable_hops = 2 * max_hops
    print(f"Max hops among reachable nodes: {max_hops}")
    print(f"Assigning unreachable nodes hops = 2 * {max_hops} = {unreachable_hops}")

    # Assign unreachable nodes hops = 2 * max_hops
    for node_name, result in path_results.items():
        if result['hops'] is None:
            result['hops'] = unreachable_hops
            result['path'] = None  # No path exists
            result['nearestLetter'] = None

    # Add results to each node in the JSON
    for node in data['nodes']:
        node_name = node['name']
        if node_name in path_results:
            result = path_results[node_name]
            node['minPathToLetter'] = {
                'hops': result['hops'],
                'path': result['path'],
                'nearestLetter': result['nearestLetter']
            }

    # Save the updated JSON
    save_slipnet(data, filepath)
    print(f"\nUpdated slipnet saved to {filepath}")

    # Print summary sorted by hops
    print("\n=== Summary of minimum hops to letter nodes (Erdos-style) ===")
    reachable_nodes = [(n['name'], n['minPathToLetter']) for n in data['nodes']
                       if 'minPathToLetter' in n and n['minPathToLetter']['path'] is not None
                       and n['minPathToLetter']['hops'] > 0]
    unreachable_nodes = [(n['name'], n['minPathToLetter']) for n in data['nodes']
                         if 'minPathToLetter' in n and n['minPathToLetter']['path'] is None
                         and n['minPathToLetter']['hops'] > 0]

    # Sort by hops, then by name
    reachable_nodes.sort(key=lambda x: (x[1]['hops'], x[0]))
    unreachable_nodes.sort(key=lambda x: x[0])

    print(f"\n{'Node':<30} {'Hops':<6} {'Nearest':<8} {'Path'}")
    print("-" * 80)

    for name, info in reachable_nodes:
        path_str = ' -> '.join(info['path'])
        print(f"{name:<30} {info['hops']:<6} {info['nearestLetter']:<8} {path_str}")

    if unreachable_nodes:
        print(f"\nUnreachable nodes (assigned hops = {unreachable_hops}):")
        for name, info in unreachable_nodes:
            print(f"  {name:<30} (depth: {[n['conceptualDepth'] for n in data['nodes'] if n['name'] == name][0]})")

if __name__ == '__main__':
    main()