Untitled

import student.TestCase;

/**
 * Extra direct tests for Graph to improve mutation coverage.
 *
 * @author Leguejou Awunganyi
 * @author Ishita Punna
 * @version 2026-02-08
 */
public class GraphTest extends TestCase {

    /**
     * Test empty graph behavior and null-guard branches.
     */
    public void testEmptyGraphAndNullOperations() {
        Graph graph = new Graph(2);

        Graph.Stats stats = graph.stats();
        assertEquals(0, stats.components);
        assertEquals(0, stats.largestSize);
        assertEquals(0, stats.diameter);

        assertFalse(graph.hasEdge(null, null));

        graph.addEdge(null, null);
        graph.removeNode(null);

        assertEquals(2, graph.capacity());
    }

    /**
     * Test that removing a middle node clears incident edges and changes stats.
     */
    public void testRemoveNodeClearsEdgesAndChangesStats() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;

        graph.addEdge(a, b);
        graph.addEdge(b, c);

        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(b, a));
        assertTrue(graph.hasEdge(b, c));
        assertFalse(graph.hasEdge(a, c));

        Graph.Stats before = graph.stats();
        assertEquals(1, before.components);
        assertEquals(3, before.largestSize);
        assertEquals(2, before.diameter);

        graph.removeNode(b);

        assertFalse(graph.hasEdge(a, b));
        assertFalse(graph.hasEdge(b, a));
        assertFalse(graph.hasEdge(b, c));
        assertFalse(graph.hasEdge(c, b));

        // Removed node should stay inactive
        graph.addEdge(b, c);
        assertFalse(graph.hasEdge(b, c));

        Graph.Stats after = graph.stats();
        assertEquals(2, after.components);
        assertEquals(1, after.largestSize);
        assertEquals(0, after.diameter);
    }

    /**
     * Test freed-slot reuse and graph resize/copy behavior.
     */
    public void testReuseFreedSlotAndResizePreservesEdge() {
        Graph graph = new Graph(2);

        Graph.AddNodeResult add1 = graph.addNode(true);
        Graph.AddNodeResult add2 = graph.addNode(false);

        GraphNode first = add1.node;
        GraphNode second = add2.node;

        assertFalse(add1.resized);
        assertFalse(add2.resized);
        assertEquals(2, graph.capacity());

        graph.removeNode(first);

        Graph.AddNodeResult reusedAdd = graph.addNode(true);
        GraphNode reused = reusedAdd.node;

        assertFalse(reusedAdd.resized);
        assertEquals(first.getIndex(), reused.getIndex());

        graph.addEdge(reused, second);
        assertTrue(graph.hasEdge(reused, second));

        Graph.AddNodeResult resizeAdd = graph.addNode(false);
        assertTrue(resizeAdd.resized);
        assertEquals(4, graph.capacity());

        // Existing edge should survive resize copy
        assertTrue(graph.hasEdge(reused, second));
    }

    /**
     * Test equal-size largest components chooses the larger diameter.
     */
    public void testEqualLargestComponentsChooseLargerDiameter() {
        Graph graph = new Graph(8);

        // Component 1: triangle, size 3, diameter 1
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        graph.addEdge(a, b);
        graph.addEdge(b, c);
        graph.addEdge(a, c);

        // Component 2: path of 3, diameter 2
        GraphNode d = graph.addNode(true).node;
        GraphNode e = graph.addNode(false).node;
        GraphNode f = graph.addNode(true).node;
        graph.addEdge(d, e);
        graph.addEdge(e, f);

        Graph.Stats stats = graph.stats();
        assertEquals(2, stats.components);
        assertEquals(3, stats.largestSize);
        assertEquals(2, stats.diameter);
    }

    /**
     * Test a larger path diameter.
     */
    public void testLongerPathDiameter() {
        Graph graph = new Graph(8);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        graph.addEdge(a, b);
        graph.addEdge(b, c);
        graph.addEdge(c, d);

        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(4, stats.largestSize);
        assertEquals(3, stats.diameter);
    }
    
    /**
     * Test that resize copies multiple old edges, not just one.
     */
    public void testResizeKeepsMultipleOldEdges() {
        Graph graph = new Graph(3);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;

        graph.addEdge(a, b);
        graph.addEdge(b, c);

        Graph.AddNodeResult add4 = graph.addNode(false);
        GraphNode d = add4.node;

        assertTrue(add4.resized);
        assertEquals(6, graph.capacity());

        // Old matrix edges should still be present after resize
        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(b, c));
        assertFalse(graph.hasEdge(a, c));

        graph.addEdge(c, d);

        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(4, stats.largestSize);
        assertEquals(3, stats.diameter);
    }

    /**
     * Test removing the same node twice is safe and does not recreate edges.
     */
    public void testRemoveInactiveNodeTwice() {
        Graph graph = new Graph(3);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;

        graph.addEdge(a, b);
        assertTrue(graph.hasEdge(a, b));

        graph.removeNode(a);
        assertFalse(graph.hasEdge(a, b));

        // Second removal should hit the inactive-node early return
        graph.removeNode(a);
        assertFalse(graph.hasEdge(a, b));

        // Adding an edge with a removed node should do nothing
        graph.addEdge(a, b);
        assertFalse(graph.hasEdge(a, b));

        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(1, stats.largestSize);
        assertEquals(0, stats.diameter);
    }

    /**
     * Test equal largest components with the same diameter.
     */
    public void testEqualLargestComponentsSameDiameter() {
        Graph graph = new Graph(6);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        graph.addEdge(a, b);
        graph.addEdge(c, d);

        Graph.Stats stats = graph.stats();
        assertEquals(2, stats.components);
        assertEquals(2, stats.largestSize);
        assertEquals(1, stats.diameter);
    }

    /**
     * Test a cycle plus an isolated node to exercise visited false branches.
     */
    public void testCycleAndIsolatedNodeStats() {
        Graph graph = new Graph(5);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        graph.addEdge(a, b);
        graph.addEdge(b, c);
        graph.addEdge(c, a);

        Graph.Stats stats = graph.stats();
        assertEquals(2, stats.components);
        assertEquals(3, stats.largestSize);
        assertEquals(1, stats.diameter);

        assertFalse(graph.hasEdge(a, d));
        assertFalse(graph.hasEdge(d, a));
    }
    
    /**
     * Test stats for a single-node component and inactive-node edge checks.
     */
    public void testSingleNodeStatsAndInactiveNodeCheck() {
        Graph graph = new Graph(3);

        GraphNode a = graph.addNode(true).node;
        GraphNode inactive = new GraphNode("Ghost", false, 2);

        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(1, stats.largestSize);
        assertEquals(0, stats.diameter);

        assertFalse(graph.hasEdge(a, inactive));
        graph.addEdge(a, inactive);
        assertFalse(graph.hasEdge(a, inactive));
    }

    /**
     * Test that freed slots are reused in lowest-index order without resizing.
     */
    public void testReuseLowestFreedSlotOrder() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        assertEquals(0, a.getIndex());
        assertEquals(1, b.getIndex());
        assertEquals(2, c.getIndex());
        assertEquals(3, d.getIndex());

        graph.removeNode(b);
        graph.removeNode(d);

        Graph.AddNodeResult eAdd = graph.addNode(true);
        Graph.AddNodeResult fAdd = graph.addNode(false);

        assertFalse(eAdd.resized);
        assertFalse(fAdd.resized);
        assertEquals(1, eAdd.node.getIndex());
        assertEquals(3, fAdd.node.getIndex());
        assertEquals(4, graph.capacity());

        Graph.Stats stats = graph.stats();
        assertEquals(4, stats.components);
        assertEquals(1, stats.largestSize);
        assertEquals(0, stats.diameter);
    }

    /**
     * Test resize after reuse preserves old edges and correct component stats.
     */
    public void testResizeAfterReusePreservesEdgesAndStats() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        graph.addEdge(a, b);
        graph.addEdge(c, d);

        graph.removeNode(b);
        assertFalse(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(c, d));

        Graph.AddNodeResult eAdd = graph.addNode(true);
        assertFalse(eAdd.resized);
        assertEquals(1, eAdd.node.getIndex());

        graph.addEdge(eAdd.node, c);
        assertTrue(graph.hasEdge(eAdd.node, c));
        assertTrue(graph.hasEdge(c, d));

        Graph.AddNodeResult fAdd = graph.addNode(false);
        assertTrue(fAdd.resized);
        assertEquals(8, graph.capacity());

        // Existing edges should survive the resize.
        assertTrue(graph.hasEdge(eAdd.node, c));
        assertTrue(graph.hasEdge(c, d));
        assertFalse(graph.hasEdge(a, eAdd.node));

        Graph.Stats stats = graph.stats();
        assertEquals(3, stats.components);
        assertEquals(3, stats.largestSize);
        assertEquals(2, stats.diameter);
    }
    
    /**
     * Test two equal largest path components and then break one by removal.
     */
    public void testEqualLargestPathsThenBreakOne() {
        Graph graph = new Graph(8);

        // Component 1: A-B-C path (size 3, diameter 2)
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        graph.addEdge(a, b);
        graph.addEdge(b, c);

        // Component 2: D-E-F path (size 3, diameter 2)
        GraphNode d = graph.addNode(false).node;
        GraphNode e = graph.addNode(true).node;
        GraphNode f = graph.addNode(false).node;
        graph.addEdge(d, e);
        graph.addEdge(e, f);

        Graph.Stats before = graph.stats();
        assertEquals(2, before.components);
        assertEquals(3, before.largestSize);
        assertEquals(2, before.diameter);

        // Break one largest component into two isolated pieces
        graph.removeNode(e);

        Graph.Stats after = graph.stats();
        assertEquals(3, after.components);
        assertEquals(3, after.largestSize);
        assertEquals(2, after.diameter);

        assertFalse(graph.hasEdge(d, e));
        assertFalse(graph.hasEdge(e, f));
    }
    
    /**
     * Test that an edge between the highest old indices survives resize.
     */
    public void testHighIndexEdgeSurvivesResize() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;   // 0
        GraphNode b = graph.addNode(false).node;  // 1
        GraphNode c = graph.addNode(true).node;   // 2
        GraphNode d = graph.addNode(false).node;  // 3

        assertEquals(0, a.getIndex());
        assertEquals(1, b.getIndex());
        assertEquals(2, c.getIndex());
        assertEquals(3, d.getIndex());

        graph.addEdge(c, d);
        assertTrue(graph.hasEdge(c, d));
        assertTrue(graph.hasEdge(d, c));
        assertFalse(graph.hasEdge(a, b));

        Graph.AddNodeResult add5 = graph.addNode(true);
        assertTrue(add5.resized);
        assertEquals(8, graph.capacity());

        // Edge in the last old row/column should still be there after copy
        assertTrue(graph.hasEdge(c, d));
        assertTrue(graph.hasEdge(d, c));
        assertFalse(graph.hasEdge(a, b));

        Graph.Stats stats = graph.stats();
        assertEquals(4, stats.components);
        assertEquals(2, stats.largestSize);
        assertEquals(1, stats.diameter);
    }
    
    
    /**
     * Test insert into a table where all slots are tombstones,
     * forcing the end-of-loop firstTomb path on
     */
    public void testInsertAllTombstonesNoNullSlot() {
        // Use size 4 so we can fill it completely with tombstones
        Hash hash = new Hash("artist", 4);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode b = new GraphNode("B", true, 1);

        // Fill to half capacity to avoid resize, then remove both
        hash.insert("A", a);
        hash.insert("B", b);
        hash.remove("A");
        hash.remove("B");

        // Now both slots are tombstones, no null slots exist
        // Insert should find firstTomb and use it
        GraphNode c = new GraphNode("C", true, 2);
        Hash.InsertResult r = hash.insert("C", c);

        assertTrue(r.inserted);
        assertFalse(r.duplicate);
        assertEquals(1, hash.size());
        assertSame(c, (GraphNode)hash.find("C"));
    }

    /**
     * Test count increments correctly via the firstTomb path
     */
    public void testCountAfterTombstoneReinsert() {
        Hash hash = new Hash("artist", 4);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode b = new GraphNode("B", true, 1);
        GraphNode c = new GraphNode("C", true, 2);

        hash.insert("A", a);
        hash.insert("B", b);
        hash.remove("A");
        hash.remove("B");

        assertEquals(0, hash.size());

        hash.insert("C", c);
        assertEquals(1, hash.size());

        hash.insert("A", a);
        assertEquals(2, hash.size());
    }
    
    /**
     * Test addEdge with first node null, second node null, and both null.
     */
    public void testAddEdgeNullCases() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;

        // Only first null
        graph.addEdge(null, a);
        // Only second null
        graph.addEdge(a, null);
        // Both null
        graph.addEdge(null, null);

        // None of the above should have added edges
        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(1, stats.largestSize);
    }

    /**
     * Test hasEdge with first null, second null, and both null.
     */
    public void testHasEdgeNullCases() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;

        assertFalse(graph.hasEdge(null, a));
        assertFalse(graph.hasEdge(a, null));
        assertFalse(graph.hasEdge(null, null));
    }

    /**
     * Test addEdge with same node twice (firstIndex == secondIndex).
     */
    public void testAddEdgeSelfLoop() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;

        graph.addEdge(a, a);
        assertFalse(graph.hasEdge(a, a));

        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(1, stats.largestSize);
        assertEquals(0, stats.diameter);
    }

    /**
     * Test addEdge where one node is inactive (isLive false).
     */
    public void testAddEdgeInactiveNode() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;

        graph.removeNode(b);

        // b is now inactive, edge should not be added
        graph.addEdge(a, b);
        assertFalse(graph.hasEdge(a, b));

        // a is inactive, b is active (but b was removed so re-add c)
        GraphNode c = graph.addNode(true).node;
        graph.removeNode(a);
        graph.addEdge(a, c);
        assertFalse(graph.hasEdge(a, c));
    }

    /**
     * Test hasEdge where one or both nodes are inactive.
     */
    public void testHasEdgeInactiveNodes() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;

        graph.addEdge(a, b);
        assertTrue(graph.hasEdge(a, b));

        graph.removeNode(a);
        // a is now inactive
        assertFalse(graph.hasEdge(a, b));
        assertFalse(graph.hasEdge(b, a));

        // Both inactive
        graph.removeNode(b);
        assertFalse(graph.hasEdge(a, b));
    }

    /**
     * Test that hasDirectedEdge returns false when edge does not exist.
     */
    public void testAddEdgeOnlyAddsOnce() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;

        graph.addEdge(a, b);
        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(b, a));

        // Adding again should not duplicate
        graph.addEdge(a, b);
        graph.addEdge(b, a);
        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(b, a));

        // Stats should still show one component
        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(2, stats.largestSize);
        assertEquals(1, stats.diameter);
    }
    
    /**
     * Test isLive with negative index and index >= capacity
     * Targets index >= 0 and index < capacity boundary checks.
     */
    public void testIsLiveOutOfBoundsIndices() {
        Graph graph = new Graph(4);
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        graph.addEdge(a, b);

        // Create a node with index -1 (out of bounds low)
        GraphNode negIndex = new GraphNode("neg", true, -1);
        assertFalse(graph.hasEdge(a, negIndex));
        assertFalse(graph.hasEdge(negIndex, a));
        graph.addEdge(a, negIndex);
        assertFalse(graph.hasEdge(a, negIndex));

        // Create a node with index == capacity (out of bounds high)
        GraphNode highIndex = new GraphNode("high", true, 4);
        assertFalse(graph.hasEdge(a, highIndex));
        assertFalse(graph.hasEdge(highIndex, a));
        graph.addEdge(a, highIndex);
        assertFalse(graph.hasEdge(a, highIndex));
    }

    /**
     * Test hasDirectedEdge finds correct neighbor
     * Targets current.neighbor == to check.
     */
    public void testHasDirectedEdgeCorrectNeighbor() {
        Graph graph = new Graph(6);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        graph.addEdge(a, b);
        graph.addEdge(a, c);

        // a connects to b and c but NOT d
        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(a, c));
        assertFalse(graph.hasEdge(a, d));  // neighbor check must be exact
        assertFalse(graph.hasEdge(b, c));  // no direct edge
        assertFalse(graph.hasEdge(b, d));
    }

    /**
     * Test removeDirectedEdge removes head of list
     * previous == null branch: adjacency[from] = current.next.
     */
    public void testRemoveDirectedEdgeAtHead() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;

        graph.addEdge(a, b);
        graph.addEdge(a, c);

        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(a, c));

        // Remove b - this removes from a's adjacency list
        // The last-added edge is at head, so this tests head removal
        graph.removeNode(b);

        assertFalse(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(a, c));  // c must still be connected
    }

    /**
     * Test removeDirectedEdge removes middle/tail of list
     * previous != null branch: previous.next = current.next.
     */
    public void testRemoveDirectedEdgeInMiddle() {
        Graph graph = new Graph(6);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        // Add multiple edges so the removed one is not at head
        graph.addEdge(a, b);
        graph.addEdge(a, c);
        graph.addEdge(a, d);

        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(a, c));
        assertTrue(graph.hasEdge(a, d));

        // Remove b - it was added first so it's at the tail
        // previous != null path in removeDirectedEdge
        graph.removeNode(b);

        assertFalse(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(a, c));
        assertTrue(graph.hasEdge(a, d));

        // Stats should reflect removal
        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(3, stats.largestSize);
    }

    /**
     * Test removeDirectedEdge while loop exits when current is null
     * Edge not found - loop must terminate without error.
     */
    public void testRemoveDirectedEdgeNotFound() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;

        graph.addEdge(a, b);

        // Remove c which has no edges - removeDirectedEdge finds nothing
        // while loop must exit cleanly
        graph.removeNode(c);

        // a-b edge should be unaffected
        assertTrue(graph.hasEdge(a, b));
        Graph.Stats stats = graph.stats();
        assertEquals(1, stats.components);
        assertEquals(2, stats.largestSize);
        assertEquals(1, stats.diameter);
    }
    
     /**
     * Test that diameter only comes from the largest component,
     * not from a smaller component with a larger diameter.
     */
    public void testDiameterIgnoresSmallerComponentWithLargerDiameter() {
        Graph graph = new Graph(8);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        GraphNode d = graph.addNode(false).node;

        // Largest component: clique of 4, diameter 1
        graph.addEdge(a, b);
        graph.addEdge(a, c);
        graph.addEdge(a, d);
        graph.addEdge(b, c);
        graph.addEdge(b, d);
        graph.addEdge(c, d);

        GraphNode e = graph.addNode(true).node;
        GraphNode f = graph.addNode(false).node;
        GraphNode g = graph.addNode(true).node;

        // Smaller component: path of 3, diameter 2
        graph.addEdge(e, f);
        graph.addEdge(f, g);

        Graph.Stats stats = graph.stats();

        assertEquals(2, stats.components);
        assertEquals(4, stats.largestSize);
        assertEquals(1, stats.diameter);
    }
    
    /**
     * Test equal largest components where the first has larger diameter.
     */
    public void testEqualLargestKeepsEarlierLargerDiameter() {
        Graph graph = new Graph(6);

        // Component 1: path of 3, diameter 2
        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;
        graph.addEdge(a, b);
        graph.addEdge(b, c);

        // Component 2: triangle of 3, diameter 1
        GraphNode d = graph.addNode(true).node;
        GraphNode e = graph.addNode(false).node;
        GraphNode f = graph.addNode(true).node;
        graph.addEdge(d, e);
        graph.addEdge(e, f);
        graph.addEdge(d, f);

        Graph.Stats stats = graph.stats();

        assertEquals(2, stats.components);
        assertEquals(3, stats.largestSize);
        assertEquals(2, stats.diameter);
    }
    
    /**
     * Tests that adding the same edge twice does not leave a stale edge
     * after one endpoint is removed and its slot is reused.
     */
    public void testDuplicateEdgeDoesNotLeaveGhostEdgeAfterReuse() {
        Graph graph = new Graph(2);

        GraphNode first = graph.addNode(true).node;
        GraphNode second = graph.addNode(false).node;

        graph.addEdge(first, second);
        graph.addEdge(first, second);

        assertTrue(graph.hasEdge(first, second));
        assertTrue(graph.hasEdge(second, first));

        graph.removeNode(second);

        GraphNode replacement = graph.addNode(false).node;

        assertEquals(second.getIndex(), replacement.getIndex());
        assertFalse(graph.hasEdge(first, replacement));
        assertFalse(graph.hasEdge(replacement, first));
    }


    /**
     * Tests that addEdge does nothing when the first endpoint has already
     * been removed.
     */
    public void testAddEdgeIgnoresRemovedFirstEndpoint() {
        Graph graph = new Graph(2);

        GraphNode first = graph.addNode(true).node;
        GraphNode second = graph.addNode(false).node;

        graph.removeNode(first);
        graph.addEdge(first, second);

        GraphNode replacement = graph.addNode(true).node;

        assertEquals(first.getIndex(), replacement.getIndex());
        assertFalse(graph.hasEdge(replacement, second));
        assertFalse(graph.hasEdge(second, replacement));
    }

    /**
     * Test removing a node clears all incoming stale edges before slot reuse.
     */
    public void testRemoveNodeClearsMultipleGhostEdgesBeforeReuse() {
        Graph graph = new Graph(4);

        GraphNode a = graph.addNode(true).node;
        GraphNode b = graph.addNode(false).node;
        GraphNode c = graph.addNode(true).node;

        graph.addEdge(a, b);
        graph.addEdge(c, b);

        assertTrue(graph.hasEdge(a, b));
        assertTrue(graph.hasEdge(c, b));

        graph.removeNode(b);

        GraphNode replacement = graph.addNode(false).node;
        assertEquals(b.getIndex(), replacement.getIndex());

        assertFalse(graph.hasEdge(a, replacement));
        assertFalse(graph.hasEdge(replacement, a));
        assertFalse(graph.hasEdge(c, replacement));
        assertFalse(graph.hasEdge(replacement, c));
    }
   
    
}