beuiCleanSankey function

BeuiSankeyData beuiCleanSankey(List<BeuiSankeyNode> nodes, List<BeuiSankeyLink> links)

Cleans the graph with the pinned source's iterative depth-first cycle rule.

Implementation

BeuiSankeyData beuiCleanSankey(
  List<BeuiSankeyNode> nodes,
  List<BeuiSankeyLink> links,
) {
  final byId = <String, BeuiSankeyNode>{};
  for (final n in nodes) {
    byId.putIfAbsent(n.id, () => n);
  }
  final merged = <String, BeuiSankeyLink>{};
  final invalid = <BeuiSankeyLink>[];
  for (final l in links) {
    if (!byId.containsKey(l.source) ||
        !byId.containsKey(l.target) ||
        l.source == l.target ||
        !l.value.isFinite ||
        l.value <= 0) {
      invalid.add(l);
      continue;
    }
    final old = merged[l.effectiveId];
    if (old == null) {
      merged[l.effectiveId] = BeuiSankeyLink(
        id: l.effectiveId,
        source: l.source,
        target: l.target,
        value: l.value,
      );
    } else if (l.id == null &&
        old.source == l.source &&
        old.target == l.target) {
      merged[l.effectiveId] = BeuiSankeyLink(
        id: old.id,
        source: old.source,
        target: old.target,
        value: old.value + l.value,
      );
    } else {
      invalid.add(l);
    }
  }
  final outgoing = <String, List<BeuiSankeyLink>>{};
  for (final l in merged.values) {
    (outgoing[l.source] ??= []).add(l);
  }
  final state = <String, bool>{};
  final back = <BeuiSankeyLink>{};
  for (final root in byId.values) {
    if (state.containsKey(root.id)) continue;
    final stack = <({String id, int next})>[(id: root.id, next: 0)];
    state[root.id] = false;
    while (stack.isNotEmpty) {
      final f = stack.last;
      final edges = outgoing[f.id] ?? [];
      if (f.next >= edges.length) {
        state[f.id] = true;
        stack.removeLast();
        continue;
      }
      stack[stack.length - 1] = (id: f.id, next: f.next + 1);
      final l = edges[f.next];
      if (state[l.target] == false) {
        back.add(l);
      } else if (!state.containsKey(l.target)) {
        state[l.target] = false;
        stack.add((id: l.target, next: 0));
      }
    }
  }
  return BeuiSankeyData(
    nodes: List.unmodifiable(byId.values),
    links: List.unmodifiable(merged.values.where((l) => !back.contains(l))),
    invalid: List.unmodifiable(invalid),
    cycles: List.unmodifiable(merged.values.where(back.contains)),
  );
}