algorithm - 無向巡回グラフを座標平面に射影

Question

私は部屋のコレクションを持っています。各部屋は、基本的な方向 (北、南、東、西) を介して 1 つ以上の他の部屋に接続されています。部屋は、A が B の西にある場合、B が A の東になるように接続されています。したがって、無向グラフ。次に、この部屋のコレクションを座標平面でグラフ化する必要があります。すべてのエッジは X 軸または Y 軸に平行でなければなりません。

私はいくつかの異なるアプローチを試しましたが、これまでのところ最も効果的だと思うのは次のとおりです。

1. 「中心」を見つけて (0,0) を割り当てます (他のすべての部屋への最短経路の長さの合計が最小になる部屋)。これが本当に必要かどうかはわかりませんが、出力の中央揃えが容易になります。
2. 中心 C から出て、遭遇した各部屋 R に座標 (X, Y) を割り当てます。ここで、P は C=>R を結ぶパスであり、座標平面上で最大の変位が生じます。X は、P に沿った正味の水平移動です。 、Y は P に沿った正味の垂直移動です。

次の方向のベクトルを想定します: 北 = [0,1] 南 = [0,-1] 東 = [1,0] 西 = [-1,0]

Answer 1

それは合理的なアプローチのように聞こえます。グラフでトポロジカルソートを実行し、ノードを順番に処理するアプローチのファミリー全体があると思います。これにより、すべてのノードに対して配置するスペースが確保されます。トポロジカル順序でそれよりも小さいノードはすべてその片隅に。

これをトポロジカル ソートと見なすもう 1 つの方法は、中心から作業するのではなく、各リンクが北から南または東から西に向かう有向グラフを形成することです。ノードを配置するときに、そのノードの北または西にあるノードがこれまでに配置されていないことがわかっているトポロジカル ソートに従って、東と南の隣接ノードに基づいて座標を割り当てることができます。

以前のようにノードを原点の周りに配置したい場合は、後でそれらをすべて変更し、各座標値に定数を追加して必要に応じてシフトすることができます。