Graph

Graphs

A powerful and flexible graph data structure implementation for working with connected data. This module provides a complete set of tools for creating, manipulating, and traversing graph structures with support for both directed and undirected weighted edges.

Overview

The Graph module allows you to:

• Create and manage nodes with custom data
• Connect nodes with weighted, directed or undirected edges
• Position nodes in 2D space for spatial algorithms
• Perform common graph traversal operations like BFS and DFS
• Find optimal paths using Dijkstra's algorithm or A* search

Basic Usage

Creating a Graph and working with Nodes and Edges

ts
import { Graph } from 'excalibur';
// Create an empty graph of strings
const graph = new Graph<string>();
// Add a few nodes with string data
const nodeA = graph.addNode("A");
const nodeB = graph.addNode("B");
const nodeC = graph.addNode("C");
// Connect nodes with bidirectional edges (default)
graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeE);
// Connect nodes in one direction only 
graph.addEdge(nodeA, nodeC, { directed: true });
// Connect nodes with weighted edges
graph.addEdge(nodeA, nodeB, { weight: 5 });
// Use coordinates of parent nodes to dictate weighting
graph.addEdge(nodeA, nodeB, {useEuclidean: true});
// Check if nodes are connected
const connected = graph.areNodesConnected(nodeA, nodeB); // true
// Get neighbors of a node
const neighbors = graph.getNeighbors(nodeA); // [nodeB]
// Delete a node (and its edges)
graph.deleteNode(nodeC);
// Delete an edge
graph.deleteEdge(edges[0]);

ts
import { Graph } from 'excalibur';
// Create an empty graph of strings
const graph = new Graph<string>();
// Add a few nodes with string data
const nodeA = graph.addNode("A");
const nodeB = graph.addNode("B");
const nodeC = graph.addNode("C");
// Connect nodes with bidirectional edges (default)
graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeE);
// Connect nodes in one direction only 
graph.addEdge(nodeA, nodeC, { directed: true });
// Connect nodes with weighted edges
graph.addEdge(nodeA, nodeB, { weight: 5 });
// Use coordinates of parent nodes to dictate weighting
graph.addEdge(nodeA, nodeB, {useEuclidean: true});
// Check if nodes are connected
const connected = graph.areNodesConnected(nodeA, nodeB); // true
// Get neighbors of a node
const neighbors = graph.getNeighbors(nodeA); // [nodeB]
// Delete a node (and its edges)
graph.deleteNode(nodeC);
// Delete an edge
graph.deleteEdge(edges[0]);

Core Concepts

Node Types

The Graph module supports two node types:

Node: Basic graph node with data

PositionNode: Node with 2D spatial coordinates, uses Excalibur's Native Vector type for position

ts
// Add positioned nodes, when Vector positions are attached to nodes, it returns a PositionNode
const nodeA = graph.addNode("A", new Vector(0, 0));
const nodeB = graph.addNode("B", new Vector(5, 10));
const nodeC = graph.addNode("C", new Vector(10, 5));

ts
// Add positioned nodes, when Vector positions are attached to nodes, it returns a PositionNode
const nodeA = graph.addNode("A", new Vector(0, 0));
const nodeB = graph.addNode("B", new Vector(5, 10));
const nodeC = graph.addNode("C", new Vector(10, 5));

Edge Options

The optional third parameter for creating an Edge has this interface (in principle):

ts
interface EdgeOptions = {
  weighted: number
  useEuclidean: boolean
  direction: boolean
}

ts
interface EdgeOptions = {
  weighted: number
  useEuclidean: boolean
  direction: boolean
}

It is setup as a discriminated union to allow:

• passing a basic weighted value to an edge
• directing the edge to use the positions of its parent nodes to calculate its weighting
• or use no weighting at all

You cannot pass a weighting parameter and direct the Edge to use Euclidean positions of the nodes, you have to pass one or the other.

Edge Properties

Edges connect nodes and can have properties:

weight: Numeric value representing distance or cost (default: 0) directed: Whether the edge is one-way or bidirectional (default: true) partner: reference to a paired edge if a bidirectional edge was created

ts
// Connect the nodes
spatialGraph.addEdge(nodeA, nodeB, { weight: 11.2, directed: false }); // Euclidean distance

ts
// Connect the nodes
spatialGraph.addEdge(nodeA, nodeB, { weight: 11.2, directed: false }); // Euclidean distance

Graph Traversal

Breadth-First Search (BFS)

Explore the graph layer by layer, visiting all direct neighbors before moving deeper:

ts
// Create and populate your graph first
const visitedNodeIds = graph.bfs(startNode);

ts
// Create and populate your graph first
const visitedNodeIds = graph.bfs(startNode);

Depth-First Search (DFS)

Explore the graph by moving as far as possible along each branch before backtracking:

ts
// Create and populate your graph first
const visitedNodeIds = graph.dfs(startNode);

ts
// Create and populate your graph first
const visitedNodeIds = graph.dfs(startNode);

Pathfinding Algorithms

Shortest Path and Dijkstra's Algorithm

Find the shortest path between two nodes in a weighted graph:

ts
// Find shortest path from A to C
const { path, distance } = graph.shortestPathDijkstra(nodeA, nodeC);
// Get full analysis
const dijkstraAnalysis = graph.dijkstra(nodeA);

ts
// Find shortest path from A to C
const { path, distance } = graph.shortestPathDijkstra(nodeA, nodeC);
// Get full analysis
const dijkstraAnalysis = graph.dijkstra(nodeA);

A* Algorithm

Find the shortest path using spatial information for better performance:

ts
const aStarResults = graph.astar(nodeA, nodeB);

ts
const aStarResults = graph.astar(nodeA, nodeB);

Returns an object with a list of nodes representing the path, a number representing the number of node steps required, the overall distance traversed, and if any nodes were skipped due to them not being PositionNodes.

Other Features

Building a Graph from Data Arrays

For convenience, you can create a graph from arrays of node data:

ts
// Create a graph with string data nodes
const cities = ["New York", "London", "Tokyo", "Sydney", "Paris"];
const graph = Graph.createGraphFromNodes(cities);

ts
// Create a graph with string data nodes
const cities = ["New York", "London", "Tokyo", "Sydney", "Paris"];
const graph = Graph.createGraphFromNodes(cities);