mky-vent-base/src/views/vent/monitorManager/windrectMonitor/topology/hooks/useTopologyOrdering.ts

import type { TopologyData, TopoNodeData } from '../windTopology.data';

/**
 * 通风网络拓扑层内排序：median / barycenter 多轮扫描法（Sugiyama 框架的 crossing reduction 阶段）。
 *
 * 背景：层级已由 level 字段固定为语义层（0=总进风 … 6=总回风），层内排序只影响相邻层
 * 巷道连线的交叉数。二部交叉最小化（bipartite crossing minimization）为 NP-hard，
 * 本模块采用工业图布局库（dagre/ELK）同款启发式：
 *   1) 每层节点按"其相邻层邻居位置的 median（中位数）/ barycenter（均值）"计算关键值；
 *   2) 左右多轮往返扫描（down/up sweep），保留历史交叉数最优解。
 *
 * 确定性保证：固定轮次（默认 20）+ 三元比较稳定排序（关键值、输入 index），
 * 同一输入永远输出同一顺序，避免 resize / 刷新导致的布局抖动。
 *
 * 不参与排序、保持输入序（不影响交叉数的节点/边）：
 *   - 未分级层（level 无效）；
 *   - 跨层巷道边（两端 level 差 > 1）及其端点；
 *   - 根边（地面 ↔ lv0 / lv6）与地面节点（单节点层）。
 * 无任何相邻层边的节点关键值为 +Infinity：排在层尾，且彼此保持相对输入序。
 */

export interface OrderingOptions {
  /** 邻居位置聚合方法：median=中位数（默认，抗离群，交叉 ≤ 3×最优 有理论保证）、barycenter=均值 */
  method?: 'median' | 'barycenter';
  /** 往返扫描轮数（固定值，保证确定性） */
  sweepRounds?: number;
}

/** 参与排序的层级 key（0=总进风 1..5 现有层级 6=总回风），与 levelTextMap / computeLayout 分组一致 */
const ORDER_KEYS = ['0', '1', '2', '3', '4', '5', '6'];

/** 层级 key：0..6 有效 → 数字字符串；否则 'ungraded' */
function levelKeyOf(p: TopoNodeData): string {
  const lv = Number(p.level);
  return Number.isFinite(lv) && lv >= 0 && lv <= 6 ? String(lv) : 'ungraded';
}

/**
 * 构建相邻层（level 差恰为 1）巷道边表：
 * key = "低层-高层"（如 '2-3'），value = 方向规范化的边数组 [低层节点 id, 高层节点 id]。
 * 渲染方向（parent → child）不影响交叉判定，统一规范化为低层 → 高层。
 */
function buildPairEdges(data: TopologyData): Map<string, Array<[string, string]>> {
  const levelById = new Map<string, number>();
  for (const n of data.nodes) {
    if (n.category !== 1) continue;
    const lv = Number(n.level);
    if (Number.isFinite(lv) && lv >= 0 && lv <= 6) levelById.set(n.id, lv);
  }

  const edgesByPair = new Map<string, Array<[string, string]>>();
  for (const l of data.links) {
    if (l.kind !== 'roadway') continue;
    const sl = levelById.get(l.source);
    const tl = levelById.get(l.target);
    if (sl === undefined || tl === undefined) continue;
    if (Math.abs(sl - tl) !== 1) continue;
    const lo = Math.min(sl, tl);
    const hi = Math.max(sl, tl);
    const key = `${lo}-${hi}`;
    if (!edgesByPair.has(key)) edgesByPair.set(key, []);
    edgesByPair.get(key)!.push(sl < tl ? [l.source, l.target] : [l.target, l.source]);
  }
  return edgesByPair;
}

/** 层序数组 → 节点秩映射（nodeId → 层内 index）；undefined（空层）返回空 map */
function rankOf(order: string[] | undefined): Map<string, number> {
  const rank = new Map<string, number>();
  if (order) order.forEach((id, i) => rank.set(id, i));
  return rank;
}

/**
 * 相邻两层交叉数：edges 中每条边一端在 A 层、一端在 B 层；
 * 两对边 (a1,b1)、(a2,b2) 交叉 ⇔ a1/a2 在 A 层秩的相对顺序与 b1/b2 在 B 层秩相反。
 * O(E²) 直接统计（本系统每矿测风点 ≤ 数百，足够）。
 */
export function countCrossings(rankA: Map<string, number>, rankB: Map<string, number>, edges: Array<[string, string]>): number {
  let total = 0;
  for (let i = 0; i < edges.length; i++) {
    const [a1, b1] = edges[i];
    const ra1 = rankA.get(a1);
    const rb1 = rankB.get(b1);
    if (ra1 === undefined || rb1 === undefined) continue;
    for (let j = i + 1; j < edges.length; j++) {
      const [a2, b2] = edges[j];
      const ra2 = rankA.get(a2);
      const rb2 = rankB.get(b2);
      if (ra2 === undefined || rb2 === undefined) continue;
      if ((ra1 < ra2 && rb1 > rb2) || (ra1 > ra2 && rb1 < rb2)) total++;
    }
  }
  return total;
}

/** 复用已有边表的全图总交叉数（4 个相邻层对 lv1-lv2 … lv4-lv5 交叉数之和） */
function countTotalCrossingsWith(edgesByPair: Map<string, Array<[string, string]>>, order: Map<string, string[]>): number {
  let total = 0;
  for (let i = 0; i < ORDER_KEYS.length - 1; i++) {
    const lo = ORDER_KEYS[i];
    const hi = ORDER_KEYS[i + 1];
    const edges = edgesByPair.get(`${lo}-${hi}`);
    if (!edges || edges.length === 0) continue;
    total += countCrossings(rankOf(order.get(lo)), rankOf(order.get(hi)), edges);
  }
  return total;
}

/** 全图总交叉数：order 为 orderNodesByLevel 返回的层序（key '0'..'6'） */
export function countTotalCrossings(data: TopologyData, order: Map<string, string[]>): number {
  return countTotalCrossingsWith(buildPairEdges(data), order);
}

/** 深拷贝层序（仅复制参与排序的层） */
function snapshotOrder(order: Map<string, string[]>): Map<string, string[]> {
  const copy = new Map<string, string[]>();
  for (const [k, arr] of order) copy.set(k, [...arr]);
  return copy;
}

/**
 * 单层重排：目标层节点按"其在 neighbor 层的邻居位置"的 median/barycenter 升序稳定排序。
 * 无邻居的节点关键值 +Infinity → 排层尾且彼此保持相对输入序。
 */
function sweepLayer(
  current: Map<string, string[]>,
  edges: Array<[string, string]> | undefined,
  targetKey: string,
  neighborKey: string,
  isTargetHigh: boolean,
  method: 'median' | 'barycenter'
): void {
  const target = current.get(targetKey);
  if (!target || target.length <= 1 || !edges || edges.length === 0) return;
  const neighborRank = rankOf(current.get(neighborKey));

  // 目标层节点 → 其邻居（neighbor 层）位置集合（边已规范化为 [低层, 高层]）
  const neighborPos = new Map<string, number[]>();
  for (const [loId, hiId] of edges) {
    const tId = isTargetHigh ? hiId : loId;
    const nId = isTargetHigh ? loId : hiId;
    const r = neighborRank.get(nId);
    if (r === undefined) continue;
    if (!neighborPos.has(tId)) neighborPos.set(tId, []);
    neighborPos.get(tId)!.push(r);
  }

  const keyOf = (id: string): number => {
    const arr = neighborPos.get(id);
    if (!arr || arr.length === 0) return Infinity;
    if (method === 'barycenter') {
      let sum = 0;
      for (const v of arr) sum += v;
      return sum / arr.length;
    }
    arr.sort((x, y) => x - y);
    const m = Math.floor(arr.length / 2);
    return arr.length % 2 === 1 ? arr[m] : (arr[m - 1] + arr[m]) / 2;
  };

  const indexed = target.map((id, idx) => ({ id, idx }));
  indexed.sort((p, q) => {
    const kp = keyOf(p.id);
    const kq = keyOf(q.id);
    if (kp !== kq) return kp - kq;
    return p.idx - q.idx;
  });
  current.set(
    targetKey,
    indexed.map((p) => p.id)
  );
}

/**
 * 层内排序主入口：返回各层有序节点 id（key：'0'..'6' 与 'ungraded'）。
 * - 参与排序层（lv0..lv6）：以输入序（data.nodes 顺序，即后端返回序）为初始序，
 *   sweep 后返回历史交叉数最优解；
 * - 未分级层：始终返回输入序（不参与扫描）；
 * - 空层：返回空数组。
 */
export function orderNodesByLevel(data: TopologyData, opts?: OrderingOptions): Map<string, string[]> {
  const method = opts?.method ?? 'median';
  const sweepRounds = opts?.sweepRounds ?? 20;

  // 1) 按输入序分层
  const layers = new Map<string, string[]>();
  for (const n of data.nodes) {
    if (n.category !== 1) continue;
    const key = levelKeyOf(n);
    if (!layers.has(key)) layers.set(key, []);
    layers.get(key)!.push(n.id);
  }

  const edgesByPair = buildPairEdges(data);

  // 2) 初始层序（仅参与层）与历史最优记录
  const current = new Map<string, string[]>();
  for (const key of ORDER_KEYS) {
    current.set(key, layers.get(key) ? [...layers.get(key)!] : []);
  }
  let best = snapshotOrder(current);
  let bestCross = countTotalCrossingsWith(edgesByPair, current);
  const evalTotal = () => {
    const c = countTotalCrossingsWith(edgesByPair, current);
    if (c < bestCross) {
      bestCross = c;
      best = snapshotOrder(current);
    }
  };

  // 3) 多轮往返扫描：down（上→下，用低层位置重排高层）+ up（下→上，用高层位置重排低层）
  for (let round = 0; round < sweepRounds; round++) {
    for (let i = 0; i < ORDER_KEYS.length - 1; i++) {
      const key = `${ORDER_KEYS[i]}-${ORDER_KEYS[i + 1]}`;
      sweepLayer(current, edgesByPair.get(key), ORDER_KEYS[i + 1], ORDER_KEYS[i], true, method);
      evalTotal();
    }
    for (let i = ORDER_KEYS.length - 2; i >= 0; i--) {
      const key = `${ORDER_KEYS[i]}-${ORDER_KEYS[i + 1]}`;
      sweepLayer(current, edgesByPair.get(key), ORDER_KEYS[i], ORDER_KEYS[i + 1], false, method);
      evalTotal();
    }
  }

  // 4) 合并输出：参与层用历史最优，未分级层用输入序
  const result = new Map<string, string[]>();
  result.set('ungraded', layers.get('ungraded') ? [...layers.get('ungraded')!] : []);
  for (const key of ORDER_KEYS) {
    result.set(key, best.get(key) ? [...best.get(key)!] : []);
  }
  return result;
}