Работа с циклическими графами в RoR

Question

Я раньше не пытался работать с графиками в Rails, и мне любопытно, как лучше всего это сделать.Немного предыстории:

Я делаю сайт Rails 3 и подумал, что было бы интересно сохранить определенные объекты и их отношения в виде графика, где каждый объект является узлом, а некоторые связаны, чтобы показать, что два объектасвязанные с.Граф содержит циклы, и в нем не будет более 100-150 узлов (вероятно, только ближе к 50).Один узел, вероятно, не будет иметь более пяти ребер, в среднем от трех до четырех ребер на узел.

Я подумал, что простая таблица соединения с двумя столбцами (каждый ID объекта) может быть самой простойспособ сделать это, но я сомневаюсь, что это лучший способ.Другая мысль заключалась в том, чтобы использовать плагин, например acts_as_tree (который, похоже, не обновляется для Rails 3 ...) или acts_as_tree_with_dotted_ids, но я не уверен в их способности работать с циклами, а не с иерархическими деревьями.

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

Совет?Вещи, которые я должен проверить?Спасибо!

Answer 1

В зависимости от того, заботитесь ли вы в первую очередь об операциях с графиками или о хранении графиков, вам может понадобиться совсем другое. Если вам нужны удобные операции с графами, изучите гем "rgl" (библиотека графов ruby). Он имеет реализации большинства основных классических алгоритмов обхода и поиска.

Если вы имеете дело с чем-то порядка 150 узлов, вы, вероятно, можете обойтись без минималистического представления списка смежности в самой базе данных или списка инцидентов. Затем вы можете передать это в RGL для операций обхода и поиска.

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

Answer 2

Я бы использовал две таблицы SQL, node и link, где ссылка - это просто два внешних ключа, исходный и целевой. Таким образом, вы можете получить набор входящих или исходящих ссылок на узел, выполнив запрос выбора SQL, ограничив идентификатор исходного или целевого узла. Вы можете сделать еще один шаг, добавив столбец «graph_id» в обе таблицы, чтобы вы могли извлечь все данные для графика в двух запросах и построить его как этап постобработки.

Эта стратегия должна быть такой же простой (если не простой), как поиск, установка, обучение использованию и реализация плагина для того же, IMHO.

Answer 3

Предполагая, что это ориентированный граф, используйте таблицу сопоставления, например

id | src | dest

, где src и dest - это FK для вашей таблицы объектов.

Если ваши объекты не все одного типа, либо они все должны наследовать класс ruby, либо иметь другую таблицу:

id | type | type_id

Где type - это тип объекта, которым он являетсяи type_id - это его идентификатор в другой таблице.

Выполнив это, вы сможете получить массив объектов для каждого объекта, на который он указывает:

select dest 
from maptable 
where dest = self.id

Есливам нужно знать его входящие ребра, вы можете предварительно выполнить запрос того же типа, используя src вместо dest.

Оттуда вы сможете легко писать любые алгоритмы графиков, которые вам нужны.Если вам нужны веса, вы можете изменить таблицу сопоставления как таковую.

id | src | dest | weight