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

У меня есть набор комнат, каждая из которых связана с одной или несколькими другими комнатами по сторонам света (север, юг, восток, запад). Комнаты были соединены таким образом, что если 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]

Вот пример правильного вывода, который мне удалось получить. К сожалению, другие графики не были полностью успешными.


path graph algorithm undirected-graph shortest-path
person Taylor    schedule 12.01.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

person mcdowella    schedule 12.01.2017
comment
Во-первых, большое спасибо за ваш вклад. Я раньше сталкивался с топологической сортировкой в ​​своих исследованиях и думал, что она применима только к DAG. Вы просто хотите притвориться, что график является DAG для целей алгоритма? - person Taylor; 12.01.2017
comment
@Taylor: да, говоря, что ссылка Север-Юг - это направленная ссылка, указывающая на Север, и говоря, что ссылка Восток-Запад - это направленная ссылка, указывающая на Запад. - person mcdowella; 12.01.2017