Graph Path Contextualizer

The problem

It is difficult to make sense of complex, multi-step paths because it is hard to see which routes share similar patterns or characteristics.

What it does

It groups different paths based on the types of steps they take and ranks them by how unique or diverse each route is.

Why it matters

It allows you to see patterns and unique paths in complex networks more clearly.

Validation

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

$ python3 graph_tool.py
Traceback (most recent call last):
  File "/work/graph_path_contextualizer.py", line 78, in <module>
    main()
  File "/work/graph_path_contextualizer.py", line 63, in main
    groups = group_paths(paths, graph)
             ^^^^^^^^^^^
UnboundLocalError: cannot access local variable 'group_paths' where it is not associated with a value

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

# graph_tool.py
import math
from collections import defaultdict

class Graph:
    def __init__(self):
        self.nodes = {
            'A': {'type': 'Person'},
            'B': {'type': 'Organization'},
            'C': {'type': 'Location'},
            'D': {'type': 'Person'},
            'E': {'type': 'Event'}
        }
        self.edges = {
            'A': ['B'],
            'B': ['C', 'E'],
            'C': ['D'],
            'D': ['E'],
            'E': ['B']
        }
    
    def get_degree(self, node):
        return len(self.edges.get(node, []))

    @staticmethod
    def multi_hop_rank(path, graph):
        depth = len(path) - 1
        connectivity = sum(graph.get_degree(node) for node in path) / depth if depth else 0
        return depth * connectivity

    @staticmethod
    def path_entropy(path, graph):
        node_types = [graph.nodes[node]['type'] for node in path]
        type_counts = defaultdict(int)
        for t in node_types:
            type_counts[t] += 1
        total = len(node_types)
        entropy = 0
        for count in type_counts.values():
            p = count / total
            entropy -= p * math.log2(p)
        return entropy

    @staticmethod
    def combine_scores(mhop_score, entropy, alpha=0.5, beta=0.5):
        return alpha * mhop_score + beta * entropy

    @staticmethod
    def group_paths(paths, graph):
        groups = defaultdict(list)
        for path in paths:
            types_in_path = set(graph.nodes[node]['type'] for node in path)
            group_key = tuple(sorted(types_in_path))
            groups[group_key].append(path)
        return groups

    @staticmethod
    def path_reachability(path):
        return len(set(path))  # New method to calculate unique node coverage

def main():
    graph = Graph()
    paths = [
        ['A', 'B', 'C', 'D', 'E'],
        ['A', 'B', 'C'],
        ['B', 'C', 'D', 'E'],
        ['B', 'E', 'B'],
        ['C', 'D', 'E']
    ]
    ranked_paths = []
    for path in paths:
        mhop = Graph.multi_hop_rank(path, graph)
        ent = Graph.path_entropy(path, graph)
        reach = Graph.path_reachability(path)  # New calculation
        score = Graph.combine_scores(mhop, ent)
        ranked_paths.append((path, mhop, ent, score, reach))  # Include reachability
    
    ranked_paths.sort(key=lambda x: x[3], reverse=True)
    groups = Graph.group_paths(paths, graph)
    print("Path Groups:\n")
    group_entropy = {}
    for group_key, group_paths in groups.items():
        group_entropy[group_key] = max(Graph.path_entropy(p, graph) for p in group_paths)
    
    sorted_groups = sorted(groups.items(), key=lambda kv: group_entropy[kv[0]], reverse=True)
    for group_key, group_paths in sorted_groups:
        group_paths_ranked = sorted(group_paths, key=lambda p: Graph.path_entropy(p, graph), reverse=True)
        print(f"Group: {group_key}")
        for path in group_paths_ranked:
            mhop = Graph.multi_hop_rank(path, graph)
            ent = Graph.path_entropy(path, graph)
            reach = Graph.path_reachability(path)  # New calculation
            score = Graph.combine_scores(mhop, ent)
            print(f"Path: {path}, Combined Score: {score}, MHop Rank: {mhop}, Entropy: {ent}, Reachability: {reach}\n")  # Include in output

if __name__ == '__main__':
    main()