← ./articles-ja

React Flowのdagre layoutはvirtual rootよりconnected componentsで分ける

react-flowdagregraph-layoutdata-visualizationreact

複数の独立したグラフ領域をdagreで並べる時、virtual rootを追加したくなります。

隠しrootを1つ作り、すべてのroot nodeにつなげてlayoutする方法です。動きますが、概念的に別の領域まで同じ親の子として扱われます。その結果、平たく横長いlayoutになります。

React Flowでは、先にconnected componentを分け、componentごとにdagre layoutをかけてから横に並べるほうが安定します。

症状: すべてのsectionが同じrankに並ぶ

たとえばgraphに次があるとします。

  • startup flow
  • event handlers
  • background jobs
  • dead nodes
  • independent state-machine regions

virtual rootを入れると、dagreからはこう見えます。

__root__
  -> startup
  -> handler_a
  -> handler_b
  -> orphan

これは1つの浅い階層です。意味のあるgroupingではありません。

weakly connected componentsを探す

groupingのためだけに、edgeを無向として扱います。

type NodeLike = { id: string };
type EdgeLike = { source: string; target: string };

function findComponents(nodes: NodeLike[], edges: EdgeLike[]) {
  const neighbors = new Map<string, Set<string>>();
  nodes.forEach((node) => neighbors.set(node.id, new Set()));

  edges.forEach((edge) => {
    neighbors.get(edge.source)?.add(edge.target);
    neighbors.get(edge.target)?.add(edge.source);
  });

  const visited = new Set<string>();
  const components: string[][] = [];

  for (const node of nodes) {
    if (visited.has(node.id)) continue;

    const stack = [node.id];
    const current: string[] = [];
    visited.add(node.id);

    while (stack.length) {
      const id = stack.pop()!;
      current.push(id);

      for (const next of neighbors.get(id) ?? []) {
        if (!visited.has(next)) {
          visited.add(next);
          stack.push(next);
        }
      }
    }

    components.push(current);
  }

  return components;
}

これで独立したsectionごとにlayoutできます。

componentごとにX座標を正規化する

Dagreは絶対座標を返します。横に並べる前に、component内の中心を0に寄せます。

function normalizeX<T extends { position: { x: number; y: number } }>(nodes: T[]): T[] {
  const minX = Math.min(...nodes.map((node) => node.position.x));
  const maxX = Math.max(...nodes.map((node) => node.position.x));
  const centerX = (minX + maxX) / 2;

  return nodes.map((node) => ({
    ...node,
    position: {
      x: node.position.x - centerX,
      y: node.position.y,
    },
  }));
}

これをしないと、大きいcomponentと単一nodeのcomponentが視覚的にズレます。

sectionごとに横へ配置する

layoutと正規化の後でoffsetを足します。

const SECTION_GAP = 420;

const positioned = components.flatMap((component, index) => {
  const layouted = layoutWithDagre(component);
  const normalized = normalizeX(layouted);

  return normalized.map((node) => ({
    ...node,
    position: {
      x: node.position.x + index * SECTION_GAP,
      y: node.position.y,
    },
  }));
});

最初は固定幅で十分です。大きなgraphではcomponentのbounding boxから幅を計算します。

使わないほうがよい場合

次の場合は向きません。

  • ユーザーが手動配置し、その位置を保存したい
  • cyclic graphで別のlayout modelが必要
  • force-directed layoutが要件
  • component分離が読者に意味を持たない

このpatternは、call graph、dependency graph、state-machine、解析ツールのように、分離したsectionそのものが説明になるUIで強いです。

検証チェック

  • 各connected componentが1回だけ検出される
  • component間にedgeが残っていない
  • 大小のcomponentが中央揃えに見える
  • fitView() が全体を収める
  • 同じgraphでlayoutが再現する
  • screenshotで「平たい1列」ではなくgroupingが見える

参考