Комментарии 22
просто скажите мне почему все рекомендуют использовать граф БД для соц сетей? в 99% задач , например найти пересечение друг друзей друга это пересечение SET'OV
Использую аналогичный подход, когда графы в постгресе. Только с 2-мя отличающимися нюансами, которые, возможно, вам будут полезны:
WHERE g.node1 = sg.node2
AND not (g.node1 = ANY(sg.path)) -- тоже самое, но останавливаемся на первом вхождении
AND ((sg.depth = 1)
or (sg.depth > 2 and sg.node1 > g.node1)
) -- исключаем логические повторы
-- актуально если 30 2 3 1003 и 30 3 2 1003 - одно и тоже
-- оставляем только одну последовательность (30 2 3 1003)
Здравствуйте! Добавление виртуального графа создает аналог прямой связи между узлами одного и того же столбца. В оригинальном графе они связаны лишь через крайний узел и узлы соседнего столбца. Разве не так?
Добрый день, а https://postgrespro.ru/docs/postgresql/14/datatype-bit пробовали?
Для постгресса есть расширение pgRouting. Им конечно в основном географы пользуются, но работает на произвольных графах, и там есть алгоритм pgr_connectedComponents, вычисляющий связанность. Описанную в начале схему по-моему можно без изменений ему скормить. Интересно, насколько быстрее / медленнее.
Вынос общего множителя всегда упрощает решение, главное правильно вынести!
© Конфуций
Для графовых БД есть такой https://tinkerpop.apache.org/gremlin.html - язык обхода графов. Для PostreSQL нету, а вот MS для новой CosmosDB реализовал. Про призводительность не знаю.
Но с производительностью использование диалекта связывать смысла не имеет. Важно что у вас за движок выполняет запросы. Но вот читабельность кода будет ясно выше, поэтому такие диалекты и изобретают.
Полюбопытствовал - Гремлин имеет вид FluentAPI, а вот Cypher больше похож на SQL. Есть даже старый транслятор от openCypher - https://github.com/opencypher/cypher-for-gremlin
Я бы попробовал на плюсах написать простой прототип (или на numpy, или на любом языке с массивами и векторизацией) и использовал как бенчмарк. Может оказаться, что никакой multi-tier и не понадобится. Человечество начинает забывать какими быстрыми могут быть программы без проводов и баз данных.
Спасибо за статью.
Чтобы свернуть так граф, которые приведены в решении - нужен полносвязный участок, на рискнках не такой (на них граф с полным двудольным подграфом).
На первом рисунке (я пронумеровал вершины), чтобы попасть в вершину 2 из 1 надо одно ребро пройти. А чтобы в 3 из 1 - надо пройти 2 ребра. На второй картинке у вас получается одинаковое расстояние - 2 ребра (через виртуальный узел).
P.S. Если ориентировать ребра ("от" виртуального и "к"), то можно свернуть так, как на рисунке и потом иметь возможность получить исходный граф (считать связью только "к"+"от" и "от"+"к")
Зависит от того направленный граф или нет. Я изначалько подразумевал направленный граф, но стрелочки загромождают схему. :) Поправлю схемы чуть позже... На суть это не сильно влияет.
Ускоряем работу с графами в 20000 раз