// Sugiyama layered graph layout — pure-Dart implementation.
//
// This file implements the four classical Sugiyama phases:
//   1. Cycle removal (greedy DFS back-edge reversal)
//   2. Layer assignment (role-driven + longest-path fallback)
//   3. Crossing reduction (virtual nodes + alternating barycenter-median sweeps)
//   4. Coordinate assignment (Brandes-Köpf, four-way average)
//
// The output is a [SugiyamaResult] with final (x, y) positions for every real
// node plus polyline waypoints for any edge that spans more than one layer.
// Virtual nodes used internally during Phase 3/4 are NOT rendered as visible
// nodes; their coordinates only inform the edge waypoints.
//
// The file imports only `dart:math` and `dart:ui` so the layout can be safely
// dispatched to an isolate via `compute()` without pulling in Flutter binding
// initialization.

import 'dart:math' as math;
import 'dart:ui';

// ─── Public API ────────────────────────────────────────────────────────────

class SugiyamaInput {
  SugiyamaInput({
    required this.nodeIds,
    required this.edges,
    this.preassignedLayers,
    this.nodeSizes,
    this.config = const SugiyamaConfig(),
  });

  /// All real (non-virtual) node IDs participating in the graph.
  final List<String> nodeIds;

  /// Directed edges. The layout treats them as undirected for layering and
  /// crossing reduction, but the direction is preserved for downstream
  /// renderers that may care about arrow style.
  final List<SugiyamaEdge> edges;

  /// Optional layer hints. If a node ID maps to an int here, that layer is
  /// used as a constraint during Phase 2. Nodes without a hint get longest-
  /// path assignment, respecting hinted nodes as floor/ceiling constraints.
  final Map<String, int>? preassignedLayers;

  /// Optional per-node bounding box. Larger nodes get more horizontal space
  /// during Phase 4 compaction. If not provided, [SugiyamaConfig.defaultNodeSize]
  /// is used.
  final Map<String, Size>? nodeSizes;

  final SugiyamaConfig config;
}

class SugiyamaEdge {
  const SugiyamaEdge({required this.id, required this.from, required this.to});

  /// Stable opaque identifier used for downstream rendering (port label chips
  /// look this up). Not used by the layout algorithm itself.
  final String id;

  final String from;
  final String to;
}

class SugiyamaConfig {
  const SugiyamaConfig({
    this.layerSpacing = 144,
    this.nodeSpacing = 96,
    this.maxSweeps = 24,
    this.useBrandesKopf = true,
    this.defaultNodeSize = const Size(160, 110),
    this.virtualNodeCap = 1000,
  });

  /// Vertical distance between consecutive layers (top of next layer to top
  /// of current layer). Used as the per-layer Y stride; per-layer adjustment
  /// based on actual node heights is applied during coordinate assignment.
  final double layerSpacing;

  /// Minimum horizontal spacing between centers of two same-layer nodes.
  final double nodeSpacing;

  /// Hard upper bound on barycenter sweeps. Most graphs converge in <8.
  final int maxSweeps;

  /// When false, use a simpler median-X coordinate assignment instead of
  /// Brandes-Köpf. Useful as a debugging fallback if the alignment phase
  /// misbehaves on pathological inputs.
  final bool useBrandesKopf;

  /// Default bounding box used when [SugiyamaInput.nodeSizes] doesn't list a
  /// specific node. Matches the standard DeviceNode dimensions.
  final Size defaultNodeSize;

  /// Maximum virtual nodes to insert during Phase 3. If the graph would
  /// exceed this (many long-span edges), Phase 3 falls back to barycenter
  /// without virtuals — quality degrades gracefully rather than crashing.
  final int virtualNodeCap;
}

class SugiyamaResult {
  SugiyamaResult({
    required this.nodePositions,
    required this.edgeWaypoints,
    required this.canvasSize,
    required this.crossingCount,
    required this.layerCount,
    required this.computeTime,
    required this.virtualNodeCount,
  });

  /// Top-left position of every real node.
  final Map<String, Offset> nodePositions;

  /// For each edge ID whose span > 1 layer, a list of intermediate (x, y)
  /// waypoints (one per virtual node it passed through). Edges that span a
  /// single layer have no entry here; the renderer should draw them straight.
  final Map<String, List<Offset>> edgeWaypoints;

  /// Bounding box of the entire layout. Includes node width/height at the
  /// extremes plus a half-spacing margin.
  final Size canvasSize;

  /// Total crossings remaining after Phase 3. Useful for diagnostics; a value
  /// near 0 means the layout is very clean.
  final int crossingCount;

  /// Number of layers in the final layered graph (max layer index + 1).
  final int layerCount;

  /// Wall-clock time for the entire layout pipeline.
  final Duration computeTime;

  /// Number of virtual nodes inserted during Phase 3. For diagnostics; 0 if
  /// the cap was exceeded and Phase 3 fell back to no-virtuals mode.
  final int virtualNodeCount;
}

/// Compute a Sugiyama layout for the given input. Synchronous; safe to call
/// from an isolate via `compute()`.
SugiyamaResult computeSugiyamaLayout(SugiyamaInput input) {
  final stopwatch = Stopwatch()..start();

  if (input.nodeIds.isEmpty) {
    stopwatch.stop();
    return SugiyamaResult(
      nodePositions: const {},
      edgeWaypoints: const {},
      canvasSize: const Size(600, 400),
      crossingCount: 0,
      layerCount: 0,
      computeTime: stopwatch.elapsed,
      virtualNodeCount: 0,
    );
  }

  // Phase 1 — cycle removal: build a DAG so layering is well-defined.
  final cycleResult = _removeCycles(input.nodeIds, input.edges);

  // Phase 2 — layer assignment.
  final layerMap = _assignLayers(
    nodeIds: input.nodeIds,
    edges: cycleResult.acyclicEdges,
    preassigned: input.preassignedLayers,
  );

  // Phase 3 — virtual nodes + crossing reduction.
  final crossingResult = _reduceCrossings(
    nodeIds: input.nodeIds,
    edges: cycleResult.acyclicEdges,
    layers: layerMap,
    config: input.config,
  );

  // Phase 4 — coordinate assignment (Brandes-Köpf or simple).
  final coords = _assignCoordinates(
    realNodeIds: input.nodeIds.toSet(),
    layerOf: crossingResult.layerOf,
    layerOrder: crossingResult.layerOrder,
    upper: crossingResult.upper,
    lower: crossingResult.lower,
    nodeSizes: input.nodeSizes ?? const {},
    config: input.config,
  );

  // Build final node positions (real nodes only) and edge waypoints.
  final positions = <String, Offset>{};
  for (final id in input.nodeIds) {
    final x = coords.x[id];
    final y = coords.y[id];
    if (x != null && y != null) {
      final size = (input.nodeSizes ?? const {})[id] ?? input.config.defaultNodeSize;
      // Position is top-left; coords are node centers.
      positions[id] = Offset(x - size.width / 2, y - size.height / 2);
    }
  }

  final waypoints = <String, List<Offset>>{};
  for (final entry in crossingResult.edgeVirtualChain.entries) {
    final virtuals = entry.value;
    if (virtuals.isEmpty) continue;
    final points = <Offset>[];
    for (final v in virtuals) {
      final x = coords.x[v];
      final y = coords.y[v];
      if (x != null && y != null) points.add(Offset(x, y));
    }
    if (points.isNotEmpty) waypoints[entry.key] = points;
  }

  // Compute canvas bounds.
  double minX = double.infinity, minY = double.infinity;
  double maxX = -double.infinity, maxY = -double.infinity;
  for (final id in input.nodeIds) {
    final pos = positions[id];
    if (pos == null) continue;
    final size = (input.nodeSizes ?? const {})[id] ?? input.config.defaultNodeSize;
    if (pos.dx < minX) minX = pos.dx;
    if (pos.dy < minY) minY = pos.dy;
    if (pos.dx + size.width > maxX) maxX = pos.dx + size.width;
    if (pos.dy + size.height > maxY) maxY = pos.dy + size.height;
  }
  // Normalize so the top-left of the bounding box is at (margin, margin).
  final margin = input.config.nodeSpacing;
  final offsetX = margin - (minX.isFinite ? minX : 0);
  final offsetY = margin - (minY.isFinite ? minY : 0);
  final normalizedPositions = {
    for (final entry in positions.entries)
      entry.key: entry.value.translate(offsetX, offsetY),
  };
  final normalizedWaypoints = <String, List<Offset>>{
    for (final entry in waypoints.entries)
      entry.key: [for (final p in entry.value) p.translate(offsetX, offsetY)],
  };

  final width =
      (maxX.isFinite ? maxX : 600) - (minX.isFinite ? minX : 0) + margin * 2;
  final height =
      (maxY.isFinite ? maxY : 400) - (minY.isFinite ? minY : 0) + margin * 2;

  stopwatch.stop();
  return SugiyamaResult(
    nodePositions: normalizedPositions,
    edgeWaypoints: normalizedWaypoints,
    canvasSize: Size(width, height),
    crossingCount: crossingResult.crossingCount,
    layerCount: crossingResult.layerOrder.length,
    computeTime: stopwatch.elapsed,
    virtualNodeCount: crossingResult.virtualCount,
  );
}

// ─── Phase 1: Cycle removal ────────────────────────────────────────────────

class _CycleResult {
  _CycleResult({required this.acyclicEdges, required this.reversed});

  /// Edges with cycle-breaking back-edges reversed. The total edge count
  /// equals the input edge count.
  final List<SugiyamaEdge> acyclicEdges;

  /// IDs of edges that were reversed. Stored for downstream renderers that
  /// may want to draw the reversed direction differently (we currently don't).
  final Set<String> reversed;
}

_CycleResult _removeCycles(List<String> nodes, List<SugiyamaEdge> edges) {
  // Adjacency list for the original graph.
  final adj = <String, List<SugiyamaEdge>>{};
  for (final e in edges) {
    adj.putIfAbsent(e.from, () => []).add(e);
  }

  // DFS coloring: 0 = unvisited, 1 = on-stack, 2 = done.
  final color = <String, int>{for (final n in nodes) n: 0};
  final reversed = <String>{};

  void visit(String v) {
    color[v] = 1;
    for (final e in adj[v] ?? const <SugiyamaEdge>[]) {
      final c = color[e.to] ?? 0;
      if (c == 1) {
        // Back-edge: this would close a cycle. Mark for reversal.
        reversed.add(e.id);
      } else if (c == 0) {
        visit(e.to);
      }
    }
    color[v] = 2;
  }

  for (final n in nodes) {
    if ((color[n] ?? 0) == 0) visit(n);
  }

  final acyclicEdges = <SugiyamaEdge>[
    for (final e in edges)
      if (reversed.contains(e.id))
        SugiyamaEdge(id: e.id, from: e.to, to: e.from)
      else
        e,
  ];

  return _CycleResult(acyclicEdges: acyclicEdges, reversed: reversed);
}

// ─── Phase 2: Layer assignment ─────────────────────────────────────────────

/// Longest-path assignment, respecting preassigned layers as floor constraints.
/// Returns a map from node id → layer index (0 = topmost).
Map<String, int> _assignLayers({
  required List<String> nodeIds,
  required List<SugiyamaEdge> edges,
  required Map<String, int>? preassigned,
}) {
  final adj = <String, List<String>>{};
  final inDeg = <String, int>{for (final n in nodeIds) n: 0};
  for (final e in edges) {
    adj.putIfAbsent(e.from, () => []).add(e.to);
    inDeg[e.to] = (inDeg[e.to] ?? 0) + 1;
  }

  // Topological order via Kahn's algorithm.
  final queue = <String>[
    for (final entry in inDeg.entries)
      if (entry.value == 0) entry.key,
  ];
  final topo = <String>[];
  final indeg = Map<String, int>.from(inDeg);
  while (queue.isNotEmpty) {
    final n = queue.removeAt(0);
    topo.add(n);
    for (final m in adj[n] ?? const <String>[]) {
      indeg[m] = (indeg[m] ?? 0) - 1;
      if (indeg[m] == 0) queue.add(m);
    }
  }
  // Handle any leftovers (shouldn't happen post-Phase-1 but guard for safety).
  for (final n in nodeIds) {
    if (!topo.contains(n)) topo.add(n);
  }

  final layer = <String, int>{};

  // Helper to enforce preassigned hints as both floor AND ceiling for the
  // hinted node itself. Non-hinted nodes use computed layer freely.
  int initialLayerFor(String n) {
    final hint = preassigned?[n];
    return hint ?? 0;
  }

  for (final n in topo) {
    var best = initialLayerFor(n);
    // For preassigned nodes, the hint is authoritative.
    if (preassigned?.containsKey(n) ?? false) {
      layer[n] = preassigned![n]!;
      continue;
    }
    // For unassigned nodes, longest-path from parents.
    var hasParent = false;
    for (final e in edges) {
      if (e.to != n) continue;
      hasParent = true;
      final parentLayer = layer[e.from];
      if (parentLayer != null && parentLayer + 1 > best) {
        best = parentLayer + 1;
      }
    }
    if (!hasParent) {
      // Source node with no hint → put on the topmost free layer.
      best = 0;
    }
    layer[n] = best;
  }

  // Second pass: push sinks down so they don't crowd above their parents.
  // For each unassigned node, ensure layer ≥ max(parent.layer) + 1.
  for (final n in topo) {
    if (preassigned?.containsKey(n) ?? false) continue;
    var maxParent = -1;
    for (final e in edges) {
      if (e.to != n) continue;
      final p = layer[e.from];
      if (p != null && p > maxParent) maxParent = p;
    }
    if (maxParent >= 0 && (layer[n] ?? 0) <= maxParent) {
      layer[n] = maxParent + 1;
    }
  }

  // Normalize: shift so the minimum layer is 0.
  if (layer.isEmpty) return layer;
  final minLayer = layer.values.reduce(math.min);
  if (minLayer != 0) {
    for (final k in layer.keys.toList()) {
      layer[k] = layer[k]! - minLayer;
    }
  }

  return layer;
}

// ─── Phase 3: Crossing reduction (virtual nodes + barycenter sweeps) ──────

class _CrossingResult {
  _CrossingResult({
    required this.layerOf,
    required this.layerOrder,
    required this.upper,
    required this.lower,
    required this.edgeVirtualChain,
    required this.crossingCount,
    required this.virtualCount,
  });

  /// Final layer index for every node (real and virtual).
  final Map<String, int> layerOf;

  /// For each layer, the ordered list of node IDs (real and virtual).
  final List<List<String>> layerOrder;

  /// Adjacency to upper neighbors (one layer above): node → list of node IDs.
  final Map<String, List<String>> upper;

  /// Adjacency to lower neighbors.
  final Map<String, List<String>> lower;

  /// For each original edge ID, the chain of virtual node IDs it passed
  /// through (empty for single-layer edges).
  final Map<String, List<String>> edgeVirtualChain;

  /// Total crossings remaining after the best sweep.
  final int crossingCount;

  /// How many virtual nodes were inserted.
  final int virtualCount;
}

_CrossingResult _reduceCrossings({
  required List<String> nodeIds,
  required List<SugiyamaEdge> edges,
  required Map<String, int> layers,
  required SugiyamaConfig config,
}) {
  // Step 1: insert virtual nodes for multi-layer edges.
  final layerOf = Map<String, int>.from(layers);
  final upper = <String, List<String>>{};
  final lower = <String, List<String>>{};
  final edgeVirtualChain = <String, List<String>>{};
  var virtualCounter = 0;
  var virtualCap = config.virtualNodeCap;

  void connect(String from, String to) {
    upper.putIfAbsent(to, () => []).add(from);
    lower.putIfAbsent(from, () => []).add(to);
  }

  for (final e in edges) {
    final lFrom = layerOf[e.from];
    final lTo = layerOf[e.to];
    if (lFrom == null || lTo == null) continue;
    if (lFrom == lTo) {
      // Same-layer edge: rare in well-formed network data. We still record
      // adjacency so crossing reduction sees it, but it cannot affect crossings.
      connect(e.from, e.to);
      continue;
    }
    final low = math.min(lFrom, lTo);
    final high = math.max(lFrom, lTo);
    if (high - low == 1) {
      connect(e.from, e.to);
      continue;
    }
    // Insert virtual nodes for every intermediate layer.
    if (virtualCounter + (high - low - 1) > virtualCap) {
      // Cap exceeded — degrade gracefully: connect endpoints directly.
      // The renderer will draw a straight line, which is uglier but stable.
      connect(e.from, e.to);
      continue;
    }
    final chain = <String>[];
    String prev = lFrom < lTo ? e.from : e.to;
    final startLayer = lFrom < lTo ? lFrom : lTo;
    final endLayer = lFrom < lTo ? lTo : lFrom;
    final endpoint = lFrom < lTo ? e.to : e.from;
    for (var l = startLayer + 1; l < endLayer; l++) {
      final vid = '__v${virtualCounter++}';
      layerOf[vid] = l;
      chain.add(vid);
      connect(prev, vid);
      prev = vid;
    }
    connect(prev, endpoint);
    edgeVirtualChain[e.id] = chain;
  }

  // Step 2: initial ordering per layer (real nodes by input order, virtuals
  // appended). We'll refine via sweeps.
  final layerCount =
      layerOf.values.isEmpty ? 0 : layerOf.values.reduce(math.max) + 1;
  final layerOrder = List<List<String>>.generate(layerCount, (_) => <String>[]);
  for (final id in nodeIds) {
    final l = layerOf[id];
    if (l != null) layerOrder[l].add(id);
  }
  for (final entry in layerOf.entries) {
    if (!entry.key.startsWith('__v')) continue;
    layerOrder[entry.value].add(entry.key);
  }

  // Step 3: alternating down + up sweeps using median barycenter.
  var crossings = _countAllCrossings(layerOrder, upper);
  var bestCrossings = crossings;
  var bestOrder = _cloneOrder(layerOrder);
  var noImprovement = 0;

  for (var sweep = 0; sweep < config.maxSweeps && noImprovement < 4; sweep++) {
    final isDown = sweep.isEven;
    if (isDown) {
      // Top → bottom: layer l reorders by median X of its upper neighbors.
      for (var l = 1; l < layerCount; l++) {
        _reorderByMedian(layerOrder, l, upper, layerOrder[l - 1]);
      }
    } else {
      // Bottom → top: layer l reorders by median X of its lower neighbors.
      for (var l = layerCount - 2; l >= 0; l--) {
        _reorderByMedian(layerOrder, l, lower, layerOrder[l + 1]);
      }
    }
    final c = _countAllCrossings(layerOrder, upper);
    if (c < bestCrossings) {
      bestCrossings = c;
      bestOrder = _cloneOrder(layerOrder);
      noImprovement = 0;
    } else {
      noImprovement++;
    }
    crossings = c;
  }

  return _CrossingResult(
    layerOf: layerOf,
    layerOrder: bestOrder,
    upper: upper,
    lower: lower,
    edgeVirtualChain: edgeVirtualChain,
    crossingCount: bestCrossings,
    virtualCount: virtualCounter,
  );
}

List<List<String>> _cloneOrder(List<List<String>> source) {
  return [for (final layer in source) List<String>.from(layer)];
}

/// Reorder the given layer by the median index of each node's neighbors in
/// [reference] (the adjacent layer). Nodes with no neighbors keep their
/// relative order.
void _reorderByMedian(
  List<List<String>> layerOrder,
  int layerIndex,
  Map<String, List<String>> adjacency,
  List<String> reference,
) {
  final indexOf = <String, int>{
    for (var i = 0; i < reference.length; i++) reference[i]: i,
  };
  final layer = layerOrder[layerIndex];
  final keys = <String, double>{};
  for (var i = 0; i < layer.length; i++) {
    final id = layer[i];
    final neighbors = adjacency[id] ?? const <String>[];
    final indexes = <int>[
      for (final n in neighbors)
        if (indexOf.containsKey(n)) indexOf[n]!,
    ]..sort();
    if (indexes.isEmpty) {
      keys[id] = i.toDouble(); // stable: keep current position
    } else if (indexes.length.isOdd) {
      keys[id] = indexes[indexes.length ~/ 2].toDouble();
    } else {
      // Even count: use the average of the two middle indexes (Eades-Wormald).
      final m1 = indexes[indexes.length ~/ 2 - 1];
      final m2 = indexes[indexes.length ~/ 2];
      keys[id] = (m1 + m2) / 2;
    }
  }
  layer.sort((a, b) {
    final cmp = (keys[a] ?? 0).compareTo(keys[b] ?? 0);
    if (cmp != 0) return cmp;
    // Stable tiebreak by current index.
    return layer.indexOf(a).compareTo(layer.indexOf(b));
  });
}

/// Count edge crossings between every pair of adjacent layers. O(E log E) via
/// the standard merge-sort inversion count, applied per layer pair.
int _countAllCrossings(
    List<List<String>> layerOrder, Map<String, List<String>> upper) {
  var total = 0;
  for (var l = 1; l < layerOrder.length; l++) {
    total += _countCrossingsBetween(layerOrder[l - 1], layerOrder[l], upper);
  }
  return total;
}

int _countCrossingsBetween(
  List<String> top,
  List<String> bottom,
  Map<String, List<String>> upper,
) {
  // Build the list of (top-index, bottom-index) pairs sorted by bottom-index.
  // Crossings = inversions in the list of top-indexes when read in bottom-order.
  final topIndex = <String, int>{
    for (var i = 0; i < top.length; i++) top[i]: i,
  };
  final pairs = <int>[];
  for (var bi = 0; bi < bottom.length; bi++) {
    final neighbors = upper[bottom[bi]] ?? const <String>[];
    final sorted = <int>[
      for (final n in neighbors)
        if (topIndex.containsKey(n)) topIndex[n]!,
    ]..sort();
    pairs.addAll(sorted);
  }
  // Inversion count via merge sort.
  return _mergeSortInversions(pairs, 0, pairs.length - 1);
}

int _mergeSortInversions(List<int> a, int lo, int hi) {
  if (lo >= hi) return 0;
  final mid = (lo + hi) ~/ 2;
  var count = _mergeSortInversions(a, lo, mid) +
      _mergeSortInversions(a, mid + 1, hi);
  // Merge.
  final tmp = <int>[];
  var i = lo;
  var j = mid + 1;
  while (i <= mid && j <= hi) {
    if (a[i] <= a[j]) {
      tmp.add(a[i++]);
    } else {
      tmp.add(a[j++]);
      count += mid - i + 1;
    }
  }
  while (i <= mid) {
    tmp.add(a[i++]);
  }
  while (j <= hi) {
    tmp.add(a[j++]);
  }
  for (var k = 0; k < tmp.length; k++) {
    a[lo + k] = tmp[k];
  }
  return count;
}

// ─── Phase 4: Coordinate assignment ───────────────────────────────────────

class _CoordResult {
  _CoordResult({required this.x, required this.y});

  /// X coordinate of every node center (real and virtual).
  final Map<String, double> x;

  /// Y coordinate of every node center.
  final Map<String, double> y;
}

_CoordResult _assignCoordinates({
  required Set<String> realNodeIds,
  required Map<String, int> layerOf,
  required List<List<String>> layerOrder,
  required Map<String, List<String>> upper,
  required Map<String, List<String>> lower,
  required Map<String, Size> nodeSizes,
  required SugiyamaConfig config,
}) {
  // Y coordinates: layer * layerSpacing, adjusted for max node height per layer.
  final y = <String, double>{};
  var cursorY = 0.0;
  for (var l = 0; l < layerOrder.length; l++) {
    var maxH = config.defaultNodeSize.height;
    for (final id in layerOrder[l]) {
      final h = nodeSizes[id]?.height ?? config.defaultNodeSize.height;
      if (h > maxH) maxH = h;
    }
    final layerY = cursorY + maxH / 2;
    for (final id in layerOrder[l]) {
      y[id] = layerY;
    }
    cursorY += maxH + config.layerSpacing;
  }

  // X coordinates:
  //   - Brandes-Köpf when enabled: 4-pass alignment + averaging.
  //   - Fallback: simple per-layer compaction using median-X.
  Map<String, double> x;
  if (config.useBrandesKopf) {
    x = _brandesKopf(
      layerOrder: layerOrder,
      upper: upper,
      lower: lower,
      nodeSizes: nodeSizes,
      config: config,
    );
  } else {
    x = _simpleXAssignment(layerOrder, nodeSizes, config);
  }

  return _CoordResult(x: x, y: y);
}

/// Simple per-layer X assignment: nodes laid out left-to-right with
/// [nodeSpacing] between centers, using max(node width, defaultNodeSize.width)
/// per node.
Map<String, double> _simpleXAssignment(
  List<List<String>> layerOrder,
  Map<String, Size> nodeSizes,
  SugiyamaConfig config,
) {
  final x = <String, double>{};
  for (final layer in layerOrder) {
    var cursor = 0.0;
    for (final id in layer) {
      final w = nodeSizes[id]?.width ?? config.defaultNodeSize.width;
      x[id] = cursor + w / 2;
      cursor += w + config.nodeSpacing;
    }
  }
  // Center each layer horizontally by shifting to the global midpoint.
  var globalMaxX = 0.0;
  for (final layer in layerOrder) {
    if (layer.isEmpty) continue;
    final lastId = layer.last;
    final lastX = x[lastId] ?? 0;
    final lastW =
        nodeSizes[lastId]?.width ?? config.defaultNodeSize.width;
    if (lastX + lastW / 2 > globalMaxX) globalMaxX = lastX + lastW / 2;
  }
  for (final layer in layerOrder) {
    if (layer.isEmpty) continue;
    final lastId = layer.last;
    final lastX = x[lastId] ?? 0;
    final lastW =
        nodeSizes[lastId]?.width ?? config.defaultNodeSize.width;
    final layerW = lastX + lastW / 2;
    final shift = (globalMaxX - layerW) / 2;
    if (shift > 0) {
      for (final id in layer) {
        x[id] = (x[id] ?? 0) + shift;
      }
    }
  }
  return x;
}

/// Brandes-Köpf horizontal coordinate assignment. Four passes (combinations of
/// up/down and left/right), then averages the resulting X coordinates.
///
/// Reference: U. Brandes & B. Köpf, "Fast and Simple Horizontal Coordinate
/// Assignment", Graph Drawing 2001.
Map<String, double> _brandesKopf({
  required List<List<String>> layerOrder,
  required Map<String, List<String>> upper,
  required Map<String, List<String>> lower,
  required Map<String, Size> nodeSizes,
  required SugiyamaConfig config,
}) {
  // Step 1: mark "type 1" conflicts — edges between two non-virtual nodes
  // that cross an edge involving a virtual node. These are the "hard" cases.
  final type1Conflicts = _markType1Conflicts(layerOrder, upper);

  // Run 4 passes: (up, left), (up, right), (down, left), (down, right).
  final passResults = <Map<String, double>>[];
  for (final goingDown in [false, true]) {
    for (final goingLeft in [false, true]) {
      final root = <String, String>{};
      final align = <String, String>{};
      for (final layer in layerOrder) {
        for (final id in layer) {
          root[id] = id;
          align[id] = id;
        }
      }

      _verticalAlign(
        layerOrder: layerOrder,
        adjacency: goingDown ? lower : upper,
        type1Conflicts: type1Conflicts,
        root: root,
        align: align,
        goingDown: goingDown,
        goingLeft: goingLeft,
      );

      final x = _horizontalCompaction(
        layerOrder: layerOrder,
        root: root,
        align: align,
        nodeSizes: nodeSizes,
        config: config,
        goingLeft: goingLeft,
      );
      passResults.add(x);
    }
  }

  // Step 2: balance — for each node, average the four x coordinates after
  // normalizing each pass to the same min-X. Brandes-Köpf paper uses median
  // of 4 values, which is equivalent to average for our 4-pass case.
  final balanced = <String, double>{};
  for (final layer in layerOrder) {
    for (final id in layer) {
      final xs = [
        for (final r in passResults)
          if (r[id] != null) r[id]!,
      ]..sort();
      if (xs.isEmpty) continue;
      // Average of the middle two (or all 4): produces stable result.
      if (xs.length >= 2) {
        balanced[id] = (xs[xs.length ~/ 2 - 1] + xs[xs.length ~/ 2]) / 2;
      } else {
        balanced[id] = xs.first;
      }
    }
  }
  return balanced;
}

/// Mark edges that are type-1 conflicts in Brandes-Köpf terminology: an edge
/// (u, v) is a conflict if it crosses an edge (u', v') where exactly one of
/// u/v is virtual and one of u'/v' is also virtual (different orientation).
/// We approximate by checking: if both endpoints are virtual, the edge is
/// never the "conflicting" one; otherwise, it conflicts with any virtual-to-
/// virtual edge that crosses it.
Set<String> _markType1Conflicts(
  List<List<String>> layerOrder,
  Map<String, List<String>> upper,
) {
  final conflicts = <String>{};
  for (var l = 1; l < layerOrder.length; l++) {
    final top = layerOrder[l - 1];
    final bot = layerOrder[l];
    final topIndex = <String, int>{
      for (var i = 0; i < top.length; i++) top[i]: i,
    };
    // For each bottom node, find its upper neighbors and sort by top-index.
    var k0 = 0;
    var k1 = top.length - 1;
    for (var bi = 0; bi < bot.length; bi++) {
      final v = bot[bi];
      final isVirtual = v.startsWith('__v');
      if (!isVirtual && bi < bot.length - 1) continue;

      // For inner-segment endpoints (both virtual), tighten search bounds.
      if (isVirtual || bi == bot.length - 1) {
        final neighborTopIndexes = <int>[
          for (final u in upper[v] ?? const <String>[])
            if (topIndex.containsKey(u)) topIndex[u]!,
        ]..sort();
        if (neighborTopIndexes.isEmpty) continue;
        final k1Local = neighborTopIndexes.last;
        // Walk preceding bottom nodes from k0 to bi, marking conflicts.
        for (var bj = k0; bj <= bi; bj++) {
          final bjNode = bot[bj];
          for (final un in upper[bjNode] ?? const <String>[]) {
            final ui = topIndex[un];
            if (ui == null) continue;
            if (ui < k0 || ui > k1Local) {
              // This edge crosses an inner segment — type-1 conflict.
              conflicts.add('$un|$bjNode');
            }
          }
        }
        k0 = bi + 1;
        k1 = k1Local;
      }
    }
    // k1 used only as scratch; keep loop tidy
    if (k1 < 0) k1 = top.length - 1;
  }
  return conflicts;
}

/// Vertical alignment phase: link each node to its median neighbor in
/// [adjacency] (upper for "up" passes, lower for "down" passes). Skip linkings
/// that would conflict with already-marked type-1 conflicts.
void _verticalAlign({
  required List<List<String>> layerOrder,
  required Map<String, List<String>> adjacency,
  required Set<String> type1Conflicts,
  required Map<String, String> root,
  required Map<String, String> align,
  required bool goingDown,
  required bool goingLeft,
}) {
  final iter = goingDown
      ? List<int>.generate(layerOrder.length, (i) => i)
      : List<int>.generate(layerOrder.length, (i) => layerOrder.length - 1 - i);

  for (final layerIdx in iter) {
    final layer = layerOrder[layerIdx];
    var r = goingLeft ? -1 : layerOrder.fold<int>(0, (acc, l) => math.max(acc, l.length));
    final orderedNodes = goingLeft ? layer : layer.reversed.toList();
    for (final v in orderedNodes) {
      final neighbors = adjacency[v] ?? const <String>[];
      if (neighbors.isEmpty) continue;
      // Build sorted list of neighbor indexes within their layer.
      final adjLayerIdx = goingDown ? layerIdx + 1 : layerIdx - 1;
      if (adjLayerIdx < 0 || adjLayerIdx >= layerOrder.length) continue;
      final adjLayer = layerOrder[adjLayerIdx];
      final adjIndex = <String, int>{
        for (var i = 0; i < adjLayer.length; i++) adjLayer[i]: i,
      };
      final sortedNeighbors = <(int, String)>[
        for (final n in neighbors)
          if (adjIndex.containsKey(n)) (adjIndex[n]!, n),
      ]..sort((a, b) => a.$1.compareTo(b.$1));
      if (sortedNeighbors.isEmpty) continue;

      // Pick the median neighbor(s) per Brandes-Köpf.
      final m1 = (sortedNeighbors.length - 1) ~/ 2;
      final m2 = sortedNeighbors.length ~/ 2;
      final medians = m1 == m2 ? [sortedNeighbors[m1]] : [sortedNeighbors[m1], sortedNeighbors[m2]];

      for (final (mIdx, mNode) in medians) {
        if (align[v] != v) continue; // already aligned
        // Check direction: only consider neighbors strictly to one side of r.
        final wantStrictlyAfter = !goingLeft;
        if ((wantStrictlyAfter && mIdx > r) ||
            (!wantStrictlyAfter && mIdx < r)) {
          // Check type-1 conflict.
          final edgeKey = goingDown ? '$v|$mNode' : '$mNode|$v';
          if (type1Conflicts.contains(edgeKey)) continue;
          align[mNode] = v;
          root[v] = root[mNode] ?? mNode;
          align[v] = root[v]!;
          r = mIdx;
        }
      }
    }
  }
}

/// Horizontal compaction: lay out aligned chains while respecting minimum
/// spacing. The resulting X positions are then optionally mirrored for
/// "leftward" passes.
Map<String, double> _horizontalCompaction({
  required List<List<String>> layerOrder,
  required Map<String, String> root,
  required Map<String, String> align,
  required Map<String, Size> nodeSizes,
  required SugiyamaConfig config,
  required bool goingLeft,
}) {
  // Each root node anchors a chain. We compute x for each root, then propagate
  // to its aligned descendants.
  final sink = <String, String>{};
  final shift = <String, double>{};
  final x = <String, double>{};

  for (final layer in layerOrder) {
    for (final id in layer) {
      sink[id] = id;
      shift[id] = double.infinity;
      x[id] = double.nan;
    }
  }

  // Position roots in topological scan order; descendants inherit.
  void placeBlock(String v) {
    if (!x[v]!.isNaN) return;
    x[v] = 0;
    var w = v;
    do {
      final layerOfW = _findLayer(layerOrder, w);
      if (layerOfW == -1) break;
      final layer = layerOrder[layerOfW];
      final idx = layer.indexOf(w);
      if (goingLeft ? idx < layer.length - 1 : idx > 0) {
        final pred = goingLeft ? layer[idx + 1] : layer[idx - 1];
        final u = root[pred]!;
        placeBlock(u);
        final widthPred =
            nodeSizes[pred]?.width ?? config.defaultNodeSize.width;
        final widthW = nodeSizes[w]?.width ?? config.defaultNodeSize.width;
        final minDelta = (widthPred + widthW) / 2 + config.nodeSpacing;
        if (sink[v] == v) sink[v] = sink[u]!;
        if (sink[v] != sink[u]) {
          final candidate = goingLeft
              ? x[u]! - x[v]! - minDelta
              : x[u]! + minDelta - x[v]!;
          final s = shift[sink[u]!]!;
          shift[sink[u]!] = goingLeft
              ? (s == double.infinity ? candidate : math.max(s, candidate))
              : (s == double.infinity ? candidate : math.min(s, candidate));
        } else {
          x[v] = goingLeft
              ? math.min(x[v]!, x[u]! - minDelta)
              : math.max(x[v]!, x[u]! + minDelta);
        }
      }
      w = align[w]!;
    } while (w != v);
  }

  for (final layer in layerOrder) {
    for (final id in layer) {
      if (root[id] == id) placeBlock(id);
    }
  }

  // Propagate root coordinates to aligned descendants and apply shifts.
  for (final layer in layerOrder) {
    for (final id in layer) {
      final r = root[id]!;
      var xr = x[r]!;
      if (xr.isNaN) xr = 0;
      final s = shift[sink[r]!]!;
      final adjusted = s.isFinite ? xr + s : xr;
      x[id] = adjusted;
    }
  }

  // Normalize: shift so minimum x = 0.
  final values = x.values.where((v) => v.isFinite).toList();
  if (values.isEmpty) return x;
  final minX = values.reduce(math.min);
  for (final k in x.keys.toList()) {
    final v = x[k]!;
    x[k] = v.isFinite ? v - minX : 0;
  }

  return x;
}

int _findLayer(List<List<String>> layerOrder, String id) {
  for (var i = 0; i < layerOrder.length; i++) {
    if (layerOrder[i].contains(id)) return i;
  }
  return -1;
}