Graph class

A directed, unweighted graph with depth-first traversal and cycle detection.

Signature:

export declare class Graph<T>

Remarks

Small on purpose. It exists so model associations can be walked as a graph — BaseModel.toGraph() builds one — and the question worth asking of that graph is whether it has a cycle, because a cycle is a chain of includes that can be asked to include itself.

Directed, despite what this said for a long time: an edge is recorded only on the vertex it starts from, so addEdge(a, b) does not make hasEdge(b, a) true. The cycle detection is the standard directed-graph one, with a recursion stack alongside the visited set, and it would be wrong for an undirected graph.

Vertices are used as Map keys, so identity is what distinguishes them — model classes work, structurally equal objects do not.

Example

const graph = Lead.toGraph();

if (graph.isCycled()) {
    // some association path leads back to where it started
}

Methods

Method	Modifiers	Description
addEdge(fromVertex, toVertex)		Adds edges from one vertex to others.
addVertex(vertex)		Adds vertices with no edges.
delEdge(fromVertex, toVertex)		Removes edges from one vertex to others.
delVertex(vertex)		Removes vertices along with the edges leading out of them.
forEach(callback)		Visits every vertex once, depth first.
hasEdge(vertex, edge)		Whether one vertex points at another.
hasVertex(vertex)		Whether a vertex is in this graph.
isCycled()		Whether any path in this graph leads back to where it started.
path(vertex)		Every vertex reachable from one vertex, in the order a depth-first walk finds them.
vertices()		The vertices in this graph, in insertion order.
walk(vertex, callback, visited)		Walks depth first from one vertex.