Source: GenericGraph.js

import { Map } from "immutable";
import { EdgeDoesNotExistError, VertexDoesNotExistError } from "@/GraphErrors";
/**
 * A generic graph that does not allow parallel edges, self loops,
 * or multiple edges.
 *
 * Behind the scenes, this graph is represented as an adjacency list
 * using immutable.js Map.
 *
 * To use objects as vertices, the object should have a valid implementation
 * of the equals() and hashCode() methods.
 * Objects should also include a valueOf() method that returns a primitive
 * value.
 *
 * @example
 * class Foo {
 *   private readonly a: number;
 *   private readonly b: number;
 *
 *   constructor(a: number, b: number) {
 *     this.a = a;
 *     this.b = b;
 *   }
 *
 *   equals(other: any) {
 *     if (!(other instanceof Foo)) return false;
 *
 *     return this.a == other.a;
 *   }
 *
 *   hashCode() {
 *     return this.a;
 *   }
 *
 *   valueOf() {
 *     return this.a + this.b;
 *   }
 * }
 * const g = new GenericGraph<Foo>();
 *
 * @template V the type of the vertices in the graph.
 */
export class GenericGraph {
    /**
     * Constructs a new empty graph.
     * @protected
     */
    constructor() {
        // eslint-disable-next-line new-cap
        this._adj = Map().asMutable();
    }
    /**
     * Returns an immutable copy of the adjacency list.
     */
    get adj() {
        return this._adj;
    }
    /**
     * Returns an array of all the vertices in the graph.
     * @return {V[]} an array of all the vertices in the graph.
     */
    vertices() {
        return this._adj.keySeq().toArray();
    }
    /**
     * Returns a string representation of the graph.
     * Just calls the toString() method of the underlying adjacency list.
     * @return {string} a string representation of the graph.
     */
    toString() {
        return this._adj.toString();
    }
    /**
     * Removes a vertex from the graph.
     * @param {V} v the vertex to remove.
     */
    removeVertex(v) {
        this.validateVertex(v);
        for (const w of this.neighbors(v)) {
            this.removeEdge(v, w);
        }
        this._adj.delete(v);
    }
    /**
     * Adds all the edges in the edge list to the graph
     * @param {Array.<Array.<V>>} edgeList the list of edges to add.
     */
    fromEdgeList(edgeList) {
        for (let i = 0; i < edgeList.length; i++) {
            const [from, to] = edgeList[i];
            this.addEdge(from, to);
        }
    }
    /**
     * Adds all the edges in the path to the graph.
     * @param {V[]} path the path to add.
     */
    addPath(path) {
        for (let i = 0; i < path.length - 1; i++) {
            const from = path[i];
            const to = path[i + 1];
            this.addEdge(from, to);
        }
    }
    /**
     * Determines if the graph contains the vertex v.
     * @param {V} v the vertex to check.\
     * @return {boolean} true if the graph contains the vertex v, false otherwise.
     */
    hasVertex(v) {
        return this._adj.has(v);
    }
    /**
     * Returns the number of vertices in the graph.
     * @return {number} the number of vertices in the graph.
     */
    numberOfNodes() {
        return this._adj.size;
    }
    /**
     * Validates that the vertex v exists in the graph.
     * @param {V} v
     * @throws VertexDoesNotExistError if the vertex does not exist.
     */
    validateVertex(v) {
        if (!this.hasVertex(v)) {
            throw new VertexDoesNotExistError(v);
        }
    }
    /**
     * Validates that the edge (v, w) exists in the graph.
     * @param {V} v
     * @param {V} w
     * @throws EdgeDoesNotExistError if the edge does not exist.
     */
    validateEdge(v, w) {
        if (!this.hasEdge(v, w)) {
            throw new EdgeDoesNotExistError(v, w);
        }
    }
}