bpmn-optimizer/src/optimizer/steps/NodeOrderingStep.ts

import NodeOrderingStepError from "../../errors/optimizer/NodeOrderingStepError.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 {SiguiyamaContext} from "../siguiyama/SiguiyamaContext.js";

enum Direction {
	Up,
	Down
}

/**
 * Шаг минимизации пересечений рёбер между слоями
 * Использует barycenter-эвристику с попеременными проходами сверху-вниз и снизу-вверх
 */
export default class NodeOrderingStep extends AlgorithmStep<SiguiyamaContext> {
	/**
	 * Количество итераций по умолчанию для barycenter-оптимизации
	 */
	private static readonly DefaultIterationsCount = 24;

	/**
	 * Максимальное количество итераций переупорядочивания слоёв
	 */
	private readonly _iterationsCount: number;

	/**
	 * @param iterationsCount Максимальное число итераций barycenter-эвристики
	 */
	public constructor(iterationsCount: number = NodeOrderingStep.DefaultIterationsCount) {
		super(NodeOrderingStep.name);

		if(iterationsCount <= 0)
			throw new NodeOrderingStepError("Iterations count must be greater than 0");

		this._iterationsCount = iterationsCount;
	}

	/**
	 * Выполняет шаг упорядочивания вершин внутри слоёв
	 * @param context Контекст алгоритма Sugiyama
	 * @throws {NodeOrderingStepError} Если граф или слоистая укладка отсутствуют
	 */
	public run(context: SiguiyamaContext): void {
		const { graph, layering } = context;

		if(!graph)
			throw new NodeOrderingStepError("Source graph was not found!");
		if(!layering)
			throw new NodeOrderingStepError("Layering of graph was not found!");

		this.barycenter(graph, layering);
	}

	/**
	 * Основной цикл barycenter-оптимизации.
	 * На каждой итерации выполняются проходы вниз и вверх; если число пересечений ухудшилось,
	 * алгоритм останавливается и возвращает лучшее найденное состояние слоёв.
	 * @param graph Граф
	 * @param layering Слои графа
	 */
	private barycenter(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>) : void {
		let bestCrossingsCount = this.countTotalCrossings(graph, layering);
		let bestLayers = this.captureLayerOrder(layering);

		for(let i = 0; i < this._iterationsCount; i++) {
			this.sweepDown(graph, layering);
			this.sweepUp(graph, layering);

			const currentCrossingsCount = this.countTotalCrossings(graph, layering);

			if(currentCrossingsCount > bestCrossingsCount) {
				this.restoreLayerOrder(layering, bestLayers);
				break;
			}

			bestCrossingsCount = currentCrossingsCount;
			bestLayers = this.captureLayerOrder(layering);
		}
	}

	/**
	 * Проход сверху-вниз: переупорядочивает каждый слой по barycenter-значениям
	 * относительно предыдущего слоя
	 * @param graph Граф
	 * @param layering Слои графа
	 */
	private sweepDown(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>) : void {
		const layers = layering.getLayers();

		for(let i = 1; i < layers.length; i++) {
			const currLayer = layers[i]!;
			currLayer.setNodes(this.applyBarycenter(graph, layering, currLayer.getNodes(), Direction.Down));
		}
	}

	/**
	 * Проход снизу-вверх: переупорядочивает каждый слой по barycenter-значениям
	 * относительно следующего слоя
	 * @param graph Граф
	 * @param layering Слои графа
	 */
	private sweepUp(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>) : void {
		const layers = layering.getLayers();

		for(let i = layers.length - 2; i >= 0; i--) {
			const currLayer = layers[i]!;
			currLayer.setNodes(this.applyBarycenter(graph, layering, currLayer.getNodes(), Direction.Up));
		}
	}

	/**
	 * Сортирует вершины слоя по barycenter-значению
	 * Для вершины вычисляется средняя позиция соседей в фиксированном соседнем слое:
	 * - при проходе вниз используются входящие соседи
	 * - при проходе вверх используются исходящие соседи.
	 * Если соседей нет, вершина сохраняет текущий порядок (по своей позиции в слое)
	 * @param graph Граф
	 * @param layering Слои графа
	 * @param nodes Вершины текущего слоя
	 * @param direction Направление прохода
	 * @returns Новый порядок вершин в текущем слое
	 */
	private applyBarycenter(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>, nodes: Node[], direction: Direction) : Node[] {
		const layerPositionMap = this.buildLayerPositionMap(layering);
		const stableIndex = new Map<string, number>();
		for(let i = 0; i < nodes.length; i++)
			stableIndex.set(nodes[i]!.getId(), i);

		const barycenterValues = nodes.map((node) => {
			const neighbors = direction === Direction.Down ? graph.getNodeInputs(node) : graph.getNodeOutputs(node);
			if(neighbors.length === 0)
				return { node, value: stableIndex.get(node.getId())! };

			const positionSum = neighbors.reduce((sum, neighbor) => {
				const position = layerPositionMap.get(neighbor.getId());
				return sum + (position !== undefined ? position : 0);
			}, 0);

			return { node, value: positionSum / neighbors.length };
		});

		return barycenterValues
			.sort((a, b) => {
				if(a.value !== b.value)
					return a.value - b.value;

				return stableIndex.get(a.node.getId())! - stableIndex.get(b.node.getId())!;
			})
			.map((entry) => entry.node);
	}

	/**
	 * Подсчитывает суммарное число пересечений между всеми соседними парами слоёв
	 * @param graph Граф
	 * @param layering Слои графа
	 * @returns Общее число пересечений
	 */
	private countTotalCrossings(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>) : number {
		const layers = layering.getLayers();

		let totalCrossings = 0;

		for(let i = 0; i < layers.length - 1; i++)
			totalCrossings += this.countCrossingsBetweenLayers(graph, layering, i, i + 1);

		return totalCrossings;
	}

	/**
	 * Подсчитывает число пересечений рёбер между двумя соседними слоями.
	 * @param graph Граф
	 * @param layering Слои графа
	 * @param upperLayerIndex Индекс верхнего слоя
	 * @param lowerLayerIndex Индекс нижнего слоя
	 * @returns Число пересечений между рёбрами, соединяющими эти слои
	 */
	private countCrossingsBetweenLayers(graph: Graph<Node, Edge<Node>>, layering: Layering<Node, Edge<Node>>, upperLayerIndex: number, lowerLayerIndex: number) : number {
		const layers = layering.getLayers();
		const upperLayer = layers[upperLayerIndex];
		const lowerLayer = layers[lowerLayerIndex];
		if(!upperLayer || !lowerLayer)
			return 0;

		const upperPosition = new Map<string, number>(
			upperLayer.getNodes().map((node, index) => [node.getId(), index])
		);
		const lowerPosition = new Map<string, number>(
			lowerLayer.getNodes().map((node, index) => [node.getId(), index])
		);

		const edges = graph.getEdges().filter((edge) => {
			const fromId = edge.getFrom().getId();
			const toId = edge.getTo().getId();

			return upperPosition.has(fromId) && lowerPosition.has(toId);
		});

		let crossings = 0;

		for(let i = 0; i < edges.length; i++) {
			for(let j = i + 1; j < edges.length; j++) {
				const posU = upperPosition.get(edges[i]!.getFrom().getId())!;
				const posV = lowerPosition.get(edges[i]!.getTo().getId())!;
				const posS = upperPosition.get(edges[j]!.getFrom().getId())!;
				const posT = lowerPosition.get(edges[j]!.getTo().getId())!;

				if((posU < posS && posV > posT) || (posU > posS && posV < posT))
					crossings++;
			}
		}

		return crossings;
	}

	/**
	 * Формирует отображение "id вершины -> позиция в своём слое"
	 * @param layering Слои графа
	 * @returns Карта позиций для всех вершин, присутствующих в слоях
	 */
	private buildLayerPositionMap(layering: Layering<Node, Edge<Node>>) : Map<string, number> {
		const positions = new Map<string, number>();
		const layers = layering.getLayers();

		for(const layer of layers) {
			for(const [position, node] of layer.getNodes().entries())
				positions.set(node.getId(), position);
		}

		return positions;
	}

	/**
	 * Сохраняет текущий порядок вершин по слоям.
	 * @param layering Слои графа.
	 * @returns Снимок порядка: массив массивов вершин по слоям.
	 */
	private captureLayerOrder(layering: Layering<Node, Edge<Node>>) : Node[][] {
		const layers = layering.getLayers();
		return layers.map((layer) => layer.getNodes());
	}

	/**
	 * Восстанавливает порядок вершин в слоях из ранее сохранённого снимка
	 * @param layering Слои графа
	 * @param snapshot Снимок, полученный методом {@link captureLayerOrder}
	 */
	private restoreLayerOrder(layering: Layering<Node, Edge<Node>>, snapshot: Node[][]) : void {
		const layers = layering.getLayers();

		for(let i = 0; i < layers.length; i++) {
			const layer = layers[i];
			const nodes = snapshot[i];
			if(!layer || !nodes)
				continue;

			layer.setNodes(nodes);
		}
	}
}