Spot a circular dependency

Two modules that import each other, two components that render each other, two effects that each trigger the other: a cycle in a directed graph is the shape behind some of the most confusing bugs in a frontend codebase.

Implement a Graph class holding a directed graph as an adjacency list. It is constructed with no arguments and starts empty. addEdge(from, to) records a directed edge from from to to, creating either node if it is not known yet; adding the same edge twice changes nothing, and its return value is not used. nodes() returns an array of every known node id in the order each was first seen, and [] when the graph is empty. neighbors(id) returns an array of the ids that id points at, in the order those edges were added, and [] for a node with no outgoing edges or one that is not in the graph. hasCycle() returns true when following edges can lead from some node back to itself, and false otherwise. hasPath(from, to) returns true when following one or more edges from from reaches to, and false otherwise, including when either id is unknown.

Note what hasPath means for a node and itself: hasPath('a', 'a') is true only when there is a real loop back to a, since it requires at least one edge to be followed.

What it has to do

• hasCycle() is false for an acyclic graph and true when any loop exists, including a self-loop.
• hasPath follows one or more edges and returns false for unknown ids.
• neighbors lists targets in the order their edges were added, with no duplicates.
• nodes() lists every node created by addEdge, in first-seen order.
• An empty graph has no nodes and no cycle.

Your workspace