プロジェクトを間違った方向に循環的に表示する

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

これは妥当なアプローチのようです。私は、グラフ上でトポロジカルなソートを行い、順番にノードを処理するアプローチのファミリがあると思うので、トポロジカルな順序よりも小さいノードがすべてであるため、すべてのノードに対して配置するスペースがあります。それの片側に。

これを見る別の方法は、トポロジカルな並べ替えは中心からではなく、各リンクが北から南または東から西に向けられた有向グラフを形成することです。トポロジカルなソートを行った後、ノードを配置するときには、これまでノードの北または西に配置されていないノードがないので、東と南の近隣に基づいてその座標を割り当てることができます。

ノードを原点の周りに配置する場合は、後ですべてを変更し、各座標値に定数を追加して希望通りにシフトすることができます。