フローチャートの配置を、実測スコアで選ぶ

自動レイアウトの結果に「もう少しだけ」と思ったことがある人は多いはずです。線が1本だけ箱をまたいでいる、2本の線が重なって1本に見える。MermaidLayoutFinisherの「おまかせ最適化」は、この「もう少し」を機械に任せるための機能です。ただし、任せ方には条件を付けました。良くなったときだけ適用し、良くならなければ図を動かさない。この記事では、その条件を成り立たせるために、配置の良し悪しをどう測り、候補をどう作り、どこで手を止めるかを紹介します。

何を「悪い配置」と呼ぶか

最初に決めたのは、測る対象を画面に描かれる線そのものにすることでした。自動レイアウトのライブラリであるdagreは、ノードの座標と一緒に線の経路も返してくれます。しかしこのアプリでは、線は毎回ノードの箱から計算し直します。手でノードを動かしても線が必ずつながるようにするための設計で、だからこそ、評価もその「実際に描かれるルート」に対して行わないと、画面と評価が食い違います。

測る指標は次のとおりです。ノード同士の重なり(8px未満の接近を含む)、線がノードを貫通している数、線同士の交差、ほぼ平行な線が1.5px以内で並走している長さ、曲がり角の数、線の総延長、そして図の面積と縦横比です。加えて、エッジラベルがノードに食い込んでいないか、サブグラフの枠が重なったり部外者のノードを抱き込んだりしていないか、流れを遡るはずのない線が逆行していないかも数えます。

2つのスコアと、硬い制約

指標は1つの数に畳みます。ただし、畳み方は2種類あります。

1つは探索が最小化するスコアで、モードごとに重みが違います。標準の重みでは、線のノード貫通が20、交差が12、並走重複が0.02、総延長が0.004、曲がり角が0.3、面積が0.02です。コンパクトでは総延長と面積の重みを上げ、ワイドでは16:9からのずれに大きな重みを掛けます。もう1つは改善量の表示に使う採点用のスコアで、こちらはモードによらず固定です。

// 探索用スコアのモード別重み（抜粋）
const MODE_WEIGHTS = {
  balanced: { overlap: 20, crossing: 12, corridor: 0.02, length: 0.004, bend: 0.3, area: 0.02, aspect: 0 },
  compact:  { overlap: 20, crossing: 12, corridor: 0.02, length: 0.02,  bend: 0.3, area: 0.3,  aspect: 0 },
  wide:     { overlap: 20, crossing: 12, corridor: 0.02, length: 0.004, bend: 0.3, area: 0.02, aspect: 240 },
};

ここで1つ迷いました。ノード同士の重なりのような致命的な欠陥も、大きな重みを付けて同じスコアに畳めば済むのではないか。実際、採点用のスコアではノードの重なりに10,000、サブグラフ枠の違反に5,000、ラベルの食い込みに2,000、逆行に1,500という大きな重みを付けています。

それでも、探索ではこれらを重みで扱いませんでした。人が一目で拒否する欠陥は、他の指標がどれだけ改善しても釣り合わないからです。実装では、ノードの重なり、ラベルの食い込み、枠の違反、逆行の4つを硬い制約として別枠で数え、探索中の一手がこの4つのどれかを現状より増やすなら、スコアに関係なくその手を捨てます。基準は「ゼロ」ではなく「現状より増やさない」です。入力の時点で重なっている図を、まず直せない状態にしないための線引きです。

候補は広く作り、磨くのは2つだけ

おまかせ最適化は、1つの配置を少しずつ直すのではなく、まず複数の候補を作ります。dagreのランク付けアルゴリズムを変えたもの、ノード間隔を広げたもの、線が混み合う段だけ間隔を広げる混雑ベースの可変間隔を掛けたもの、そして現状の配置そのものです。ノード数が20以上の図では、この7種類が出発点になります。

候補は、ノードの重なりを修復し、ラベルの分だけ段を広げてから、干渉スコアで順位を付けます。ここで精緻化に進むのは上位2つだけです。全候補を磨くと時間予算に収まらないためで、既定の予算は2.5秒、そのうち350ミリ秒は後述の戻り線の処理に取っておきます。

精緻化は素朴な山登り法です。ノードを縦横に16、32、64、96px動かしてみて、スコアが厳密に良くなり、硬い制約を増やさない手だけを採ります。これを最大3周し、同じ段にあるノード同士の入れ替えも試します。処理は8ノードごとにイベントループへ制御を返すので、探索中も画面は固まりません。

戻り線は外周へ逃がす

フローチャートには、承認が却下されて差し戻しへ戻る、というような、流れを遡る線があります。この線をそのまま最短で引くと、図の中央を横切って多くの線と交差します。

そこで、精緻化のあとに、遡る線のうち2段以上をまたぐものを最大8本まで取り出し、図の左右(横向きの図なら上下)のどちらかから出入りするように接続面を割り当ててみます。左と右の両方を実際に描いて測り、硬い制約を増やさず、スコアが厳密に良くなる側だけを採用します。手で経路を調整済みの線は対象外です。人が決めた経路を機械が上書きするわけにはいきません。

小さい図には触りすぎない

もう1つ、実装してから足した規則があります。ノードが20個未満の図では、面積と総延長の重みを0にする、というものです。

理由は単純で、小さい図ではdagreの結果がほぼ正解だからです。そこに面積を詰める圧力を掛けると、正しかった配置がわずかに崩れて、改善どころか改悪になります。小さい図で行うのは、貫通や重なりやラベルの食い込みといった欠陥の修理だけです。欠陥がなければ、何も動かさずに「現在の配置が最良でした」と返します。

最後の関門も同じ思想です。おまかせと「今の配置を整える」の2つのモードは、探索用スコアで厳密に勝ち、かつ採点用スコアで後退していないときだけ結果を適用します。どちらか一方でも満たさなければ、図は1pxも動きません。トーストに出る改善量も、この採点用スコアと同じ計測値です。

「良くなったときだけ」を守るための構造

振り返ると、この機能の設計判断はどれも「良くなったときだけ適用する」という1つの約束から出ています。実際に描かれる線で測るのは、画面と評価をずらさないため。硬い制約を重みにしないのは、致命的な欠陥をスコアで買い戻させないため。小さい図に触らないのは、正しい配置を崩さないため。そして最後の関門は、その約束を最終的に保証するためです。

自動化の価値は、何でもやることではなく、やらないべきときにやらないことにもあります。次にレイアウトの機能を足すときも、この約束を破らない範囲で足すことになるはずです。書き出した図をPowerPointで編集可能な図形として扱う方法は、ガイド「Mermaidのフローチャートを、PowerPointで編集できる図形として貼る」で紹介しています。