作成した flexflowflight✈ の紹介 (7/18 時点 α版)
mermaid.js や PlantUML のように、テキストから図を作成するツール flexflowflight✈1 を作成しました。
【デモ】
【CodePenのサンプル】(※PCで確認ください)
See the Pen Untitled by j5c8k6m8 (@j5c8k6m8) on CodePen.
【github】
flexflowflight✈ は、 CSS Flexbox と tomlのテーブル記法 に触発された DSL(ドメイン固有言語) を用います。ノードの相対的な配置をテキストで指定して、綺麗なフローチャートが作成 できます。
mermaid.js に比べて、 フローチャートに特化 して、 要素の配置を制御できる 点が特徴です。
上記の CodePen で示したような <code class="flexflowflight">を変換するCDN の他、 TypeScript や javascript で文字列やオブジェクトからSVGに変換するAPI も使えます。是非利用してみてください。
flexflowflight✈ は、 Deno で作成中の α版 となります。
npm にはまだ登録していないこと、IFに破壊的な変更を行う可能性があることに注意してください。
はじめに
本記事は、 Qiita Engineer Festa の、テーマ アルゴリズム強化月間 - 楽しいアルゴリズムの世界を紹介しよう - への投稿記事です。
今回作成した、flexflowflight✈ は、
CSS Flexbox で配置されたノードに対して、コネクタを『いい感じの経路で描画』する
というアイディアがベースとなっています。
筆者は情報工学には疎いのですが、 経路の決定問題は、適したアルゴリズムを考えるのが比較的難しい（＝面白い）問題 と捉えています。
実際、今回作成した flexflowflight✈ についても、 アルゴリズムの具体化が進まず、アイディア止まり となっていました。
今回、提示するアルゴリズムは、それ自体に革新性などがあるわけではなく、前提となる CSS Flexbox の特性を理解し、モデル化し、 アルゴリズムを徐々に改善した作業の結果 です。
そのため、もっと『いい感じの経路で描画』するアルゴリズムや、同じ結果で計算量の少ないのアルゴリズムもあるかもしれません。
flexflowflight✈ では、アルゴリズムを含む関数をAPIに渡すことで、 独自のアルゴリズムで算出した結果を描画することも可能 です。
興味のある方は、自身でアルゴリズムを作成し、 flexflowflight✈ での描画を試してください。 アルゴリズムのパターンを追加する PR も大歓迎 しています。
さて、閑話休題します。flexflowflight✈ を作成するにあたり、 アルゴリズムの考慮が特に必要な問題は、３点ありました。
１点目が、経路決定の問題 です。経路の決定問題は、アルゴリズムに取り組む前に「CSS Flexbox 相当のデータモデルに、どのように経路のデータモデルを追加するか？」 という、データモデルの設計もする必要がありました。
２点目が、配置の問題 です。当初は CSS Flexbox の仕組みをそのまま、つまり、一部機能を実装するだけで、『いい感じの経路で描画』が実現可能と考えていました。
しかし、コネクタの描画を検討するにあたり、CSS Flexbox の機能だけではなく、 独自の機能を入れる必要がある と考えました。具体的には、要素の位置あわせに、コンテナ内だけではなく、 隣接コンテナを考慮した位置合わせ のアルゴリズムが必要でした。
筆者にとっては、配置の問題は、経路決定の問題と同じくらい、適切なアルゴリズムを考えるのが難しい問題だと感じました。そのため、 flexflowflight✈ では、 「経路決定」と「配置」の問題を完全に分離 した上で、両方の アルゴリズムを入れ換え可能 な構成にしました。配置のアルゴリズムも、入れ換え可能な構成のもと、両者のアルゴリズムを改善しました。
7/18 時点では、Qiita Engineer Festa に間に合わせて投稿するために、 隣接コンテナを考慮した位置合わせは未実装(開発中) の状態となります。
３点目が、DSL(ドメイン固有言語) のパース 、つまり、テキスト（文字列）から構造化されたデータ（AST）への変換です。
こちらは、アルゴリズム自体に新規性は一切ありません。しかし、短期間での実装が求められた背景もあり、 シンプル、かつ、拡張性が高くなるように設計 しました。
本記事は、上記３点のアルゴリズムの考慮が必要な問題に、どのように対応していったかを、前提となる知識の紹介から、設計方針の策定、実装を順番に紹介します。そのため、 flexflowflight✈ の 核となる仕組みや思想が理解できる かと思います。
一方で、 flexflowflight✈ の使い方、ユースケース、仕様の詳細は割愛します。また、バージョンアップに伴う記事の更新等も予定していないため、 flexflowflight✈ 自体の情報は、 github のリボジトリのドキュメントを参照 してください。
flexflowflight✈ は Deno 環境で、 TypeScript を使用して実装しています。また、 ライブラリは、一切使用してません 。
実装詳細を理解するためには、 TypeScript の基本知識が必要となりますが、 Class や ジェネリクスを使用せずに、 比較的基本的な一部の機能2 のみを使用 しています。そのため、typescript の基本的なデータ構造と、条件分岐・繰り返しの構文、関数呼び出し を理解すれば、アルゴリズムを読み解くことができると思います。
綺麗に実装しているとは言えませんが 記事中の実装には、 DSL のパース、AST の最適化、座標変換、経路導出、配置決定、SVG出力 などのアルゴリズムが含まれます。
本記事は、flexflowflight✈ を作成するまでの全てを対象としていますが、興味のある部分だけでも読んでいただき、アルゴリズムに対する興味や、新しいアイディアに繋がれば幸いです。
経路と配置に関わる前提と設計方針
CSS Flexboxについて
flexflowflight✈ は、 CSS Flexbox に触発された 独自のDSL(ドメイン固有言語) を利用します。
flexflowflight✈ を使用するために、 CSS Flexbox の知識は必要ありません が、CSS Flexbox を知っている方が、その 設計背景などが分かりやすい でしょう。
CSS Flexbox は、 親要素(flex container) で軸の向きを設定し、子要素（flex item）に対して、軸に沿った位置合わせが実現できる機能です。
要素ネストさせる、すなわち 子要素(flex item) 自体を 親要素(flex container) にすることで、2次元の配置も可能です。
具体例を見てみましょう。
See the Pen Untitled by j5c8k6m8 (@j5c8k6m8) on CodePen.
この HTMLは、Flex box を利用して記載しています。簡単に、整った配置が実現できていることが分かるでしょう。
構造が分かりやすいように、主軸が右方向の親要素(flex container)を赤で、主軸がした方向の親要素(flex container)を青で示します。
See the Pen Untitled by j5c8k6m8 (@j5c8k6m8) on CodePen.
CSS Flexbox では、 主軸の向きを変えるためには、親要素(flex container) の追加が必要 です。
これは、CSS Flexbox の制約です。この制約が問題になる場合、CSSにおいては、 CSS Grid Layout を用いる必要があります。
一方で、この制約は 構造を伴うデータの描画 においては適切3 であると筆者は考えています。
以降、本記事では 『階層構造で親要素が子要素の主軸の向きを決めるレイアウト』
を、 Flexbox指向 と定義して記載します。
また、ここで示した、 CSS Flexbox の親要素を コンテナ 、親要素と子要素の両方を含む要素を示すものを、 ノード 、末尾の子要素（葉）を セル として記載します。
コネクタをどう扱うか
flexflowflight✈ では、図が複雑になっても、コネクタの接続元と接続先が分かるように、 コネクタが重ならないように描画 4 します。
では、このコネクタの情報は、どのように持てばいいでしょうか？
筆者は、以下の2つの方針を検討しました。
- コネクタの情報を主体 で考える。コネクタから作られる 分割されたエリアの中に、ノードの階層構造 を持つ。
- ノードの階層構造を主体 で考える。 ノードの階層構造の中に、分割されたコネクタ の情報を持つ。
ノードの配置を意識しない、 mermaid.js などでは、 ノード間の(暗黙的なものを含めた)関連で配置が決まる でしょう。当初は、この延長線上で、関連（コネクタ）による配置を決めてから、ノードの配置を行う、上記１番目の方針での実現を考えてました。
しかし、 ノードの階層構造を分断すると、分断されたノード間の位置合わせが難しい5 という問題が発生します。
ノードの配置を明示的にユーザが指定 する flexflowflight✈ では、 ノードの階層構造が主体であり、コネクタの情報は副次的 であると考え、 コネクタを分割する という、２番目の方針の方が、実現が容易であり、また、「CSS flexbox指向」に合っていたため、この２番目での方針を採用しました。
それでは、 コネクタをどう分割すればよい でしょうか？
以下に、概要図を示します。
まずは、簡単に用語の定義を説明します。
| 要素 | 説明 |
|---|---|
| ノード | Flex-itemに相当する、 親要素/子要素を含む要素 |
| コンテナ | Flex-containerに相当する 親要素(子要素を持つ要素) |
| セル | 末尾の子要素 |
| ボックス | コネクタの始点/終点となりうる ノード |
| エッジ | コネクタの始点/終点となりうる ボックスの辺 |
| ゲート | コネクタの始点/終点となりうる ボックスの辺毎の番号 |
| アベニュー(通り) | コンテナ内の 余白に対する番号 |
| レーン | アベニュー内毎の番号 |
| ロード | コネクタの通り道。 レーンと同じ単位 |
コネクタは、ゲートから、ノードの隙間、つまり、ロードを通ります。各ロードは 常に、ノードの辺と並行に存在 します。同じノード間を複数のコネクタが通る可能性があるため、 同じノード間をレーン分け して、複数のロードが作れるようにします。なお、ロードはコンテナ内に存在します。親のノードや、 別階層のコンテナにコネクタを繋げる ためには、ロードを曲がって、 別の階層のロードに移らなければならない ことに注意しましょう。
この考え方は、比較的実際のシーンにも近いでしょう。ノードを家と考えると、これは、 家から家への行き方を決める ことになります。家を出ると、常に玄関と垂直に道があります。もちろん、玄関の前に道がある、つまりT字の道があるかもしれません。それでも、その交点を考えると、一度、玄関と垂直な道を経由すると考えることができます。
また、 道は常に梯子のような形 です。梯子の足を乗せる部分には番号が触れます。また、右の辺か左の辺かの区別もあるでしょう。これは、 何番通りか、もしくは、東通か西通など でイメージできるでしょう。
ノードの 階層関係は、道路と高速道路 を考えましょう。ただし、道路と高速道路は立体に交わりません。あなたの家は 高速道路に囲まれている と考えられます。もちろん、突っ切ることもできますが、その際には、先ほどの家の前がT字になっている時と同様に、 高速道路を一度経由する必要 があります。
つまり、高速道路をまたいだ家にいくには、横切るとしても、高速道路を通ります。これは、横切るにしても高速道路には料金所があると考えられます。
更に、道は直線です。環状に繋がることもなく、曲がるときには必ず別の道に入る必要があります。また、同一方向に道を変える、つまり、レーンだけを変えることは、できないものとします。跨ぐ（横切る）ときも、高速道路の例のように、一度別方向の道に入ったと考えます。すると、どうでしょうか。このモデルであれば、 経路を、辿る道路だけで一意に表現できる ことが分かるでしょう。
『A1通りから、西三条通りに入り、b3高速にのり、x地方の北三条通りの接続で降り、d4通り沿いの、東七条と東八条通りの間』
という具合です。どっちの方向に曲がるかは指定しなくても、その後に通る道だけ知っていれば目的地までの道は確定します。
さて、 flexflowflight✈ に戻ります。経路の決定問題は、まさに、このような、ルートを決めることになります。
また、面白いことに、 flexbox指向 は、コンテナ内での配置に流動性があります。また、先ほど決めた経路には、交通量（コネクタの数）に従ったレーン必要です。配置の問題は、経路の問題で決まったレーン数を前提として、どのように町を作るのかという問題となります。
これで、経路と配置の問題のイメージは十分でしょう。実装の章では、このような構成、経路、配置モデルの、を、 flexflowflight✈ としては、どのようなデータの構造で持っているかを示します。
さて、描画に関わる検討は一旦ここまでとします。次に、DSL(ドメイン固有言語)について簡単に検討しましょう。
DSL(ドメイン固有言語) に関わる前提と設計方針
さて、先ほどまでの話は、データをどのように、 いい感じに出力 させるかの話でした。
DSL(ドメイン固有言語) については逆の話、つまり、 いい感じに入力 させるための話となります。
話題が全く変わりますので、頭を切り替えて読んでいただければと思います。
TOML のテーブル記法について
CSS flexbox は、HTML で使われます。HTML は木構造、つまり、階層構造です。
Flexbox指向は、 『階層構造で親要素が子要素の主軸の向きを決めるレイアウト』 であるため、そのための記法(データ記述言語)は、階層構造を表しやすいものがよいでしょう。
世の中には、階層構造を表すことがデータ記述言語はたくさんあります。
代表的なものは、 json と yaml でしょう。これらの使用はケースバイケースと考えますが、 人が書くデータとして、 json の末尾カンマ問題も、 yaml のインデント依存も、筆者は 宗教上の理由により許容できない 好んでいません。
これらの問題のひとつの解決法が TOMLのテーブル記法 だと筆者は考えています。
TOMLは、読みやすい設定ファイルとして、最小限の構成を目指したデータ記述言語です。
ここでは、JSONから、テーブル表記への変換例を引用して紹介します。
json の、 {"hoge": {"key1": "val1", "key2": "val2"}} は、 toml の table表記では以下のように記載します。
[hoge]
key1 = "val1"
key2 = "val2"
[hoge] と書かれた行がテーブル名、つまり、連想配列のキーを表します。[hoge]
以降の行の記述は、この連想配列内に対する記述となります。ネストした構造を表しているのにも関わらず、 json と比較して、 閉じ括弧とカンマ という無駄 が無いのが分かるでしょう。また、 yaml のように、インデントに依存していないことも分かります。
深いネストも、 . を利用して記載できます。
[x.hoge]
desc = "toml example"
[x.hoge.sub1]
key1 = "val1"
[x.hoge.sub2]
key2 = "val2"
これは、 json では、 {"x": {"hoge": { "desc": "toml example", "sub1": {"key1": "val1"}, "sub2": { "key2": "val2"}}}} に相当します。上位の連想配列のキーを省略できると言う点にも注意して下さい。これは、テーブル記法が 後続の行のスコープを決める ともいえるでしょう。
筆者は、 toml のテーブルの表記は、 行指向であり、diff が分かりやすいなどの利点があり、人が書くプレーンテキストの形式としては優れていると考えてます。
また、マークダウンのヘッダなどとも書き方が似ていると感じています6。
そのため、マークダウンや mermaid.js に慣れている flexflowflight✈ の想定ユーザとも相性がいいのではないか？と考えています。
それでは実際の flexflowflight✈ の DSL の設計の話に移ります。
DSL(ドメイン固有言語)の設計方針
さて、toml は、設定ファイルのためのミニマル(最低限）な言語です。flexflowflight✈ で直感的な既述を可能にするために、toml のテーブル記法の概念を取り入れた DSL を考えます。
元々の CSS flexbox から触発されたものであるため、 HTML の <img src="test.png" height="20" width="40" alt="test" > のような、
開括弧 名前 属性名=属性値... 閉括弧 という形式は、属性の追加による拡張が容易なことと、属性名でカテゴライズされることから、筆者は好んでいます。ただし、閉じタグは記載したくないため、コンテナ要素(子要素を保持する要素) は、 toml のテーブル記法のように、後続の行のスコープを変更できるものとします。
イメージとしては、 マークダウンと、htmlとtomlを足して、３で割ったもの を目指します。つまり、書き手としてはマークダウン程度の感覚で記載ができ、HTML のように拡張性があり、toml のように後続のスコープを変更してシンプルに記載ができます。
また、toml よりも複雑な構造を記載することが多いと思うので、テーブル記法に . はじまりによる、相対的な記述も可能とします。
また、 mermaid.js のように、 コネクタは - で記載できるといいでしょう。また、flexflowflight✈ では、主軸と交差軸という二方向の概念があるため、 - で主軸方向を、 | で交差軸方向のコネクタを表すものとします。コメントは、 # 始まりの末尾行までとします。
また、使いやすさを考えると、セレクタ(コネクタのための別名での指定) も必要でしょう。 & と $ はセレクタ用の記号として予約します。
パースを簡単にするために、識別子の表記ルールを厳しくします。いわゆる、無印の識別子や値は 半角英数字アンダースコアのみ(先頭数字も許容)とし、これら以外の文字を識別子や値として使用したい場合は、ダブルクォーテーションかシングルクォーテーションで囲むものとします。
では、代表的な記載の一覧を示しましょう。
| 要素 | フローチャート | FlexBox | DSLの記法 |
|---|---|---|---|
| ノード | 個別のノード | flex-item | (ノード名) |
| ボックス | 表示しない (配置指定のみ) |
flex-container | [ボックス名] |
| リンク | コネクタ | - | {接続元-接続先} |
| グループ | グループ (配置指定含む) |
flex-container | [[グループ名]] |
サンプルは、 flexflowflight✈ の動作と合わせて以下のコードペンを参照して下さい。
flexflowflight✈ は、まだ α版 ですが、DSL の基礎としては大きく変えずに、HTML のように属性の追加で機能追加でき、かつ、ユーザが書きやすい DSL が設計できたのではないでしょうか？
では、設計方針の策定はここまでとして、実装に入ります。
実装
では、以降は実装を交えて flexflowflight✈ の説明をしていきます。
ここからは、プログラミングと設計の話となります。
全体構成
flexflowflight✈ で行う処理は、 究極的にはテキスト変換 です。DSL もしくは json 文字列から、SVG列へ変換します。
ただし、その 変換内容は比較的複雑 です。DSL を扱う言語では、まず パーサーによる変換を行い、テキストから AST(abstract syntax tree) 抽象構文木 と呼ばれる構造化されたデータ構造へと変換するのが一般的でしょう。 また、ASTに対して、複数回の最適化が行われることも一般的でしょう。
flexflowflight✈ も同様に、入力されたテキスト(fl3、json) から、まず AST を作成し、各種最適化を行った後、テキストを出力します。
経路や配置の決定は、最適化のフェーズで行われます。flexflowflight✈ では、経路や配置のアルゴリズムを プラガブル(交換、作成可能) にするため、各ASTの段階毎のデータ構造をシリアライズ可能な形式で定義します。
上手は、flexflowflight✈ で描画していますが、7/18 時点のα版では描画に時間がかかり、コネクタが多いと無駄にスペースを取ってしまうなど、まだ改善点が多くある事が分かると思います。
flexflowflight✈ はある程度複雑かつノード数が多いフロー図をかける事を目指しているため、上手のようなフローをノードの配置だけ指定して、違和感のないフロー図となる様に改善していきます。
このような構成にすることで、 flexflowflight✈ がデータ変換のみを行う複数のアルゴリズムのみから構成されることが分かると思います。
DSN(.fl3) の変換 [parseFl3xL1.ts]
設計方針で示した文法のパーサーを作成します。パーサーを作成する際は、EBNF などで文法を定義することが多いかと思いますが、 期間がないため これは省略します。
今回は、要素ごとのパースを、関数で分け、状態を持ったループを用いて、力業で実装します。
詳細は、以下のGitHUBから実際のコードを参照してください。属性のパースは含まれていませんが、 1Kstep 以下の比較的単純なコードであることがわかるでしょう。
ツリー型からグラフ型への変換 [parseL1xL2.ts]
入力された DSL を階層構造である、ツリー構造に変換しました。
ただし、Lv1 の AST は、各ノードにIDが振られていません。これは、コネクタの構造を示すのには扱いにくいことに加え、シリアライズしにくい形式でしょう。
今後の処理を行いやすくするために、各ノードに ID を振り、各ノードの 親(先祖)/子/兄弟 の情報を持たせる構造に変換します。
また、Lv1 の AST はユーザが入力しやすい形式、つまり、デフォルト値などが省略されている形式を許容しています。
プログラムで扱う際には、省略されていない方が扱いやすいため、デフォルト値なども合わせて設定します。
経路決定(初期バージョン) [parseL2xL3.ts / calcRouteV1.ts]
さて、経路決定のアルゴリズムの準備が整いました。
まずは一番簡単な経路決定アルゴリズムを考えます。
木構造であるデータ構造を利用し、
- 共通の親コンテナを探す
- 親側を優先して共通親コンテナ迄のルートを探す
- 共通親コンテナの出方のパターンごとのつなぎ方を行う
というアルゴリズムを実装します。
なお、複数パターンが存在するため、折り返し数などからスコアリングを行い、一番スコアのいいルートを選びます。
import { NodeId, Direct, getMappingCompassFull, isSameAxisDirect, getAnotherAxisByDirect, getReverse } from "./astC0.ts"
import { Node, Link } from "./astL2.ts"
import { LinkRoute, Road } from "./astL3.ts"
// FILE ERROR ID = '21'
// deno-lint-ignore require-await
export const calcRoute = async (nodes: Node[], links: Link[]): Promise<LinkRoute[]> => {
// FUNCTION ERROR ID = '01'
const linkRoutes: LinkRoute[] = []
links.forEach(link => {
const fromNodeId = link.box[0];
const toNodeId = link.box[1];
const fromNode = nodes[fromNodeId];
const toNode = nodes[toNodeId];
if (!fromNode) {
throw new Error(`[E210101] asgR1 is invalid.`);
}
if (!toNode) {
throw new Error(`[E210102] asgR1 is invalid.`);
}
if (fromNode.parents.includes(toNodeId)) {
throw new Error(`[E210103] between parents link is invalid.`);
}
if (toNode.parents.includes(fromNodeId)) {
throw new Error(`[E210104] between parents link is invalid.`);
}
const fromParentsR = [...fromNode.parents].reverse();
const toParentsR = [...toNode.parents].reverse();
let fromCommonParentIndex = -1;
let toCommonParentIndex = -1;
for (let i = 0; i < fromParentsR.length; i++) {
toCommonParentIndex = toParentsR.indexOf(fromParentsR[i]);
if (toCommonParentIndex !== -1) {
fromCommonParentIndex = i;
break;
}
}
// fromNode and toNode are not rootNode.
if (fromCommonParentIndex == -1) {
throw new Error(`[E210105] asgR1 is invalid.`);
}
const fromRoutes: [Road[] | null, Road[] | null, Road[] | null, Road[] | null] = [null, null, null, null];
const toRoutes: [Road[] | null, Road[] | null, Road[] | null, Road[] | null] = [null, null, null, null];
getRoutes(fromNode, link.edge[0], fromCommonParentIndex, [], fromRoutes, [0, 1, 2, 3], nodes, 1);
getRoutes(toNode, link.edge[1], toCommonParentIndex, [], toRoutes, [2, 3, 0, 1], nodes, 1);
const route = getBestRoute(fromRoutes, toRoutes, fromNodeId, toNodeId);
linkRoutes.push({
linkId: link.linkId,
route: route,
});
});
return linkRoutes;
}
const getRoutes = (node: Node, direct: Direct, parentIndex: number, currentRoute: Road[], routes: [Road[] | null, Road[] | null, Road[] | null, Road[] | null], directPriority: [Direct, Direct, Direct, Direct], nodeMap: Node[], callNum: number): void => {
// FUNCTION ERROR ID = '02'
// Avoid infinite loops.
if (callNum > 1000) {
throw new Error(`[E210201] nest too deep.`);
}
callNum++;
// TODO refactor reference v2 getRoad
let targetIndex: number;
if (node.bnParents[direct] - 1 >= parentIndex) {
targetIndex = parentIndex;
} else {
targetIndex = node.bnParents[direct] - 1;
}
const targetNodeId = [...node.parents].reverse()[targetIndex];
if (!targetNodeId == null) {
throw new Error(`[E210202] asgR1 is invalid.`);
}
const targetNode = nodeMap[targetNodeId];
if (!targetNode) {
throw new Error(`[E210203] asgR1 is invalid.`);
}
if (targetNode.type !== 'Group' && targetNode.type !== 'Unit') {
throw new Error(`[E030204] asgR1 is invalid.`);
}
const railDirect = getMappingCompassFull(node.compassSelf, targetNode.compassItems)[direct];
const siblingIndex = targetNode.children.indexOf(targetIndex > 0 ? [...node.parents].reverse()[targetIndex - 1] : node.nodeId);
let road: Road;
if (railDirect === 0) {
road = {
containerId: targetNodeId,
axis: 0,
avenue: siblingIndex + 1,
}
} else if (railDirect === 1) {
road = {
containerId: targetNodeId,
axis: 1,
avenue: 1,
}
} else if (railDirect === 2) {
road = {
containerId: targetNodeId,
axis: 0,
avenue: siblingIndex,
}
} else if (railDirect === 3) {
road = {
containerId: targetNodeId,
axis: 1,
avenue: 0,
}
} else {
const _: never = railDirect;
return _;
}
currentRoute = currentRoute.concat(road);
if (node.bnParents[direct] - 1 >= parentIndex) {
const lastRoutes = routes[railDirect];
if (lastRoutes == null || lastRoutes.length > currentRoute.length) {
routes[railDirect] = currentRoute;
}
return;
} else {
const targetParentNodeId = targetNode.parents[targetNode.parents.length - 1];
const targetParentNode = nodeMap[targetParentNodeId];
if (!targetParentNode) {
throw new Error(`[E210207] asgR1 is invalid.`);
}
if (targetParentNode.type !== 'Group' && targetParentNode.type !== 'Unit') {
throw new Error(`[E210208] asgR1 is invalid.`);
}
const nextMappingCompassFull = getMappingCompassFull(targetNode.compassItems, targetParentNode.compassItems);
directPriority.forEach(d => {
if (!isSameAxisDirect(d, railDirect)) {
// recursive call
getRoutes(targetNode, nextMappingCompassFull[d], parentIndex - targetIndex - 1, currentRoute, routes, directPriority, nodeMap, callNum + 1);
}
});
}
}
const getBestRoute = (fromRoutes: [Road[] | null, Road[] | null, Road[] | null, Road[] | null], toRoutes: [Road[] | null, Road[] | null, Road[] | null, Road[] | null], fromLinkNodeId: NodeId, toLinkNodeId: NodeId): Road[] => {
// FUNCTION ERROR ID = '03'
const allDirect: Direct[] = [0, 1, 2, 3];
let ret: Road[] | null = null;
let retScore = Number.MAX_SAFE_INTEGER;
allDirect.forEach(i => {
const fromRoute = fromRoutes[i];
allDirect.forEach(j => {
const toRoute = toRoutes[j];
if (fromRoute == null) {
return;
}
if (toRoute == null) {
return;
}
const fromLastRoute = fromRoute[fromRoute.length - 1];
const toLastRoute = toRoute[toRoute.length - 1];
if (i === j) {
if (fromLastRoute.avenue === toLastRoute.avenue) {
const tmpScore = (fromRoute.length + toRoute.length - 1) * 10 + 4;
if (tmpScore < retScore) {
retScore = tmpScore;
ret = fromRoute.concat([...toRoute].slice(0, -1).reverse());
}
} else {
const tmpScore = (fromRoute.length + toRoute.length + 1) * 10 + 6;
if (tmpScore < retScore) {
retScore = tmpScore;
ret = fromRoute.concat({
containerId: fromLastRoute.containerId,
axis: getAnotherAxisByDirect(i),
avenue: 0,
}).concat([...toRoute].reverse());
}
}
} else {
if (i === getReverse(j)) {
if (fromLastRoute.avenue === toLastRoute.avenue) {
const tmpScore = (fromRoute.length + toRoute.length - 1) * 10;
if (tmpScore < retScore) {
retScore = tmpScore;
ret = fromRoute.concat([...toRoute].slice(0, -1).reverse());
}
} else {
const fromSecondNodeId = fromRoute.length === 1 ? fromLinkNodeId : fromRoute[fromRoute.length - 2].containerId;
const toSecondNodeId = toRoute.length === 1 ? toLinkNodeId : toRoute[toRoute.length - 2].containerId;
const addPoint = ((i < j && fromSecondNodeId < toSecondNodeId) || (i > j && fromSecondNodeId > toSecondNodeId)) ? 2 : 8;
const tmpScore = (fromRoute.length + toRoute.length + 1) * 10 + addPoint;
if (tmpScore < retScore) {
retScore = tmpScore;
ret = fromRoute.concat({
containerId: fromLastRoute.containerId,
axis: getAnotherAxisByDirect(i),
avenue: 0,
}).concat([...toRoute].reverse());
}
}
} else {
const tmpScore = (fromRoute.length + toRoute.length - 1) * 10 + 5;
if (tmpScore < retScore) {
retScore = tmpScore;
ret = fromRoute.concat([...toRoute].reverse());
}
}
}
});
});
if (!ret) {
throw new Error(`[E210301] asgR1 is invalid.`);
}
return ret;
}
レール情報変換(アイテム作成) [parseL3xL4.ts]
ルートを出したのちは、位置決定に移りますが、その前に、扱いやすいデータ構造に変換します。
ノード と、経路を現す ロード の両方を、アイテムというデータで表します。
アイテム位置決定(初期バージョン) [parseL4xL5.ts / calcLocaV1.ts]
それでは、アイテムの配置を行います。
初期バージョンとしては、特に最適化等は考えません。
アイテムのサイズは子要素により、親要素のサイズが確定するため、深さ優先探索で、
- サイズの決定
- 配置の決定
を順に行います。
import { ItemId, Direct, Size, getReverse, getCompassAxis, getCompassFull, getAnotherAxisByDirect, getSameAxisByDirect } from "./astC0.ts"
import { LocaAttr } from "./astL2.ts"
import { Item, LinkItem } from "./astL4.ts"
import { ItemLoca, GateLoca } from "./astL5.ts"
// FILE ERROR ID = '31'
// deno-lint-ignore require-await
export const calcLoca = async (items: Item[], linkItems: LinkItem[], locaAttr: LocaAttr): Promise<[ItemLoca[], GateLoca[]]> => {
// FUNCTION ERROR ID = '01'
const sizes: Size[] = [];
getCalcSizeRecursive(0, items, sizes);
const itemLocas: ItemLoca[] = [];
const rootSize = sizes[0];
itemLocas[0] = {
itemId: 0,
size: rootSize,
coord: [0, 0],
}
getCalcItemCoordRecursive(0, items, sizes, itemLocas);
const gateLocas = getCalcGateLoca(linkItems, items, itemLocas, locaAttr);
return [itemLocas, gateLocas];
}
const getCalcSizeRecursive = (itemId: ItemId, items: Item[], sizes: Size[]): Size => {
// FUNCTION ERROR ID = '02'
const item = items[itemId];
const itemType = item.type;
if (itemType === 'Cell') {
const size = item.size;
sizes[itemId] = size;
return size;
} else if (itemType === 'Road') {
throw new Error(`[E310201] invalid unreachable code.`);
} else if (itemType === 'Group' || itemType === 'Unit') {
let maxMainItemWidth = 0;
const size: Size = [0, 0];
const compassAxis = getCompassAxis(item.compassItems);
item.crossItems.forEach(eachCrossItem => {
eachCrossItem.forEach(itemId => {
const item = items[itemId];
if (item.type !== 'Road') {
throw new Error(`[E310201] invalid unreachable code.`);
}
size[compassAxis[1]] += item.width;
});
});
item.mainItems.forEach(itemId => {
const item = items[itemId];
const itemType = item.type;
if (itemType === 'Road') {
size[compassAxis[0]] += item.width;
} else if (itemType === 'Cell' || itemType === 'Group' || itemType === 'Unit') {
const itemSize = getCalcSizeRecursive(item.itemId, items, sizes)
size[compassAxis[0]] += itemSize[compassAxis[0]];
if (maxMainItemWidth < itemSize[compassAxis[1]]) {
maxMainItemWidth = itemSize[compassAxis[1]];
}
} else {
const _: never = itemType;
return _;
}
});
size[compassAxis[1]] += maxMainItemWidth;
size[0] += (item.space[0] + item.space[2])
size[1] += (item.space[1] + item.space[3])
sizes[itemId] = size;
item.mainItems.forEach(itemId => {
const item = items[itemId];
const itemType = item.type;
if (itemType === 'Road') {
const mainItemSize: Size = [0, 0];
mainItemSize[compassAxis[0]] = item.width;
mainItemSize[compassAxis[1]] = maxMainItemWidth;
sizes[itemId] = mainItemSize;
} else if (itemType === 'Cell' || itemType === 'Group' || itemType === 'Unit') {
// pass
} else {
const _: never = itemType;
return _;
}
});
item.crossItems.forEach(eachCrossItem => {
eachCrossItem.forEach(itemId => {
const item = items[itemId];
if (item.type !== 'Road') {
throw new Error(`[E310201] invalid unreachable code.`);
}
const crossItemSize: Size = [0, 0];
crossItemSize[compassAxis[0]] = size[compassAxis[0]];
crossItemSize[compassAxis[1]] = item.width;
sizes[itemId] = crossItemSize;
});
});
return size;
} else {
const _: never = itemType;
return _;
}
}
const getCalcItemCoordRecursive = (itemId: ItemId, items: Item[], sizes: Size[], itemLocas: ItemLoca[]): void => {
// FUNCTION ERROR ID = '03'
const item = items[itemId];
const itemType = item.type;
if (itemType === 'Group' || itemType === 'Unit') {
const compassAxis = getCompassAxis(item.compassItems);
const mainCood = item.space[compassAxis[0]];
let crossCood = item.space[compassAxis[1]];
item.crossItems[0].forEach(itemId => {
const item = items[itemId];
const size = sizes[itemId];
const itemType = item.type;
if (itemType !== 'Road') {
throw new Error(`[E310201] invalid unreachable code.`);
}
itemLocas[itemId] = {
itemId: itemId,
size: size,
coord: [mainCood, crossCood],
}
crossCood += size[compassAxis[1]];
});
let mainItemMainCood = mainCood;
const mainItemCrossCood = crossCood;
let maxMainItemWidth = 0;
item.mainItems.forEach(itemId => {
const size = sizes[itemId];
if (maxMainItemWidth < size[compassAxis[1]]) {
maxMainItemWidth = size[compassAxis[1]];
}
});
crossCood += maxMainItemWidth;
item.crossItems[1].forEach(itemId => {
const item = items[itemId];
const size = sizes[itemId];
const itemType = item.type;
if (itemType !== 'Road') {
throw new Error(`[E310201] invalid unreachable code.`);
}
itemLocas[itemId] = {
itemId: itemId,
size: size,
coord: [mainCood, crossCood],
}
crossCood += size[compassAxis[1]];
});
item.mainItems.forEach(itemId => {
const item = items[itemId];
const size = sizes[itemId];
const itemType = item.type;
if (itemType === 'Road') {
itemLocas[itemId] = {
itemId: itemId,
size: size,
coord: [mainItemMainCood, mainItemCrossCood],
}
mainItemMainCood += size[compassAxis[0]];
} else if (itemType === 'Cell') {
let cellCrossCood;
if (item.align === 'start') {
cellCrossCood = mainItemCrossCood;
} else if (item.align === 'center') {
cellCrossCood = mainItemCrossCood + Math.floor((maxMainItemWidth - size[compassAxis[1]]) / 2);
} else if (item.align === 'end') {
cellCrossCood = mainItemCrossCood + maxMainItemWidth - size[compassAxis[1]];
} else {
const _: never = item.align;
return _;
}
itemLocas[itemId] = {
itemId: itemId,
size: size,
coord: [mainItemMainCood, cellCrossCood],
}
mainItemMainCood += size[compassAxis[0]];
} else if (itemType === 'Group' || itemType === 'Unit') {
let cellCrossCood;
if (item.align === 'start') {
cellCrossCood = mainItemCrossCood;
} else if (item.align === 'center') {
cellCrossCood = mainItemCrossCood + Math.floor((maxMainItemWidth - size[compassAxis[1]]) / 2);
} else if (item.align === 'end') {
cellCrossCood = mainItemCrossCood + maxMainItemWidth - size[compassAxis[1]];
} else {
const _: never = item.align;
return _;
}
itemLocas[itemId] = {
itemId: itemId,
size: size,
coord: [mainItemMainCood, cellCrossCood],
}
getCalcItemCoordRecursive(itemId, items, sizes, itemLocas);
mainItemMainCood += size[compassAxis[0]];
} else {
const _: never = itemType;
return _;
}
});
} else if (itemType === 'Cell' || itemType === 'Road') {
// pass
} else {
const _: never = itemType;
return _;
}
}
const getCalcGateLoca = (linkItems: LinkItem[], items: Item[], itemLocas: ItemLoca[], locaAttr: LocaAttr): GateLoca[] => {
// FUNCTION ERROR ID = '04'
const itemEdgeInfoMap: Map<ItemId, [itemEdgeInfo, itemEdgeInfo, itemEdgeInfo, itemEdgeInfo]> = new Map();
const gateLocas: GateLoca[] = [];
linkItems.forEach(linkItem => {
const linkId = linkItem.linkId;
const frItemId = linkItem.box[0];
const toItemId = linkItem.box[1];
let frItemEdgeInfo = itemEdgeInfoMap.get(frItemId);
if (!frItemEdgeInfo) {
frItemEdgeInfo = getItemEdgeInfo(frItemId, items, itemLocas, locaAttr);
itemEdgeInfoMap.set(frItemId, frItemEdgeInfo);
}
let toItemEdgeInfo = itemEdgeInfoMap.get(toItemId);
if (!toItemEdgeInfo) {
toItemEdgeInfo = getItemEdgeInfo(toItemId, items, itemLocas, locaAttr);
itemEdgeInfoMap.set(toItemId, toItemEdgeInfo);
}
const frItemInfo = frItemEdgeInfo[linkItem.edge[0]];
const toItemInfo = toItemEdgeInfo[linkItem.edge[1]];
const frCurrent = frItemInfo.currentGate;
const toCurrent = toItemInfo.currentGate;
frItemInfo.currentGate = frCurrent + 1;
toItemInfo.currentGate = toCurrent + 1;
gateLocas[linkId] = {
linkId: linkId,
coords: [
frItemInfo.startCood + (locaAttr.gate_gap[frItemInfo.absoluteAxis] * frCurrent),
toItemInfo.startCood + (locaAttr.gate_gap[toItemInfo.absoluteAxis] * toCurrent),
]
}
});
return gateLocas;
}
type itemEdgeInfo = {
absoluteAxis: Direct;
startCood: number;
currentGate: number;
};
const getItemEdgeInfo = (itemId: ItemId, items: Item[], itemLocas: ItemLoca[], locaAttr: LocaAttr): [itemEdgeInfo, itemEdgeInfo, itemEdgeInfo, itemEdgeInfo] => {
// FUNCTION ERROR ID = '05'
const item = items[itemId];
const itemLoca = itemLocas[itemId];
if (!(item.type === 'Group' || item.type === 'Cell')) {
throw new Error(`[E310501] invalid unreachable code.`);
}
const compass = getCompassFull(item.compassSelf);
const getItemEdgeInfo = (d: Direct) => {
const direct = compass[d];
const absoluteAxis = getAnotherAxisByDirect(direct);
const num = item.links[0][d].length + item.links[1][d].length;
const allGateLen = num === 0 ? 0 : (num - 1) * locaAttr.gate_gap[direct];
const edgeLength = itemLoca.size[absoluteAxis];
return {
absoluteAxis: absoluteAxis,
startCood: item.margin[getSameAxisByDirect(d)] + Math.floor((edgeLength - allGateLen - item.margin[d] - item.margin[getReverse(d)]) / 2),
currentGate: 0,
}
};
return [
getItemEdgeInfo(0),
getItemEdgeInfo(1),
getItemEdgeInfo(2),
getItemEdgeInfo(3),
];
}
描画用位置決定 [parseL5xL6.ts]
先ほどの位置は、相対位置での指定でした。これを、描画に必要な絶対座標に変換します。
SVG出力 [parseL6xSvg.ts]
位置情報を SVG に変換します。折れ曲がりは曲線の区別がつきやすいように、Path を用いて曲線とします。
WEBページ用エントリーポイント
これらのパースをつなぎ合わせ、また flexflowflight✈ のクラス名のタグを検知する WEBページ用のモジュールを作成します。
/// <reference no-default-lib="true"/>
/// <reference lib="dom" />
/// <reference lib="deno.ns" />
import { Name } from "./core/astC1.ts"
import { Cell as CellL1 } from "./core/astL1.ts"
import { DocAttr } from "./core/astL2.ts"
import { Parse, parse } from "./parse.ts"
interface Window {
flexflowflight: {
onload: boolean;
debug: boolean;
parse: Parse;
}
}
declare let window: Window
window.flexflowflight = {
onload: true,
debug: false,
parse: parse,
};
addEventListener(
'load',
function (_e) {
if (window.flexflowflight.onload) {
const elems = document.querySelectorAll<HTMLElement>(".flexflowflight");
elems.forEach(async elem => {
elem.style.display = "none";
elem.insertAdjacentHTML("afterend", '<svg id="_flexflowflight_work" xmlns="http://www.w3.org/2000/svg" width="1000" height="1000"></svg>');
const tmpElem = document.getElementById('_flexflowflight_work');
// deno-lint-ignore require-await
const getTextSize = async (name: Name, _cellL1: CellL1): Promise<[number, number]> => {
const text = document.createElementNS('http://www.w3.org/2000/svg', 'text');
text.textContent = name;
tmpElem?.appendChild(text);
const domRect = text.getBoundingClientRect()
return [domRect.width, domRect.height];
}
const svg = await parse(elem.textContent || '', { textSize: getTextSize, debug: window.flexflowflight.debug });
tmpElem?.remove()
elem.insertAdjacentHTML("afterend", svg);
});
}
},
false
);
経路決定改善(配置後位置の利用)[calcRouteV2.ts]
さて、経路の決定のアルゴリズムでは、配置される位置を意識していないという問題があります。
そのため、以下のように、う回が気になる現象が発生するでしょう。
See the Pen Untitled by j5c8k6m8 (@j5c8k6m8) on CodePen.
この、改善を考えます。配置後の位置を考慮した、経路の決定を行うためには、一度、AstL6 まで実行してしまい、位置を考慮した経路を決定すればよいでしょう。この方針での経路決定アルゴリズムを示します。
import { NodeId, ItemId, Direct, Compass, Axis, getMappingCompassFull, isSameAxisDirect, getSameAxisByDirect, getAnotherAxisByDirect, getReverse, getCompassFull, XY, CrossAvenue } from "./astC0.ts"
import { AstL2, Node, Container, Link } from "./astL2.ts"
import { AstL3 } from "./astL3.ts"
import { AstL4 } from "./astL4.ts"
import { AstL5 } from "./astL5.ts"
import { AstL6, ItemLoca } from "./astL6.ts"
import { LinkRoute, Road } from "./astL3.ts"
import { parse as parseL3xL4 } from "./parseL3xL4.ts"
import { parse as parseL4xL5 } from "./parseL4xL5.ts"
import { parse as parseL5xL6 } from "./parseL5xL6.ts"
// FILE ERROR ID = '22'
export const calcRoute = async (nodes: Node[], links: Link[], astL2: AstL2): Promise<LinkRoute[]> => {
// FUNCTION ERROR ID = '01'
const dummyAstL3: AstL3 = {
nodes: astL2.nodes,
nodeAttrs: astL2.nodeAttrs,
links: [], // Dare to empty
linkAttrs: astL2.linkAttrs,
docAttr: astL2.docAttr,
locaAttr: astL2.locaAttr,
linkRoutes: [],
}
const dummyAstL4: AstL4 = await parseL3xL4(dummyAstL3, { mainLaneMin: 1, crossLaneMin: 1 });
const dummyAstL5: AstL5 = await parseL4xL5(dummyAstL4);
const dummyAstL6: AstL6 = await parseL5xL6(dummyAstL5);
const linkRoutes: LinkRoute[] = []
links.forEach(link => {
const fromNodeId = link.box[0];
const toNodeId = link.box[1];
const fromDirect = link.edge[0];
const toDirect = link.edge[1];
const fromNode = nodes[fromNodeId];
const toNode = nodes[toNodeId];
if (!fromNode) {
throw new Error(`[E220101] asgR1 is invalid.`);
}
if (!toNode) {
throw new Error(`[E220102] asgR1 is invalid.`);
}
const currentRoad = getRoad(fromNode, fromDirect, toNode, nodes);
const fromXY = getRoadXY(getGateXY(fromNode, fromDirect, dummyAstL6), currentRoad, nodes, dummyAstL6.itemLocas, dummyAstL6.n2i);
const toDummyRoad = getRoad(toNode, toDirect, fromNode, nodes);
const toXY = getRoadXY(getGateXY(toNode, toDirect, dummyAstL6), toDummyRoad, nodes, dummyAstL6.itemLocas, dummyAstL6.n2i);
const [route, _distance] = getRoutes(currentRoad, fromXY, toNode, toDirect, toXY, [], nodes, dummyAstL6, 1, null);
if (route == null) {
throw new Error(`[E220104] invalid.`);
}
linkRoutes.push({
linkId: link.linkId,
route: route,
});
});
return linkRoutes;
}
const getRoutes = (currentRoad: Road, currentXY: XY, lastNode: Node, lastDirect: Direct, lastXY: XY, currentRoute: Road[], nodes: Node[], astL6: AstL6, callNum: number, limitDistance: number | null): [Road[], number] | [null, null] => {
// FUNCTION ERROR ID = '02'
// Avoid infinite loops.
if (callNum > 100) {
throw new Error(`[E220201] nest too deep.`);
}
callNum++;
currentRoute = currentRoute.concat(currentRoad);
if (isRoadReach(currentRoad, lastNode, lastDirect, nodes)) {
const currentRoadCompass = getRoadCompass(currentRoad, nodes);
const currentRoadAbsAxis = getAnotherAxisByDirect(currentRoadCompass[currentRoad.axis]);
const retDistance = Math.abs(currentXY[currentRoadAbsAxis] - lastXY[currentRoadAbsAxis])
if (limitDistance == null || retDistance < limitDistance) {
return [currentRoute, retDistance];
} else {
return [null, null];
}
}
const minDistance = Math.abs(currentXY[0] - lastXY[0]) + Math.abs(currentXY[1] - lastXY[1]);
const extraLimitDistance = limitDistance == null ? null : limitDistance - minDistance;
if (extraLimitDistance != null && extraLimitDistance < 0) {
return [null, null];
}
const allCandidateRoads = getNextAllRoads(currentRoad, lastNode, nodes);
const candidateRoads = allCandidateRoads.filter(c => {
let notFindFlg = true;
for (let i = 0; i < currentRoute.length; i++) {
const road = currentRoute[i];
if (road.containerId === c.containerId && road.axis === c.axis && road.avenue === c.avenue) {
notFindFlg = false;
break;
}
}
return notFindFlg;
});
const innerCandidateRoads: Array<[Road, XY, number, number]> = [];
const outerCandidateRoads: Array<[Road, XY, number, number]> = [];
candidateRoads.forEach(candidateRoad => {
const targetXY = getRoadXY(currentXY, candidateRoad, nodes, astL6.itemLocas, astL6.n2i);
const roadXYAxis = getRoadAbsAxis(currentRoad, nodes);
const distance = Math.abs(currentXY[roadXYAxis] - targetXY[roadXYAxis]);
if (currentXY[roadXYAxis] <= lastXY[roadXYAxis]) {
if (lastXY[roadXYAxis] < targetXY[roadXYAxis]) {
const priorityDistance = targetXY[roadXYAxis] - lastXY[roadXYAxis];
if (extraLimitDistance != null && priorityDistance * 2 > extraLimitDistance) {
return; // continue;
}
let findFlg = false;
for (let i = 0; i < outerCandidateRoads.length; i++) {
if (outerCandidateRoads[i][3] > priorityDistance) {
outerCandidateRoads.splice(i, 0, [candidateRoad, targetXY, distance, priorityDistance]);
findFlg = true;
break;
}
}
if (!findFlg) {
outerCandidateRoads.push([candidateRoad, targetXY, distance, priorityDistance]);
}
} else if (currentXY[roadXYAxis] > targetXY[roadXYAxis]) {
const priorityDistance = currentXY[roadXYAxis] - targetXY[roadXYAxis];
if (extraLimitDistance != null && priorityDistance * 2 > extraLimitDistance) {
return; // continue;
}
let findFlg = false;
for (let i = 0; i < outerCandidateRoads.length; i++) {
if (outerCandidateRoads[i][3] > priorityDistance) {
outerCandidateRoads.splice(i, 0, [candidateRoad, targetXY, distance, priorityDistance]);
findFlg = true;
break;
}
}
if (!findFlg) {
outerCandidateRoads.push([candidateRoad, targetXY, distance, priorityDistance]);
}
} else {
const priorityDistance = lastXY[roadXYAxis] - targetXY[roadXYAxis];
let findFlg = false;
for (let i = 0; i < innerCandidateRoads.length; i++) {
if (innerCandidateRoads[i][3] > priorityDistance) {
innerCandidateRoads.splice(i, 0, [candidateRoad, targetXY, distance, priorityDistance])
findFlg = true;
break;
}
}
if (!findFlg) {
innerCandidateRoads.push([candidateRoad, targetXY, distance, priorityDistance]);
}
}
} else {
if (lastXY[roadXYAxis] > targetXY[roadXYAxis]) {
const priorityDistance = targetXY[roadXYAxis] - lastXY[roadXYAxis];
if (extraLimitDistance != null && priorityDistance * 2 > extraLimitDistance) {
return; // continue;
}
let findFlg = false;
for (let i = 0; i < outerCandidateRoads.length; i++) {
if (outerCandidateRoads[i][3] > priorityDistance) {
outerCandidateRoads.splice(i, 0, [candidateRoad, targetXY, distance, priorityDistance])
findFlg = true;
break;
}
}
if (!findFlg) {
outerCandidateRoads.push([candidateRoad, targetXY, distance, priorityDistance]);
}
} else if (currentXY[roadXYAxis] < targetXY[roadXYAxis]) {
const priorityDistance = targetXY[roadXYAxis] - currentXY[roadXYAxis];
if (extraLimitDistance != null && priorityDistance * 2 > extraLimitDistance) {
return; // continue;
}
let findFlg = false;
for (let i = 0; i < outerCandidateRoads.length; i++) {
if (outerCandidateRoads[i][3] > priorityDistance) {
outerCandidateRoads.splice(i, 0, [candidateRoad, targetXY, distance, priorityDistance]);
findFlg = true;
break;
}
}
if (!findFlg) {
outerCandidateRoads.push([candidateRoad, targetXY, distance, priorityDistance]);
}
} else {
const priorityDistance = targetXY[roadXYAxis] - lastXY[roadXYAxis];
let findFlg = false;
for (let i = 0; i < innerCandidateRoads.length; i++) {
if (innerCandidateRoads[i][3] > priorityDistance) {
innerCandidateRoads.splice(i, 0, [candidateRoad, targetXY, distance, priorityDistance])
findFlg = true;
break;
}
}
if (!findFlg) {
innerCandidateRoads.push([candidateRoad, targetXY, distance, priorityDistance]);
}
}
}
});
let extraDistance: number | null = null;
let ret: [Road[], number] | [null, null] = [null, null];
for (let i = 0; i < innerCandidateRoads.length; i++) {
const t = innerCandidateRoads[i];
let argLimitDistance: number | null = null;
if (extraDistance != null) {
argLimitDistance = minDistance + extraDistance - t[2];
} else if (limitDistance != null) {
argLimitDistance = limitDistance - t[2];
}
const [tmpRoute, tmpDistance] = getRoutes(t[0], t[1], lastNode, lastDirect, lastXY, currentRoute, nodes, astL6, callNum, argLimitDistance);
if (tmpRoute != null && tmpDistance != null) {
const distance = tmpDistance + t[2];
const tmpExtraDistance = distance - minDistance;
if (tmpExtraDistance === 0) {
return [tmpRoute, distance];
} else if (extraDistance == null || extraDistance > tmpExtraDistance) {
extraDistance = tmpExtraDistance;
ret = [tmpRoute, distance];
}
}
}
for (let i = 0; i < outerCandidateRoads.length; i++) {
const t = outerCandidateRoads[i];
if (extraDistance != null && extraDistance < t[3] * 2) {
break;
}
let argLimitDistance: number | null = null;
if (extraDistance != null) {
argLimitDistance = minDistance + extraDistance - t[2];
} else if (limitDistance != null) {
argLimitDistance = limitDistance - t[2];
}
const [tmpRoute, tmpDistance] = getRoutes(t[0], t[1], lastNode, lastDirect, lastXY, currentRoute, nodes, astL6, callNum, argLimitDistance);
if (tmpRoute != null && tmpDistance != null) {
const distance = tmpDistance + t[2];
const tmpExtraDistance = distance - minDistance;
if (extraDistance == null || extraDistance > tmpExtraDistance) {
extraDistance = tmpExtraDistance;
ret = [tmpRoute, distance];
}
}
}
return ret;
}
const getGateXY = (node: Node, direct: Direct, astL6: AstL6): XY => {
// FUNCTION ERROR ID = '04'
const itemLoca = astL6.itemLocas[astL6.n2i[node.nodeId]];
const absDirect = getCompassFull(node.compassSelf)[direct];
if (absDirect === 0) {
return [
itemLoca.xy[0] + itemLoca.size[0],
itemLoca.xy[1] + Math.floor(itemLoca.size[1] / 2),
];
} else if (absDirect === 1) {
return [
itemLoca.xy[0] + Math.floor(itemLoca.size[0] / 2),
itemLoca.xy[1] + itemLoca.size[1],
];
} else if (absDirect === 2) {
return [
itemLoca.xy[0],
itemLoca.xy[1] + Math.floor(itemLoca.size[1] / 2),
];
} else if (absDirect === 3) {
return [
itemLoca.xy[0] + Math.floor(itemLoca.size[0] / 2),
itemLoca.xy[1],
];
} else {
const _: never = absDirect;
return _;
}
}
const getRoad = (fromNode: Node, fromDirect: Direct, toNode: Node, nodes: Node[]): Road => {
// FUNCTION ERROR ID = '05'
const fromParentsR = [...fromNode.parents].reverse();
const toParentsR = [...toNode.parents].reverse();
if (fromNode.parents.includes(toNode.nodeId)) {
throw new Error(`[E220506] Direct descendants can not connect.`);
}
if (toNode.parents.includes(fromNode.nodeId)) {
throw new Error(`[E220507] Direct descendants can not connect.`);
}
let parentIndex = -1;
for (let i = 0; i < fromParentsR.length; i++) {
const toCommonParentIndex = toParentsR.indexOf(fromParentsR[i]);
if (toCommonParentIndex !== -1) {
parentIndex = i;
break;
}
}
// fromNode and toNode are not rootNode.
if (parentIndex == -1) {
throw new Error(`[E220505] asgR1 is invalid.`);
}
let targetIndex: number;
if (fromDirect === 0 && fromNode.siblings[fromNode.siblings.length - 1] !== fromNode.nodeId) {
targetIndex = 0;
} else if (fromDirect === 2 && fromNode.siblings[0] !== fromNode.nodeId) {
targetIndex = 0;
} else {
if (fromNode.bnParents[fromDirect] - 1 >= parentIndex) {
targetIndex = parentIndex;
} else {
targetIndex = fromNode.bnParents[fromDirect] - 1;
}
}
const targetNodeId = fromParentsR[targetIndex];
if (!targetNodeId == null) {
throw new Error(`[E220501] asgR1 is invalid.`);
}
const targetNode = nodes[targetNodeId];
if (!targetNode) {
throw new Error(`[E220502] asgR1 is invalid.`);
}
if (targetNode.type !== 'Group' && targetNode.type !== 'Unit') {
throw new Error(`[E220503] asgR1 is invalid.`);
}
const railDirect = getMappingCompassFull(fromNode.compassSelf, targetNode.compassItems)[fromDirect];
const siblingIndex = targetNode.children.indexOf(targetIndex > 0 ? fromParentsR[targetIndex - 1] : fromNode.nodeId);
if (railDirect === 0) {
return {
containerId: targetNodeId,
axis: 0,
avenue: siblingIndex + 1,
}
} else if (railDirect === 1) {
return {
containerId: targetNodeId,
axis: 1,
avenue: 1,
}
} else if (railDirect === 2) {
return {
containerId: targetNodeId,
axis: 0,
avenue: siblingIndex,
}
} else if (railDirect === 3) {
return {
containerId: targetNodeId,
axis: 1,
avenue: 0,
}
} else {
const _: never = railDirect;
return _;
}
}
const isRoadReach = (currentRoad: Road, lastNode: Node, lastDirect: Direct, nodes: Node[]): boolean => {
// FUNCTION ERROR ID = '06'
const lastParentsR = [...lastNode.parents].reverse();
const parentIndex = lastParentsR.indexOf(currentRoad.containerId);
if (parentIndex === -1) {
return false;
}
if (lastNode.bnParents[lastDirect] - 1 < parentIndex) {
return false;
}
const roadContainer = nodes[currentRoad.containerId];
if (!(roadContainer.type === 'Group' || roadContainer.type === 'Unit')) {
throw new Error(`[E220601] road is invalid.`);
}
const railDirect = getMappingCompassFull(lastNode.compassSelf, roadContainer.compassItems)[lastDirect];
if (railDirect === 0) {
if (currentRoad.axis === 0) {
const siblingIndex = roadContainer.children.indexOf(parentIndex > 0 ? lastParentsR[parentIndex - 1] : lastNode.nodeId);
if (siblingIndex + 1 === currentRoad.avenue) {
return true;
}
}
} else if (railDirect === 1) {
if (currentRoad.axis === 1 && currentRoad.avenue === 1) {
return true;
}
} else if (railDirect === 2) {
if (currentRoad.axis === 0) {
const siblingIndex = roadContainer.children.indexOf(parentIndex > 0 ? lastParentsR[parentIndex - 1] : lastNode.nodeId);
if (siblingIndex === currentRoad.avenue) {
return true;
}
}
} else if (railDirect === 3) {
if (currentRoad.axis === 1 && currentRoad.avenue === 0) {
return true;
}
}
return false;
}
const getRoadCompass = (road: Road, nodes: Node[]): Compass => {
// FUNCTION ERROR ID = '07'
const container = nodes[road.containerId];
if (container.type !== 'Group' && container.type !== 'Unit') {
throw new Error(`[E220701] asgR1 is invalid.`);
}
return container.compassItems;
}
const getRoadAbsAxis = (road: Road, nodes: Node[]): Axis => {
// FUNCTION ERROR ID = '07'
const container = nodes[road.containerId];
if (container.type !== 'Group' && container.type !== 'Unit') {
throw new Error(`[E220701] asgR1 is invalid.`);
}
const compass = container.compassItems;
return getAnotherAxisByDirect(compass[road.axis]);
}
const getNextAllRoads = (currentRoad: Road, lastNode: Node, nodes: Node[]): Road[] => {
// FUNCTION ERROR ID = '08'
let ret: Road[] = [];
const container = nodes[currentRoad.containerId];
if (!(container.type === 'Group' || container.type === 'Unit')) {
throw new Error(`[E220801] invalid.`);
}
const roadAxis = currentRoad.axis;
if (roadAxis === 0) {
ret.push(getRoadByContainer(container, 1, 0, lastNode, nodes));
ret.push(getRoadByContainer(container, 1, 1, lastNode, nodes));
if (currentRoad.avenue !== 0) {
ret = ret.concat(getNextAllRoadsEachNode(container.children[currentRoad.avenue - 1], container.compassItems, 0, lastNode, nodes));
}
if (currentRoad.avenue !== container.children.length) {
ret = ret.concat(getNextAllRoadsEachNode(container.children[currentRoad.avenue], container.compassItems, 2, lastNode, nodes));
}
} else if (roadAxis === 1) {
const roadAvenue = currentRoad.avenue;
for (let i = 0; i < container.children.length + 1; i++) {
ret.push(getRoadByContainer(container, 0, i, lastNode, nodes));
}
if (roadAvenue === 0) {
container.children.forEach((child: NodeId) => {
ret = ret.concat(getNextAllRoadsEachNode(child, container.compassItems, 3, lastNode, nodes));
});
} else if (roadAvenue === 1) {
container.children.forEach((child: NodeId) => {
ret = ret.concat(getNextAllRoadsEachNode(child, container.compassItems, 1, lastNode, nodes));
});
} else {
const _: never = roadAvenue;
return _;
}
} else {
const _: never = roadAxis;
return _
}
return ret;
}
// for blank group, not use getRoad
const getRoadByContainer = (container: Container, axis: Axis, avenue: number, toNode: Node, nodes: Node[]): Road => {
// FUNCTION ERROR ID = '09'
let itemsDirect: Direct;
if (axis === 0) {
if (avenue === 0) {
itemsDirect = 2;
} else if (avenue === container.children.length) {
itemsDirect = 0;
} else {
return {
containerId: container.nodeId,
axis: axis,
avenue: avenue,
};
}
} else if (axis === 1) {
if (avenue === 0) {
itemsDirect = 3;
} else if (avenue === 1) {
itemsDirect = 1;
} else {
throw new Error(`[E220901] invalid.`);
}
} else {
const _: never = axis;
return _;
}
const containerParentsR = [...container.parents].reverse();
const toParentsR = [...toNode.parents].reverse();
if (container.parents.includes(toNode.nodeId)) {
throw new Error(`[E220902] Direct descendants can not connect.`);
}
if (container.nodeId === 0 || toNode.parents.includes(container.nodeId)) {
if (axis === 0) {
return {
containerId: container.nodeId,
axis: 0,
avenue: avenue,
};
} else if (axis === 1) {
if (avenue === 0 || avenue === 1) {
return {
containerId: container.nodeId,
axis: 1,
avenue: avenue,
};
} else {
throw new Error(`[E220907] invalid.`);
}
} else {
const _: never = axis;
return _;
}
}
let parentIndex = -1;
for (let i = 0; i < containerParentsR.length; i++) {
const toCommonParentIndex = toParentsR.indexOf(containerParentsR[i]);
if (toCommonParentIndex !== -1) {
parentIndex = i;
break;
}
}
// toNode are not rootNode.
if (parentIndex == -1) {
throw new Error(`[E220903] asgR1 is invalid.`);
}
const selfDirect = getMappingCompassFull(container.compassItems, container.compassSelf)[itemsDirect];
let targetIndex: number;
if (container.bnParents[selfDirect] - 1 >= parentIndex) {
targetIndex = parentIndex;
} else {
targetIndex = container.bnParents[selfDirect] - 1;
}
const targetNodeId = containerParentsR[targetIndex];
if (!targetNodeId == null) {
throw new Error(`[E220904] asgR1 is invalid.`);
}
const targetNode = nodes[targetNodeId];
if (!targetNode) {
throw new Error(`[E220905] asgR1 is invalid.`);
}
if (targetNode.type !== 'Group' && targetNode.type !== 'Unit') {
throw new Error(`[E220906] asgR1 is invalid.`);
}
const railDirect = getMappingCompassFull(container.compassSelf, targetNode.compassItems)[selfDirect];
const siblingIndex = targetNode.children.indexOf(targetIndex > 0 ? containerParentsR[targetIndex - 1] : container.nodeId)
if (railDirect === 0) {
return {
containerId: targetNodeId,
axis: 0,
avenue: siblingIndex + 1,
}
} else if (railDirect === 1) {
return {
containerId: targetNodeId,
axis: 1,
avenue: 1,
}
} else if (railDirect === 2) {
return {
containerId: targetNodeId,
axis: 0,
avenue: siblingIndex,
}
} else if (railDirect === 3) {
return {
containerId: targetNodeId,
axis: 1,
avenue: 0,
}
} else {
const _: never = railDirect;
return _;
}
}
const getNextAllRoadsEachNode = (nodeId: NodeId, compass: Compass, direct: Direct, toNode: Node, nodes: Node[]): Road[] => {
let ret: Road[] = []
if (nodeId === toNode.nodeId) {
return ret;
}
const node = nodes[nodeId];
if (node.type === 'Cell') {
return ret;
}
const nodeCompass = node.compassItems;
const nodeDirect = getMappingCompassFull(compass, nodeCompass)[direct];
if (nodeDirect === 0) {
if (node.children.length > 0) {
ret = ret.concat(getNextAllRoadsEachNode(node.children[node.children.length - 1], compass, direct, toNode, nodes));
}
} else if (nodeDirect === 2) {
if (node.children.length > 0) {
ret = ret.concat(getNextAllRoadsEachNode(node.children[0], compass, direct, toNode, nodes));
}
} else if (nodeDirect === 1 || nodeDirect === 3) {
for (let i = 0; i < node.children.length - 1; i++) {
ret.push(getRoadByContainer(node, 0, i + 1, toNode, nodes));
}
node.children.forEach(child => {
ret = ret.concat(getNextAllRoadsEachNode(child, compass, direct, toNode, nodes));
});
} else {
const _: never = nodeDirect;
return _;
}
return ret;
}
const getRoadXY = (xy: XY, road: Road, nodes: Node[], itemLocas: ItemLoca[], n2i: ItemId[]): XY => {
const ret: [number, number] = [xy[0], xy[1]];
const xyAxis = getSameAxisByDirect(getRoadCompass(road, nodes)[road.axis]);
if (road.axis === 0) {
const container = nodes[road.containerId];
if (!(container.type === 'Group' || container.type === 'Unit')) {
throw new Error(`[E220203] invalid.`);
}
if (container.compassItems[0] < 2) {
if (road.avenue < container.children.length) {
ret[xyAxis] = itemLocas[n2i[container.children[road.avenue]]].xy[xyAxis];
} else {
const itemLoca = itemLocas[n2i[container.children[container.children.length - 1]]];
ret[xyAxis] = itemLoca.xy[xyAxis] + itemLoca.size[xyAxis];
}
} else {
if (road.avenue === 0) {
const itemLoca = itemLocas[n2i[container.children[container.children.length - 1]]];
ret[xyAxis] = itemLoca.xy[xyAxis] + itemLoca.size[xyAxis];
} else {
ret[xyAxis] = itemLocas[n2i[container.children[container.children.length - road.avenue]]].xy[xyAxis];
}
}
} else {
const itemLoca = itemLocas[n2i[road.containerId]];
const avenue = road.avenue;
if (avenue === 0) {
ret[xyAxis] = itemLoca.xy[xyAxis];
} else if (avenue === 1) {
ret[xyAxis] = itemLoca.xy[xyAxis] + itemLoca.size[xyAxis];
} else {
const _: never = avenue;
return _;
}
}
return ret;
}
See the Pen Untitled by j5c8k6m8 (@j5c8k6m8) on CodePen.
アイテム位置決定の改善 [calcLocaV2.ts]
7/18 時点の α版では実装中となります。実装が出来次第、記事に追記する予定です。
さいごに
いかがでしたでしょうか？
CSS Flexbox で配置されたノードに対して、コネクタを『いい感じの経路で描画』する というアイディアのすべてを アルゴリズム力不足により イベント期間中には実装できませんでしたが、最低限、動く形でその可能性を示せたと思っています。
アイディアを実現する機会を提供いただいた Qiita にも、感謝しています。
flexflowflight✈ は、イベントのために作成を始めましたが、 CSS Flexbox で配置されたノードに対して、コネクタを『いい感じの経路で描画』する というアイディア自体は、他のグラフ描画ツールにはないもので、可能性を感じています。
この発想に、少しでも可能性を感じられたら、本記事への LGTM や、GitHub へスターをつけてもらえると、筆者のモチベーションに繋がりますのでよろしくおねがいします！
（もちろん PullRequest も大歓迎です）
-
flight✈ は、フローチャートを作成する目的である、俯瞰を表しています。 ↩
-
「基本的な機能」 に関する議論は避けますが、順接・分岐・反復の制御構造を主体とする構造化プログラミングを主体としています。また、重複を排除するような最適化も、
執筆に間に合わせるため十分に実施していません。 ↩ -
レスポンシブデザインの考慮を除くものとします。flexflowflight✈ では mermaid.js と同様にレスポンシブデザインを考慮しません。 ↩
-
同じ接続元や接続先のコネクタを、オプションであえて重ねることもできるようにする予定です。
コネクタの数が多くなっても、コネクタが重ならないためには、図を拡張(伸張)させる必要があります。 Flexbox指向で拡張させれば、ノードの相対的な配置を変えない拡張が可能 と考えました。 ↩ -
グリッドレイアウトの考え方などを参考に、ハイブリッドな構成にできないかなども考えた ↩
-
筆者は一時、 toml に、マークダウンの
-を用いた記法を加え、 テーブル記法を相対パスなどを加えて先頭=で表現可能な、横線ばかりの設定ファイル記述言語lamen🍜を途中まで作り、 (toml に対する優位性が少なく) 供養したことがあります。 ↩