graph_utils.py

"""
graph_utils.py
==============
Provides the Graph class used by Dijkstra and Floyd‑Warshall.

Responsibilities
----------------
- Store the adjacency list, edge list, and node set.
- Build an adjacency matrix (for Floyd‑Warshall).
- Map nodes ↔ integer indices.
- Auto‑generate (x, y) coordinates in a circular layout (used by the GUI
  drawing canvas).

Space Complexity
----------------
- Adjacency list  : O(V + E)
- Adjacency matrix: O(V²)
- Coordinates dict: O(V)
"""

import math


class Graph:
    """
    Directed, weighted graph with multiple representation layers.

    Parameters
    ----------
    adj_dict : dict
        {node: [(neighbor, weight), ...], ...}
        All nodes that appear as neighbors but have no outgoing edges
        must also be present as keys (possibly with an empty list).
    """

    def __init__(self, adj_dict: dict):
        # ------------------------------------------------------------------ #
        # 1. Store raw adjacency list
        # ------------------------------------------------------------------ #
        # Time : O(V + E)  –– iterate all nodes + all edges
        # Space: O(V + E)
        self.adj = {node: list(neighbors) for node, neighbors in adj_dict.items()}

        # ------------------------------------------------------------------ #
        # 2. Collect the full node set (includes isolated / sink nodes)
        # ------------------------------------------------------------------ #
        # Time : O(V + E)
        node_set = set(self.adj.keys())
        for neighbors in self.adj.values():
            for neighbor, _ in neighbors:
                node_set.add(neighbor)
                # Ensure every discovered node has an entry in adj
                if neighbor not in self.adj:
                    self.adj[neighbor] = []

        # Sorted for deterministic ordering (required by matrix + index maps)
        self.nodes = sorted(node_set)          # list[node]
        self.n     = len(self.nodes)           # V – number of vertices

        # ------------------------------------------------------------------ #
        # 3. Build node ↔ index maps
        # ------------------------------------------------------------------ #
        # Time : O(V)  –– one pass over sorted node list
        # Space: O(V)
        self.node_to_idx: dict = {node: i for i, node in enumerate(self.nodes)}
        self.idx_to_node: dict = {i: node for i, node in enumerate(self.nodes)}

        # ------------------------------------------------------------------ #
        # 4. Flatten edge list as (u, v, weight) tuples
        # ------------------------------------------------------------------ #
        # Time : O(E)
        # Space: O(E)
        self.edges = []
        for u, neighbors in self.adj.items():
            for v, w in neighbors:
                self.edges.append((u, v, w))

        # ------------------------------------------------------------------ #
        # 5. Build adjacency matrix   (used by Floyd‑Warshall)
        # ------------------------------------------------------------------ #
        # Time : O(V²) initialisation + O(E) edge insertion  →  O(V² + E)
        # Space: O(V²)
        INF = float('inf')
        self.matrix = [[INF] * self.n for _ in range(self.n)]
        for i in range(self.n):
            self.matrix[i][i] = 0            # zero‑cost self‑loops
        for u, v, w in self.edges:
            i = self.node_to_idx[u]
            j = self.node_to_idx[v]
            # Keep the minimum weight if parallel edges exist
            if w < self.matrix[i][j]:
                self.matrix[i][j] = w

        # ------------------------------------------------------------------ #
        # 6. Generate circular coordinates   (used by GUI drawing)
        # ------------------------------------------------------------------ #
        # Nodes are placed evenly around a unit circle.
        # Time : O(V)
        # Space: O(V)
        self.coords = self._generate_circular_coords()

    # ---------------------------------------------------------------------- #
    # Internal helpers
    # ---------------------------------------------------------------------- #

    def _generate_circular_coords(self) -> dict:
        """
        Place V nodes evenly around a circle of radius 1 centred at (0, 0).

        Returns
        -------
        dict : {node: (x, y)}

        Time  : O(V)
        Space : O(V)
        """
        coords = {}
        for i, node in enumerate(self.nodes):
            angle = 2 * math.pi * i / max(self.n, 1)
            coords[node] = (math.cos(angle), math.sin(angle))
        return coords

    # ---------------------------------------------------------------------- #
    # Public helpers
    # ---------------------------------------------------------------------- #

    def neighbors(self, node) -> list:
        """
        Return the adjacency list for *node*.

        Time : O(1)  – dict lookup
        Space: O(1)
        """
        return self.adj.get(node, [])



    def __repr__(self) -> str:
        return (f"Graph(V={self.n}, E={len(self.edges)}, "
                f"nodes={self.nodes})")