Проект непрямой циклический график на плоскости координат

Question

У меня есть коллекция комнат, каждая из которых соединена с одной или несколькими другими комнатами через главные направления (север, юг, восток, запад). Номера были соединены таким образом, что если A находится к западу от B, то B находится к востоку от A; таким образом, неориентированный граф. Теперь мне нужно взять эту коллекцию комнат и нарисовать их на координатной плоскости. Все ребра должны быть параллельны оси X или Y.

Я пробовал несколько различных подходов, но я думаю, что наиболее эффективным до сих пор выглядит следующим образом:

1. Найти «центр» и назначить его (0,0) (номер, для которого сумма длина кратчайших путей к каждой другой комнате наименьшая). Я не знаю, действительно ли это необходимо, но облегчает центрирование вывода.
2. Выйдите из центра C и найдите для каждой комнаты R координату (X, Y), где P - путь, соединяющий C => R, что приводит к наибольшему смещению на координатной плоскости, X - чистый горизонтальный движение по Р и Y представляет собой чистое вертикальное перемещение вдоль P.

Предположат следующие векторы для направлений: Севера = [0,1] Юга = [0, -1] Восток = [1, 0] West = [-1,0]

Answer 1

Это звучит как разумный подход. Я думаю, что существует целый ряд подходов, которые означают выполнение топологического сортирования на графике, а затем обработку узлов по порядку, так что для каждого узла у вас есть место для его размещения, потому что узлы, которые меньше его в топологическом порядке, все с одной стороны от него.

Другой способ просмотра этого топологического вида - не работать из центра, а сформировать ориентированный граф, в котором каждая ссылка направлена ​​либо с севера на юг, либо с востока на запад. Следуя топологическому типу, вы знаете, когда вы размещаете узел, где нет узла, расположенного до севера, или к западу от него, поэтому вы можете назначить его координаты на основе своих восточных и южных соседей.

Если вы хотите, чтобы узлы размещались вокруг начала координат по-прежнему, вы можете изменить их все впоследствии, добавив константу к каждому координирующему значению, чтобы сдвинуть их по желанию.