java-topology/tools/tickets/defects/create-0001.md

id	repo	file	line	status	severity	complexity	pattern	source	created
create-0001	Creators-of-Create/Create	src/main/java/com/simibubi/create/content/trains/graph/TrackGraph.java	findDisconnectedGraphs method	unpatched	MEDIUM	O(V²) BFS — ArrayList.remove(0) is O(n) per iteration due to array shift	ArrayList used as BFS queue; remove(0) shifts all elements left each iteration	open source (GitHub), mc1.20.1/dev branch	2026-03-24

Defect

File: com/simibubi/create/content/trains/graph/TrackGraph.java Method: findDisconnectedGraphs() Pattern: ArrayList.remove(0) in BFS frontier loop Trigger: Every time track is removed from a railroad network

Description

findDisconnectedGraphs() detects whether removing a track segment splits the railroad network into disconnected components. It implements BFS using an ArrayList as the frontier queue:

List<TrackNodeLocation> frontier = new ArrayList<>();
// ...
while (!frontier.isEmpty()) {
    TrackNodeLocation current = frontier.remove(0);  // O(n) — shifts all elements
    // ...
    frontier.add(connected.getLocation());
}

ArrayList.remove(0) is O(n) because Java arrays are contiguous — removing the first element requires shifting every remaining element one position left. For a BFS over a railroad graph with V nodes, each of the V iterations does an O(V) remove, yielding O(V²) total instead of O(V+E).

Secondary inefficiency: the outer loop picks the next unvisited start node with vertices.stream().findFirst() — O(V) per connected component, instead of O(1) with a pre-built iterator or queue seeded from unvisited nodes.

Severity constraint

This fires only when track topology changes (player removes a track segment), not on every game tick. In small railroad networks the quadratic cost is unnoticeable. In large automated factory servers with extensive railroad infrastructure (common in Create megabuilds and ATM/Omnifactory modpacks), track removal can cause measurable lag spikes proportional to V² of the connected graph.

Create's train graph can span hundreds or thousands of nodes in active factory servers. At V=500, the difference is 500 operations (correct) vs 250,000 (actual). At V=2,000: 2,000 vs 4,000,000.

Fix

Replace ArrayList with ArrayDeque — a double-ended queue with O(1) amortized addLast and removeFirst:

// Before
List<TrackNodeLocation> frontier = new ArrayList<>();
TrackNodeLocation current = frontier.remove(0);   // O(n)

// After
Deque<TrackNodeLocation> frontier = new ArrayDeque<>();
TrackNodeLocation current = frontier.removeFirst();  // O(1)

No behavioral change. ArrayDeque implements Deque which is not a List, so the declaration type must change from List<> to Deque<> or Queue<>.

Scan context

AE2 (GridNode.java) — CLEAN: uses ArrayDeque + object-identity visited counter (O(1)) Mekanism (TransmitterNetworkRegistry.java) — CLEAN: uses ObjectOpenHashSet + Deque

Work items

• Confirm against latest Create source (branch may have changed since mc1.20.1/dev)
• Report to Creators-of-Create/Create GitHub issues
• Note: trigger-bounded (track removal only), severity MEDIUM not HIGH