DndGamePlayer/app/shared/graph/sceneGraphLineage.ts

import type { GraphNodeId, SceneGraphEdge, SceneGraphNode } from '../types';

/** Корень сюжета: основная линия, старт побочной (id узла) или изолированный узел. */
export type StoryRoot = 'main' | GraphNodeId | null;

/** true — корень относится к побочной линии (id стартового узла), не к основной. */
export function isSideStoryRoot(root: StoryRoot): root is GraphNodeId {
  return root !== null && root !== 'main';
}

function buildAdjacency(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
): Map<GraphNodeId, Set<GraphNodeId>> {
  const adj = new Map<GraphNodeId, Set<GraphNodeId>>();
  for (const n of nodes) {
    adj.set(n.id, new Set());
  }
  for (const e of edges) {
    adj.get(e.sourceGraphNodeId)?.add(e.targetGraphNodeId);
    adj.get(e.targetGraphNodeId)?.add(e.sourceGraphNodeId);
  }
  return adj;
}

function bfsComponent(adj: Map<GraphNodeId, Set<GraphNodeId>>, startId: GraphNodeId): Set<GraphNodeId> {
  const seen = new Set<GraphNodeId>();
  const queue: GraphNodeId[] = [startId];
  seen.add(startId);
  while (queue.length > 0) {
    const cur = queue.shift();
    if (!cur) continue;
    for (const nb of adj.get(cur) ?? []) {
      if (seen.has(nb)) continue;
      seen.add(nb);
      queue.push(nb);
    }
  }
  return seen;
}

/** Неориентированная компонента связности узла. */
export function getConnectedComponent(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  graphNodeId: GraphNodeId,
): Set<GraphNodeId> {
  const adj = buildAdjacency(nodes, edges);
  if (!adj.has(graphNodeId)) return new Set();
  return bfsComponent(adj, graphNodeId);
}

export function componentHasMainStart(nodes: SceneGraphNode[], component: Set<GraphNodeId>): boolean {
  return nodes.some((n) => component.has(n.id) && n.isStartScene);
}

export function componentHasSideStart(nodes: SceneGraphNode[], component: Set<GraphNodeId>): boolean {
  return nodes.some((n) => component.has(n.id) && n.isSideStoryStart);
}

/** Классификация связной компоненты графа для правил связей и стилей. */
export type StorylineBucket = 'main' | 'side' | 'free';

/**
 * main — в компоненте есть «НАЧАЛО» (основной сюжет);
 * side — есть «ПОБОЧНАЯ», но нет «НАЧАЛО» в той же компоненте;
 * free — нет ни одной стартовой метки в компоненте.
 */
export function getStorylineBucket(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  graphNodeId: GraphNodeId,
): StorylineBucket {
  const component = getConnectedComponent(nodes, edges, graphNodeId);
  if (componentHasMainStart(nodes, component)) return 'main';
  if (componentHasSideStart(nodes, component)) return 'side';
  return 'free';
}

/** Можно ли поставить синюю метку «ПОБОЧНАЯ» на узел. */
export function canSetSideStoryStart(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  graphNodeId: GraphNodeId,
): boolean {
  const component = getConnectedComponent(nodes, edges, graphNodeId);
  if (componentHasMainStart(nodes, component)) return false;
  if (componentHasSideStart(nodes, component)) return false;
  return true;
}

/** Карта узел → корень сюжета (основной приоритетнее побочного). */
export function buildStoryRootMap(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
): Map<GraphNodeId, StoryRoot> {
  const adj = buildAdjacency(nodes, edges);
  const roots = new Map<GraphNodeId, StoryRoot>();

  const mainStart = nodes.find((n) => n.isStartScene);
  if (mainStart) {
    for (const id of bfsComponent(adj, mainStart.id)) {
      roots.set(id, 'main');
    }
  }

  for (const sideStart of nodes.filter((n) => n.isSideStoryStart)) {
    for (const id of bfsComponent(adj, sideStart.id)) {
      if (!roots.has(id)) {
        roots.set(id, sideStart.id);
      }
    }
  }

  for (const n of nodes) {
    if (!roots.has(n.id)) {
      roots.set(n.id, null);
    }
  }

  return roots;
}

export function getNodeStoryRoot(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  graphNodeId: GraphNodeId,
): StoryRoot {
  return buildStoryRootMap(nodes, edges).get(graphNodeId) ?? null;
}

export function isNodeInSideStoryline(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  graphNodeId: GraphNodeId,
): boolean {
  return getStorylineBucket(nodes, edges, graphNodeId) === 'side';
}

export function isNodeInMainStoryline(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  graphNodeId: GraphNodeId,
): boolean {
  return getStorylineBucket(nodes, edges, graphNodeId) === 'main';
}

/** Все узлы одной побочной линии (по её стартовому узлу). */
export function getSideStoryComponentNodeIds(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  sideStartGraphNodeId: GraphNodeId,
): Set<GraphNodeId> {
  return getConnectedComponent(nodes, edges, sideStartGraphNodeId);
}

export function listSideStoryStarts(nodes: SceneGraphNode[]): SceneGraphNode[] {
  return nodes.filter((n) => n.isSideStoryStart);
}

/** true, если ребро целиком внутри одной побочной линии (по компоненте связности). */
export function isSideStoryEdge(
  nodes: SceneGraphNode[],
  edges: SceneGraphEdge[],
  edge: SceneGraphEdge,
): boolean {
  const srcBucket = getStorylineBucket(nodes, edges, edge.sourceGraphNodeId);
  const tgtBucket = getStorylineBucket(nodes, edges, edge.targetGraphNodeId);
  if (srcBucket !== 'side' || tgtBucket !== 'side') return false;
  const srcComp = getConnectedComponent(nodes, edges, edge.sourceGraphNodeId);
  return srcComp.has(edge.targetGraphNodeId);
}