Files
alan fb1935a62d Keep graph edge labels clear of nodes and other labels
The linear layout used by the definition and run graphs placed each
outcome label at the middle of its widest run with no collision check,
and the run graph measured only the label text while rendering an order
badge in front of it, so taken labels ran into the next node.

Labels now try positions along their own route (horizontal runs above
and below, sliding along, then vertical runs) and take the first whose
box stays 4px clear of every node and earlier label, preferring spots
off other wires. If a label finds no spot, the layout widens its column
gaps and lanes and runs again; a last-resort shelf below the drawing
never overlaps. The run graph measures the exact badge+label widget it
renders, keyed by edge id.
2026-10-31 16:36:48 +00:00

571 lines
17 KiB
Dart

import 'dart:math' as math;
import '../domain/graph_definition.dart';
import '../domain/graph_protocol.dart';
import '../routing/route_models.dart';
import 'layout_models.dart';
import 'linear_label_placement.dart';
/// Graph-space spacings for [layoutLinearGraph], the web's
/// `DEFAULT_GRAPH_METRICS` tightened for a phone-sized canvas.
class LinearGraphMetrics {
const LinearGraphMetrics({
this.hGap = 48,
this.pad = 24,
this.laneSpacing = 28,
this.terminalGap = 24,
this.trackStep = 24,
this.portSpacing = 12,
this.labelPadding = 10,
this.labelGap = 3,
});
final double hGap;
final double pad;
final double laneSpacing;
final double terminalGap;
final double trackStep;
final double portSpacing;
final double labelPadding;
final double labelGap;
/// These metrics with every column gap and lane widened by [width] and
/// [height], making room for one more label in each.
LinearGraphMetrics widenedBy(double width, double height) =>
LinearGraphMetrics(
hGap: hGap + width,
pad: pad,
laneSpacing: laneSpacing + height,
terminalGap: terminalGap,
trackStep: trackStep,
portSpacing: portSpacing,
labelPadding: labelPadding,
labelGap: labelGap,
);
}
/// How many times [layoutLinearGraph] widens its gaps for a crowded label
/// before it falls back to the free shelf below the drawing.
const int _maxWidening = 4;
/// The web's `layoutGraph` (web/src/graph.js): stages keep their declaration
/// order on one row; Failure and Success share a lower row, Failure on the
/// left, the pair centred. Every edge that is not a straight step to the next
/// stage gets its own lane below the stage row, in stable edge-id order, so no
/// two runs share a track. Pure: measured extents in, geometry out.
///
/// No label box comes within [edgeLabelClearance] of a node or another label.
/// When a label finds no such spot on its own route, the column gaps and lanes
/// grow by the widest and tallest label and the layout runs again, rather than
/// letting a label cover a node.
(GraphLayout, GraphRouting) layoutLinearGraph({
required List<GraphNode> nodes,
required List<GraphEdge> edges,
required Map<String, NodeExtent> extents,
required Map<int, LabelExtent> labelExtents,
LinearGraphMetrics metrics = const LinearGraphMetrics(),
}) {
var widest = 0.0, tallest = 0.0;
for (final extent in labelExtents.values) {
widest = math.max(widest, extent.width);
tallest = math.max(tallest, extent.height);
}
var m = metrics;
for (var attempt = 0; ; attempt++) {
final (result, misfits) = _layoutPass(
nodes: nodes,
edges: edges,
extents: extents,
labelExtents: labelExtents,
metrics: m,
);
if (misfits.isEmpty || attempt == _maxWidening) return result;
m = m.widenedBy(
widest + 2 * edgeLabelClearance,
tallest + 2 * edgeLabelClearance,
);
}
}
((GraphLayout, GraphRouting), Set<int>) _layoutPass({
required List<GraphNode> nodes,
required List<GraphEdge> edges,
required Map<String, NodeExtent> extents,
required Map<int, LabelExtent> labelExtents,
required LinearGraphMetrics metrics,
}) {
final m = metrics;
final stages = [
for (final node in nodes)
if (!node.terminal) node,
];
final terminals = {
for (final node in nodes)
if (node.terminal) node.key: node,
};
NodeExtent extentOf(String key) {
final extent = extents[key];
if (extent == null) {
throw ArgumentError.value(key, 'extents', 'missing measured extent');
}
return extent;
}
final rank = {for (var i = 0; i < stages.length; i++) stages[i].key: i};
final ordered = [...edges]..sort((a, b) => a.id.compareTo(b.id));
final placed = <GraphEdge>[];
final skipped = <RouteDiagnostic>[];
for (final edge in ordered) {
final knownSource = rank.containsKey(edge.source);
final knownTarget =
edge.knownTarget &&
(rank.containsKey(edge.target) || terminals.containsKey(edge.target));
if (knownSource && knownTarget) {
placed.add(edge);
continue;
}
skipped.add(
RouteDiagnostic(
id: edge.id,
source: edge.source,
outcome: edge.outcome,
target: edge.target,
reason: knownSource
? RouteSkipReason.unknownTarget
: RouteSkipReason.unknownSource,
message: knownSource
? (edge.target.isEmpty
? 'edge target is empty'
: 'target "${edge.target}" has no placed node')
: 'source "${edge.source}" has no placed node',
),
);
}
if (stages.isEmpty) {
return (
(
GraphLayout(
nodes: const [],
width: 0,
height: 0,
rankCount: 0,
ranks: const {},
),
GraphRouting(
routes: const [],
labels: const [],
skipped: skipped,
width: 0,
height: 0,
),
),
const <int>{},
);
}
final stageCount = stages.length;
final hasTerminal = terminals.isNotEmpty;
bool isForward(GraphEdge edge) =>
!isTerminalTarget(edge.target) &&
rank[edge.target] == rank[edge.source]! + 1;
LabelExtent labelOf(GraphEdge edge) =>
labelExtents[edge.id] ?? LabelExtent(width: 0, height: 0);
final labelHeight = placed.fold<double>(
0,
(tallest, edge) => math.max(tallest, labelOf(edge).height),
);
// A lane holds its label above the wire.
final laneSpacing = math.max(m.laneSpacing, labelHeight + 2 * m.labelGap + 4);
// A gap is as wide as its widest straight-route label plus breathing room,
// so a label never reaches into either neighbouring box.
final gapWidths = List<double>.filled(stageCount, m.hGap);
for (final edge in placed) {
if (!isForward(edge)) continue;
final target = rank[edge.target]!;
gapWidths[target] = math.max(
gapWidths[target],
labelOf(edge).width + 2 * m.labelPadding,
);
}
final contentLeft = m.pad + m.hGap;
final stageXs = <double>[];
var nextX = contentLeft;
for (var i = 0; i < stageCount; i++) {
if (i > 0) nextX += gapWidths[i];
stageXs.add(nextX);
nextX += extentOf(stages[i].key).width;
}
final stageRowRight = nextX;
final rowHeight = stages.fold<double>(
0,
(tallest, stage) => math.max(tallest, extentOf(stage.key).height),
);
final stageBottom = m.pad + rowHeight;
final laneEdges = [
for (final edge in placed)
if (!isForward(edge)) edge,
];
final laneIndex = {
for (var i = 0; i < laneEdges.length; i++) laneEdges[i].id: i,
};
double laneY(GraphEdge edge) =>
stageBottom + (laneIndex[edge.id]! + 1) * laneSpacing;
final terminalY =
stageBottom + (laneEdges.length + 1) * laneSpacing + m.terminalGap;
// A terminal grows with its incoming routes so each gets its own top port.
double terminalWidth(String key) {
final incoming = placed.where((edge) => edge.target == key).length;
return math.max(
extentOf(key).width,
incoming * m.trackStep + 4 * m.portSpacing,
);
}
final failureWidth = terminals.containsKey(failureEnd)
? terminalWidth(failureEnd)
: 0.0;
final successWidth = terminals.containsKey(successEnd)
? terminalWidth(successEnd)
: 0.0;
final pairInner =
failureWidth +
successWidth +
(failureWidth > 0 && successWidth > 0 ? m.hGap : 0);
final width = math.max(stageRowRight + m.hGap + m.pad, pairInner + 2 * m.pad);
final boxes = <GraphNodeBox>[
for (var i = 0; i < stageCount; i++)
GraphNodeBox(
key: stages[i].key,
terminal: false,
stageIndex: stages[i].stageIndex,
rank: i,
x: stageXs[i],
y: m.pad + (rowHeight - extentOf(stages[i].key).height) / 2,
width: extentOf(stages[i].key).width,
height: extentOf(stages[i].key).height,
),
];
if (hasTerminal) {
var x = width / 2 - pairInner / 2;
for (final (key, terminalW) in [
(failureEnd, failureWidth),
(successEnd, successWidth),
]) {
final node = terminals[key];
if (node == null) continue;
boxes.add(
GraphNodeBox(
key: key,
terminal: true,
stageIndex: null,
rank: stageCount,
x: x,
y: terminalY,
width: terminalW,
height: extentOf(key).height,
),
);
x += terminalW + m.hGap;
}
}
final byKey = {for (final box in boxes) box.key: box};
final horizontals = _SegmentAllocator(m.portSpacing);
final verticals = _SegmentAllocator(m.trackStep / 3);
(double, double) gapBounds(int gap) {
if (gap <= 0) return (m.pad, contentLeft);
if (gap >= stageCount) return (stageRowRight, stageRowRight + m.hGap);
final left = byKey[stages[gap - 1].key]!;
return (left.right, stageXs[gap]);
}
// Forward edges first: a straight route keeps one horizontal run by sharing
// its y between source and target, fanned per source so two labels clear.
final forwardY = <int, double>{};
final forwardBySource = <String, List<GraphEdge>>{};
for (final edge in placed) {
if (isForward(edge)) {
forwardBySource.putIfAbsent(edge.source, () => []).add(edge);
}
}
for (final list in forwardBySource.values) {
final source = byKey[list.first.source]!;
final n = list.length;
final usable = source.height - m.portSpacing;
final spacing = n > 1
? math.min(
math.max(labelHeight + m.labelGap * 2, m.portSpacing),
usable / (n - 1),
)
: 0.0;
final first = source.y + source.height / 2 - (n - 1) / 2 * spacing;
for (var i = 0; i < n; i++) {
final target = byKey[list[i].target]!;
final desired = first + i * spacing;
forwardY[list[i].id] = horizontals.allocate(
desired,
source.right,
target.x,
desired,
desired,
math.max(spacing, m.portSpacing),
);
}
}
double portMin(GraphNodeBox node) => node.y + m.portSpacing / 2;
double portMax(GraphNodeBox node) => node.bottom - m.portSpacing / 2;
bool bottomExitOf(GraphEdge edge) =>
edge.outcome == 'error' && edge.target == failureEnd;
final routes = <EdgeRoute>[];
for (final edge in placed) {
final source = byKey[edge.source]!;
final target = byKey[edge.target]!;
final forward = isForward(edge);
final bottomExit = bottomExitOf(edge);
final topEntry = isTerminalTarget(edge.target);
final across = !topEntry && !forward;
final sourceRank = rank[edge.source]!;
final targetRank = topEntry ? stageCount : rank[edge.target]!;
final lane = forward ? 0.0 : laneY(edge);
final double fromX;
final double fromY;
if (bottomExit) {
final slot = placed
.where((c) => bottomExitOf(c) && c.source == edge.source)
.toList()
.indexWhere((c) => c.id == edge.id);
fromX = source.x + source.width / 2 + _portOffset(slot, m.portSpacing);
fromY = source.bottom;
} else if (forward) {
fromX = source.right;
fromY = forwardY[edge.id]!;
} else {
final slot = placed
.where(
(c) => c.source == edge.source && !isForward(c) && !bottomExitOf(c),
)
.toList()
.indexWhere((c) => c.id == edge.id);
fromX = source.right;
fromY = horizontals.allocate(
source.y + source.height / 2 + _portOffset(slot, m.portSpacing),
source.right,
source.right + m.hGap,
portMin(source),
portMax(source),
m.portSpacing,
);
}
final double toX;
final double toY;
if (forward) {
toX = target.x;
toY = forwardY[edge.id]!;
} else if (topEntry) {
final slot = placed
.where((c) => c.target == edge.target)
.toList()
.indexWhere((c) => c.id == edge.id);
toX = target.x + target.width / 2 + _portOffset(slot, m.trackStep);
toY = target.y;
} else {
final slot = placed
.where((c) => c.target == edge.target && !isForward(c))
.toList()
.indexWhere((c) => c.id == edge.id);
toX = target.x;
toY = horizontals.allocate(
target.y + target.height / 2 + _portOffset(slot, m.portSpacing),
target.x - m.hGap,
target.x,
portMin(target),
portMax(target),
m.portSpacing,
);
}
var trackX = 0.0;
var leadX = 0.0;
if ((topEntry && !bottomExit) || across) {
final (lo, hi) = gapBounds(sourceRank + 1);
trackX = verticals.allocate(
lo + m.trackStep,
math.min(fromY, lane),
math.max(fromY, lane),
lo + m.trackStep / 2,
hi - m.trackStep / 2,
m.trackStep,
);
}
if (across) {
final (lo, hi) = gapBounds(targetRank);
leadX = verticals.allocate(
hi - m.trackStep,
math.min(lane, toY),
math.max(lane, toY),
lo + m.trackStep / 2,
hi - m.trackStep / 2,
m.trackStep,
);
}
final from = RoutePoint(fromX, fromY);
final to = RoutePoint(toX, toY);
final points = _collapse(
bottomExit
? [from, RoutePoint(fromX, lane), RoutePoint(toX, lane), to]
: topEntry
? [
from,
RoutePoint(trackX, fromY),
RoutePoint(trackX, lane),
RoutePoint(toX, lane),
to,
]
: across
? [
from,
RoutePoint(trackX, fromY),
RoutePoint(trackX, lane),
RoutePoint(leadX, lane),
RoutePoint(leadX, toY),
to,
]
: [from, to],
);
routes.add(
EdgeRoute(
id: edge.id,
source: edge.source,
outcome: edge.outcome,
target: edge.target,
label: edge.label,
fallback: edge.fallback,
kind: forward || topEntry
? RouteKind.forward
: edge.source == edge.target
? RouteKind.selfLoop
: targetRank <= sourceRank
? RouteKind.back
: RouteKind.sameRank,
straight: points.length == 2,
sourcePort: RoutePort(
side: bottomExit ? RoutePortSide.bottom : RoutePortSide.right,
point: from,
),
targetPort: RoutePort(
side: topEntry ? RoutePortSide.top : RoutePortSide.left,
point: to,
),
points: points,
),
);
}
// Every label keeps clear of every node and earlier label; one that finds
// no spot on its own route is a misfit, and the caller grows the gaps.
final placement = placeLinearLabels(
routes: routes,
extents: {for (final edge in placed) edge.id: labelOf(edge)},
nodes: boxes,
labelGap: m.labelGap,
);
final labels = placement.labels;
final contentBottom = hasTerminal
? boxes
.where((box) => box.terminal)
.fold<double>(0, (bottom, box) => math.max(bottom, box.bottom))
: stageBottom + laneEdges.length * laneSpacing;
var height = contentBottom + m.pad;
var right = width;
for (final label in labels) {
height = math.max(height, label.bottom + m.pad);
right = math.max(right, label.right + m.pad);
}
final layout = GraphLayout(
nodes: boxes,
width: right,
height: height,
rankCount: stageCount + (hasTerminal ? 1 : 0),
ranks: {for (final box in boxes) box.key: box.rank},
);
return (
(
layout,
GraphRouting(
routes: routes,
labels: labels,
skipped: skipped,
width: right,
height: height,
),
),
placement.misfits,
);
}
/// Centred fan for the k-th port: 0, +s, -s, +2s, -2s, ...
double _portOffset(int index, double spacing) {
if (index <= 0) return 0;
final magnitude = (index + 1) ~/ 2;
return (index.isOdd ? 1 : -1) * magnitude * spacing;
}
List<RoutePoint> _collapse(List<RoutePoint> points) {
final result = <RoutePoint>[];
for (final point in points) {
if (result.isEmpty || result.last != point) result.add(point);
}
return result;
}
/// Places a run at the first position from `desired`, stepping outward, that
/// keeps `eps` from every placed run whose cross-interval overlaps.
class _SegmentAllocator {
_SegmentAllocator(this.eps);
final double eps;
final _placed = <({double position, double lo, double hi})>[];
double allocate(
double desired,
double from,
double to,
double min,
double max,
double step,
) {
final start = math.min(math.max(desired, min), math.max(min, max));
final a = math.min(from, to);
final b = math.max(from, to);
bool free(double candidate) => !_placed.any(
(run) =>
(run.position - candidate).abs() < eps && run.lo <= b && a <= run.hi,
);
for (var k = 0; k <= 512; k++) {
final candidates = k == 0
? [start]
: [start + k * step, start - k * step];
for (final candidate in candidates) {
if (candidate < min || candidate > max) continue;
if (free(candidate)) {
_placed.add((position: candidate, lo: a, hi: b));
return candidate;
}
}
}
_placed.add((position: start, lo: a, hi: b));
return start;
}
}