Untitled

/**
 * Undirected graph storing artist-song relationships using an adjacency list.
 *
 * @author Leguejou Awunganyi
 * @author Ishita Punna
 * @version 2026-02-08
 */
public class Graph {

    /**
     * Result returned when a node is added.
     */
    public static class AddNodeResult {

        /**
         * Newly created graph node.
         */
        public GraphNode node;

        /**
         * True when the graph doubled before insertion.
         */
        public boolean resized;
    }

    /**
     * Result describing graph statistics.
     */
    public static class Stats {

        /**
         * Number of connected components.
         */
        public int components;

        /**
         * Size of the largest connected component.
         */
        public int largestSize;

        /**
         * Diameter of the largest connected component.
         */
        public int diameter;
    }

    /**
     * Adjacency-list node.
     */
    private static class EdgeNode {

        /**
         * Neighbor index.
         */
        private int neighbor;

        /**
         * Next edge in the linked list.
         */
        private EdgeNode next;

        /**
         * Create an adjacency-list node.
         *
         * @param n neighbor index
         * @param nx next edge
         */
        EdgeNode(int n, EdgeNode nx) {
            neighbor = n;
            next = nx;
        }
    }

    /**
     * Graph nodes by slot.
     */
    private GraphNode[] nodes;

    /**
     * True when a slot currently holds a live node.
     */
    private boolean[] active;

    /**
     * Adjacency lists by slot.
     */
    private EdgeNode[] adjacency;

    /**
     * Current graph capacity.
     */
    private int capacity;

    /**
     * Number of active nodes.
     */
    private int count;

    /**
     * Create a graph with the given initial capacity.
     *
     * @param initialSize starting capacity
     */
    public Graph(int initialSize) {
        capacity = initialSize;
        nodes = new GraphNode[capacity];
        active = new boolean[capacity];
        adjacency = new EdgeNode[capacity];
        count = 0;
    }

    /**
     * Add a new graph node, reusing freed slots when possible.
     *
     * @param name node name
     * @param isArtist true for artists
     * @return result containing the node and resize flag
     */
    public AddNodeResult addNode(String name, boolean isArtist) {
        AddNodeResult result = new AddNodeResult();
        int slot = firstFreeSlot();

        if (slot < 0) {
            resize();
            result.resized = true;
            slot = firstFreeSlot();
        }

        GraphNode node = new GraphNode(name, isArtist, slot);
        nodes[slot] = node;
        active[slot] = true;
        adjacency[slot] = null;
        count++;
        result.node = node;
        return result;
    }

    /**
     * Add an undirected edge between two nodes.
     *
     * @param firstNode first node
     * @param secondNode second node
     */
    public void addEdge(GraphNode firstNode, GraphNode secondNode) {
        if (firstNode == null || secondNode == null) {
            return;
        }

        int firstIndex = firstNode.getIndex();
        int secondIndex = secondNode.getIndex();

        if (!isLive(firstIndex) || !isLive(secondIndex) 
            || firstIndex == secondIndex) {
            return;
        }

        if (!hasDirectedEdge(firstIndex, secondIndex)) {
            adjacency[firstIndex] = new EdgeNode(secondIndex, 
                adjacency[firstIndex]);
        }

        if (!hasDirectedEdge(secondIndex, firstIndex)) {
            adjacency[secondIndex] = new EdgeNode(firstIndex, 
                adjacency[secondIndex]);
        }
    }

    /**
     * Check whether an undirected edge exists.
     *
     * @param firstNode first node
     * @param secondNode second node
     * @return true if the edge exists
     */
    public boolean hasEdge(GraphNode firstNode, GraphNode secondNode) {
        if (firstNode == null || secondNode == null) {
            return false;
        }

        int firstIndex = firstNode.getIndex();
        int secondIndex = secondNode.getIndex();

        return isLive(firstIndex) && isLive(secondIndex)
            && hasDirectedEdge(firstIndex, secondIndex);
    }

    /**
     * Remove a node and all of its incident edges.
     *
     * @param node node to remove
     */
    public void removeNode(GraphNode node) {
        if (node == null) {
            return;
        }

        int index = node.getIndex();
        if (!isLive(index)) {
            return;
        }

        EdgeNode current = adjacency[index];
        while (current != null) {
            removeDirectedEdge(current.neighbor, index);
            current = current.next;
        }

        adjacency[index] = null;
        active[index] = false;
        nodes[index] = null;
        count--;
    }

    /**
     * Get the current graph capacity.
     *
     * @return graph capacity
     */
    public int capacity() {
        return capacity;
    }

    /**
     * Compute the connected-component statistics using Union/FIND and Floyd.
     *
     * @return graph statistics
     */
    public Stats stats() {
        Stats stats = new Stats();

        if (count == 0) {
            return stats;
        }

        int[] parent = new int[capacity];
        int[] weights = new int[capacity];

        initializeUnionFind(parent, weights);
        buildConnectedComponents(parent, weights);

        int[] componentSizes = new int[capacity];
        boolean[] seenRoot = new boolean[capacity];

        for (int i = 0; i < capacity; i++) {
            if (active[i]) {
                int root = find(parent, i);
                componentSizes[root]++;

                if (!seenRoot[root]) {
                    seenRoot[root] = true;
                    stats.components++;
                }
            }
        }

        for (int i = 0; i < capacity; i++) {
            if (seenRoot[i] && componentSizes[i] > stats.largestSize) {
                stats.largestSize = componentSizes[i];
            }
        }

        for (int i = 0; i < capacity; i++) {
            if (seenRoot[i] && componentSizes[i] == stats.largestSize) {
                int[] members = collectMembers(parent, i, componentSizes[i]);
                int diameter = floydDiameter(members, componentSizes[i]);
                if (diameter > stats.diameter) {
                    stats.diameter = diameter;
                }
            }
        }

        return stats;
    }

    /**
     * Initialize parent-pointer trees.
     *
     * @param parent parent array
     * @param weights subtree sizes
     */
    private void initializeUnionFind(int[] parent, int[] weights) {
        for (int i = 0; i < capacity; i++) {
            if (active[i]) {
                parent[i] = -1;
                weights[i] = 1;
            }
            else {
                parent[i] = -2;
                weights[i] = 0;
            }
        }
    }

    /**
     * Build components with weighted Union/FIND.
     *
     * @param parent parent array
     * @param weights subtree sizes
     */
    private void buildConnectedComponents(int[] parent, int[] weights) {
        for (int i = 0; i < capacity; i++) {
            if (!active[i]) {
                continue;
            }

            EdgeNode current = adjacency[i];
            while (current != null) {
                int neighbor = current.neighbor;
                if (active[neighbor] && i < neighbor) {
                    union(parent, weights, i, neighbor);
                }
                current = current.next;
            }
        }
    }

    /**
     * Weighted union.
     *
     * @param parent parent array
     * @param weights subtree sizes
     * @param a first node
     * @param b second node
     */
    private void union(int[] parent, int[] weights, int a, int b) {
        int rootA = find(parent, a);
        int rootB = find(parent, b);

        if (rootA == rootB) {
            return;
        }

        if (weights[rootA] < weights[rootB]) {
            parent[rootA] = rootB;
            weights[rootB] += weights[rootA];
        }
        else {
            parent[rootB] = rootA;
            weights[rootA] += weights[rootB];
        }
    }

    /**
     * Find with path compression.
     *
     * @param parent parent array
     * @param curr current node
     * @return root index
     */
    private int find(int[] parent, int curr) {
        if (parent[curr] == -1) {
            return curr;
        }

        parent[curr] = find(parent, parent[curr]);
        return parent[curr];
    }

    /**
     * Collect members of one component.
     *
     * @param parent parent array
     * @param root component root
     * @param size expected size
     * @return component member indices
     */
    private int[] collectMembers(int[] parent, int root, int size) {
        int[] members = new int[size];
        int pos = 0;

        for (int i = 0; i < capacity; i++) {
            if (active[i] && find(parent, i) == root) {
                members[pos++] = i;
            }
        }

        return members;
    }

    /**
     * Compute diameter of one component using Floyd's algorithm.
     *
     * @param members component members
     * @param size component size
     * @return component diameter
     */
    private int floydDiameter(int[] members, int size) {
        if (size <= 1) {
            return 0;
        }

        int inf = Integer.MAX_VALUE / 4;
        int[][] dist = new int[size][size];
        int[] localIndex = new int[capacity];

        for (int i = 0; i < capacity; i++) {
            localIndex[i] = -1;
        }

        for (int i = 0; i < size; i++) {
            localIndex[members[i]] = i;
        }

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                }
                else {
                    dist[i][j] = inf;
                }
            }
        }

        for (int i = 0; i < size; i++) {
            EdgeNode current = adjacency[members[i]];
            while (current != null) {
                int j = localIndex[current.neighbor];
                if (j >= 0) {
                    dist[i][j] = 1;
                }
                current = current.next;
            }
        }

        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                if (dist[i][k] == inf) {
                    continue;
                }
                for (int j = 0; j < size; j++) {
                    if (dist[k][j] == inf) {
                        continue;
                    }
                    int throughK = dist[i][k] + dist[k][j];
                    if (throughK < dist[i][j]) {
                        dist[i][j] = throughK;
                    }
                }
            }
        }

        int diameter = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (dist[i][j] != inf && dist[i][j] > diameter) {
                    diameter = dist[i][j];
                }
            }
        }

        return diameter;
    }

    /**
     * Check whether a slot stores a live node.
     *
     * @param index slot index
     * @return true when live
     */
    private boolean isLive(int index) {
        return index >= 0 && index < capacity && active[index];
    }

    /**
     * Check whether a directed edge exists.
     *
     * @param from start slot
     * @param to end slot
     * @return true if the edge exists
     */
    private boolean hasDirectedEdge(int from, int to) {
        EdgeNode current = adjacency[from];
        while (current != null) {
            if (current.neighbor == to) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * Remove one directed edge from a list.
     *
     * @param from start slot
     * @param to end slot
     */
    private void removeDirectedEdge(int from, int to) {
        EdgeNode current = adjacency[from];
        EdgeNode previous = null;

        while (current != null) {
            if (current.neighbor == to) {
                if (previous == null) {
                    adjacency[from] = current.next;
                }
                else {
                    previous.next = current.next;
                }
                return;
            }

            previous = current;
            current = current.next;
        }
    }

    /**
     * Find the first open graph slot.
     *
     * @return free slot index or -1 if none
     */
    private int firstFreeSlot() {
        for (int i = 0; i < capacity; i++) {
            if (!active[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Double the graph capacity.
     */
    private void resize() {
        int newCapacity = capacity * 2;

        GraphNode[] newNodes = new GraphNode[newCapacity];
        boolean[] newActive = new boolean[newCapacity];
        EdgeNode[] newAdjacency = new EdgeNode[newCapacity];

        for (int i = 0; i < capacity; i++) {
            newNodes[i] = nodes[i];
            newActive[i] = active[i];
            newAdjacency[i] = adjacency[i];
        }

        nodes = newNodes;
        active = newActive;
        adjacency = newAdjacency;
        capacity = newCapacity;
    }
}