bpmn-optimizer/src/v1/optimizer/steps/LayerAssignmentStep.ts

import LayerAssignmentStepError from "../../errors/optimizer/LayerAssignmentStepError.js";
import Edge from "../../graph/edge/Edge.js";
import Graph from "../../graph/Graph.js";
import Layering from "../../graph/layering/Layering.js";
import Node from "../../graph/node/Node.js";
import AlgorithmStep from "../AlgorithmStep.js";
import {EdgeSubdivisions, FeedbackSet, SiguiyamaContext} from "../siguiyama/SiguiyamaContext.js";
import DummyNode from "../../graph/node/DummyNode.js";
import DummyEdge from "../../graph/edge/DummyEdge.js";

/**
 * Шаг алгоритма Sugiyama для присвоения слоёв вершинам графа.
 * Использует longest path layering для минимизации числа слоёв и обеспечения направления рёбер вниз.
 */
export default class LayerAssignmentStep extends AlgorithmStep<SiguiyamaContext> {
	/**
	 * Создаёт экземпляр шага LayerAssignmentStep.
	 */
	public constructor() {
		super(LayerAssignmentStep.name);
	}

	/**
	 * Выполняет шаг присвоения слоёв.
	 * @param context Контекст алгоритма Sugiyama, содержащий граф, feedback set и edge subdivisions.
	 * @throws {LayerAssignmentStepError} Если граф не найден, feedback set не определён или граф ацикличен.
	 */
	public run(context: SiguiyamaContext): void {
		const {graph, feedbackSet} = context;

		if(!graph)
			throw new LayerAssignmentStepError("Graph was not found!");
		if(!feedbackSet)
			throw new LayerAssignmentStepError("Feedback set is undefined!");

		if(!graph.isAcyclic())
			throw new LayerAssignmentStepError("Graph is acyclic, can not assign layers to an acyclic graph!");

		const layering = this.longestPathAlgorithm(graph);
		const edgeSubdivisions: EdgeSubdivisions<Node, Edge<Node>> = new Map();

		this.divideLongEdges(graph, layering, feedbackSet, edgeSubdivisions);

		context.layering = layering;
		context.edgeSubdivisions = edgeSubdivisions;
	}

	/**
	 * Реализация алгоритма longest path layering для присвоения слоёв вершинам DAG.
	 * Каждая вершина получает слой, равный длине самого длинного пути от неё.
	 * @param dag Направленный ациклический граф.
	 * @returns Объект Layering с присвоенными слоями.
	 * @private
	 */
	private longestPathAlgorithm(dag: Graph<Node, Edge<Node>>): NonNullable<SiguiyamaContext["layering"]> {
		const layering = new Layering<Node, Edge<Node>>();
		const cache = new Map<string, number>();

		const getLongestPath = (node: Node): number => {
			if(cache.has(node.getId()))
				return cache.get(node.getId())!;

			const successors = dag.getNodeOutputs(node);
			if(successors.length === 0) {
				cache.set(node.getId(), 0);
				return 0;
			}

			const maxSucc = Math.max(...successors.map(s => getLongestPath(s)));
			const dist = 1 + maxSucc;
			cache.set(node.getId(), dist);
			return dist;
		};

		for(const node of dag.getNodes()) {
			const layer = getLongestPath(node);
			layering.addToLayer(layer, node);
		}

		return layering;
	}

	/**
     * Разбивает длинные рёбра (span >= 2) добавлением dummy-вершин между слоями.
     *
     * Для каждого ребра, у которого {@link Layering.getEdgeSpan} возвращает значение больше 1:
     * - создаётся цепочка из `span - 1` вершин {@link DummyNode};
     * - каждая dummy-вершина добавляется в промежуточный слой;
     * - исходная вершина/последняя dummy соединяется новым сегментом {@link Edge}.
     *
     * @param graph Граф, в который добавляются dummy-вершины и сегменты рёбер.
     * @param layering Текущее разбиение графа на слои, используемое для вычисления span и вставки dummy-вершин.
     * @param feedbackSet Набор рёбер обратной связи
     * @param edgeSubdivisions Информация о разделении рёбер в графе
     */
	private divideLongEdges(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>, feedbackSet: FeedbackSet, edgeSubdivisions: EdgeSubdivisions<Node, Edge<Node>>) : void {
		const edges = graph.getEdges();

		for(const edge of edges) {
			const span = layering.getEdgeSpan(edge);
			if(span < 2)
				continue;

			const from = edge.getFrom(), to = edge.getTo();
			const fromLayer = layering.getNodeLayerIndex(from);
			let currentEdge: Edge<Node> = edge;

			graph.removeEdge(edge.getId());

			for(let i = 1; i < span; i++) {
				const dummyNode = new DummyNode(0, 0);
				layering.addToLayer(fromLayer - i, dummyNode);
				graph.addNode(dummyNode);

				const left = new DummyEdge(currentEdge.getFrom(), dummyNode);
				const right = new DummyEdge(dummyNode, currentEdge.getTo());

				edgeSubdivisions.set(currentEdge, { left, right });

				graph.addEdge(left).addEdge(right);

				const feedbackIndex = feedbackSet.indexOf(currentEdge);
				if(feedbackIndex >= 0) {
					feedbackSet.splice(feedbackIndex, 1);
					feedbackSet.push(left, right);
				}

				if(currentEdge !== edge)
					graph.removeEdge(currentEdge.getId());

				currentEdge = right;
			}
		}
	}
}