bpmn-optimizer/src/v1/graph/Graph.ts

import { array, forward, object, partialCheck, pipe } from "valibot";
import Edge, { EdgeSchema } from "./edge/Edge.js";
import Node, { NodeSchema } from "./node/Node.js";
import GraphError from "../errors/graph/GraphError.js";

export default class Graph<TNode extends Node, TEdge extends Edge<TNode>> {
	private readonly _adjacencyList: Map<TNode, Array<TNode>> = new Map();

	private readonly _nodeMap: Map<string, TNode>;
	private readonly _edgeMap: Map<string, TEdge>;

	public constructor(nodes: TNode[], edges: TEdge[]) {
		this._nodeMap = new Map();
		nodes.forEach((node) => this.addNode(node));

		this._edgeMap = new Map();
		edges.forEach((edge) => this.addEdge(edge));

		for(const edge of edges) {
			const from = edge.getFrom(), to = edge.getTo();

			const adjacencyNodes = this._adjacencyList.get(from);
			if(adjacencyNodes)
				adjacencyNodes.push(to);
			else
				this._adjacencyList.set(from, [to]);
		}
	}

	public isAcyclic() : boolean {
		const queue: TNode[] = [];
		const nodeToInDegree = new Map<TNode, number>();
		const nodesCount = this._nodeMap.size;
		let visitedNodesCount = 0;

		for(const node of this.getNodes())
			nodeToInDegree.set(node, this.getNodeInputs(node).length);

		for(const [nodeId, inDegree] of nodeToInDegree)
			if(inDegree === 0)
				queue.push(nodeId);

		while(queue.length > 0) {
			const node = queue.pop()!;
			visitedNodesCount++;

			for(const output of this.getNodeOutputs(node)) {
				const inDegree = nodeToInDegree.get(output);
				const newInDegree = inDegree !== undefined ? inDegree - 1 : 0;

				nodeToInDegree.set(output, newInDegree);

				if(newInDegree === 0)
					queue.push(output);
			}
		}

		return visitedNodesCount === nodesCount;
	}

	public getNodes() : TNode[] {
		return [...this._nodeMap.values()];
	}

	public getNode(id: string) : Node | null {
		return this._nodeMap.get(id) || null;
	}

	public addNode(node: TNode) : this {
		const id = node.getId();

		if(this._nodeMap.has(id))
			throw new GraphError(`Can't add a new node to graph: node with id ${id} already exists`);

		this._nodeMap.set(id, node);

		node.subscribe(() => this.onNodeChange(node));

		return this;
	}

	public removeNode(nodeId: string) : this {
		if(!this._nodeMap.has(nodeId))
			throw new GraphError(`Can't delete a node from graph: node with id ${nodeId} doesn't exists`);

		for(const [edgeId, edge] of this._edgeMap) {
			const fromId = edge.getFrom().getId(), toId = edge.getTo().getId();

			if(fromId == nodeId || toId == nodeId)
				this._edgeMap.delete(edgeId);
		}

		this._nodeMap.delete(nodeId);

		this.buildAdjacencyList();

		return this;
	}

	public getEdges() : TEdge[] {
		return Array.from(this._edgeMap.values());
	}

	public getEdge(edgeId: string): TEdge | null {
		return this._edgeMap.get(edgeId) || null;
	}

	public addEdge(edge: TEdge) : this {
		const id = edge.getId(), from = edge.getFrom(), to = edge.getTo();

		if(this._edgeMap.has(id))
			throw new GraphError(`Can't add a new edge to graph: edge with id ${id} already exists`);

		if(!this._nodeMap.has(from.getId()) || !this._nodeMap.has(to.getId()))
			throw new GraphError(`Can't add a new edge to graph: edge references to non-existing nodes`);

		this._edgeMap.set(id, edge);

		edge.subscribe(() => this.onEdgeChange(edge));

		this.buildAdjacencyList();

		return this;
	}

	public removeEdge(edgeId: string): this {
		if(!this._edgeMap.has(edgeId))
			return this;

		this._edgeMap.delete(edgeId);

		this.buildAdjacencyList();

		return this;
	}

	public getNodeInputs(node: TNode) : TNode[] {
		const inputs: TNode[] = [];

		for(const [input, outputs] of this._adjacencyList) {
			if(!outputs.includes(node))
				continue;
			inputs.push(input);
		}

		return inputs;
	}

	public getNodeOutputs(node: TNode) : TNode[] {
		return  this._adjacencyList.get(node) || [];
	}

	public isSourceNode(node: TNode) : boolean {
		return this.getNodeInputs(node).length === 0;
	}

	public isSinkNode(node: TNode) : boolean {
		return this.getNodeOutputs(node).length === 0;
	}

	protected onNodeChange(node: TNode) : void {
	}

	protected onEdgeChange(edge: TEdge) : void {
		this.buildAdjacencyList();
	}

	private buildAdjacencyList() : void {
		this._adjacencyList.clear();

		for(const [, edge] of this._edgeMap) {
			const from = edge.getFrom(), to = edge.getTo();

			const adjacencyNodes = this._adjacencyList.get(from);
			if(adjacencyNodes)
				adjacencyNodes.push(to);
			else
				this._adjacencyList.set(from, [to]);
		}
	}
}

export const GraphSchema = pipe(
	object({
		nodes: array(NodeSchema),
		edges: array(EdgeSchema)
	}),
	forward(
		partialCheck(
			[['nodes']],
			(input) => {
				const {nodes} = input;
				for(let i = 0; i < nodes.length; i++) {
					const currentNodeId = nodes[i]!.id;
					const idIndex = nodes.findIndex((n) => n.id === currentNodeId);
					if(idIndex !== i)
						return false;
				}

				return true;
			},
			`Every node in "nodes" array must have an unique identifier!`
		),
		["nodes"]
	),
	forward(
		partialCheck(
			[['edges']],
			(input) => {
				const { edges } = input;
				for(let i = 0; i < edges.length; i++) {
					const currentNodeId = edges[i]!.id;
					const idIndex = edges.findIndex((n) => n.id === currentNodeId);
					if(idIndex !== i)
						return false;
				}

				return true;
			},
			`Every edge in "edges" array must have an unique identifier!`
		),
		['edges']
	),
	forward(
		partialCheck(
			[['nodes'], ['edges']],
			(input) => {
				const { nodes, edges } = input;
				for(const edge of edges) {
					const { from, to } = edge;
					if(!(nodes.some((node) => node.id == from) && nodes.some((node) => node.id == to)))
						return false;
				}

				return true;
			},
			`Some of edges contains link to a node that doesn't exist in "nodes" array`
		),
		['edges']
	)
)