ユーザーが一連のノードから Web ダイアグラムを作成できるようにするコントロールを (実際に考えて) 実装しています。目的は、ソフトウェアの別の部分で尋ねられる一連の質問からある種の「フローチャート」を作成することです。質問ごとに、選択された回答によって、次にどの質問を行うかが決まります。少し FSM っぽいですが、「質問 Y に対して X と答えた場合は、次の質問に答えてください...」という形式の質問の直線的な進行よりもはるかにスマートです。グラフは Web であり、ツリーであるとは限りません。これは、グラフを定義するユーザーが、いくつかのフォローアップの質問をしてから、質問の「通常の」行に戻りたい場合があるため、2 つの異なるノードが「マージ」される可能性があるためです。同じ子ノード。でも、
これが質問です。相互に交差する必要がある Web のノードを接続する線の数が最小限になるように、ノードを再配置する「配置」ボタン (または単に自動配置) が必要です。ほとんどのフローチャート ツールにはこれを行う機能がありますが、私の Google-fu はこのタイプの汎用アルゴリズムを見つけることができませんでした。私はこれを「交差数」問題と特定しましたが、V ノードと E パスを含むグラフの最小交差数を見つける一般的な解決策はないようであり、そのような解決策は NP 困難になります (特定のサブ問題を 1 回の操作で解決できれば、問題全体を多項式時間で解決できます)。その上、私が見つけた参照のどれも、最小値でグラフをレイアウトできる詳細なアルゴリズムを見つけていません (言うまでもなく、"
ヒントはありますか？
編集:私は Sharkos に彼の優れた参考文献に目盛りを付けました. ただし、グラフに明確な開始点があり、一方向で非円形であると仮定すると、実際に機能するアルゴリズム (おそらく最適ではない) は非常に単純です。擬似コード:
"
Give all nodes an initial XScore, YScore and LinkScore of 0
Determine the start node (either designated, or the one not linked to by any other)
Set start node's XScore and YScore to 1
Set running YScore = 1
Start recursion
for each path from node
if node on other end has XScore <= current
set other node's XScore to current + 1
if node on other end has YScore <= running YScore
set other node's YScore to running YScore
increment other node's LinkScore
Recurse with node on other end
Increment running YScore
Order nodes by XScore, then YScore.
--If the graph happens to be planar, we're done.
--To minimize crossover:
for each XScore
for each node with that XScore
if the next node with the same XScore has a higher LinkScore
swap the two nodes, exchanging YScores