Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Обход ненаправленного графа с циклическими связями  [new]
Totos
Member

Откуда: Калуга
Сообщений: 193
Есть граф, характеризующий связи между организациями на основании взаимоотношений владения.

При этом возможно:
- как перекрестное владение (А владеет Б и Б владеет А),
- так и кольцевое владение (А владеет Б, Б владеет С, С владеет А).

Требуется: для конкретной организации А узнать всех её прямых и косвенных владельцев.


Рассматривал следующие варианты реализации:

Вариант 1: При помощи конструкции WITH Recursive - не подошел (или я не смог) из-за наличия петель;

Вариант 2: Есть вариантный организации дерева при помощи типа данных HierarchyID,
но для меня это пока сложно (не являюсь специализированным программистом MS SQL), нет времени на детальное изучение (конкретная задача - короткие сроки), не уверен, что мне подойдет (на основании поверхностного изучения сложилось мнение, что данный тип подходит для деревьев).

Вариант 3: Создать рекурсивную функцию в которую передавать список уже пройденных узлов
и проверять их на каждой итерации для исключения возможности зацикливания. Идентификаторы организаций передавать в виде строки, разделенной запятыми (потом разбирать строку - парсить).

Пока остановился на Варианте №3, но может кто-нибудь подскажет более оптимальное решение, если есть ?

Спасибо.
25 авг 17, 11:49    [20748846]     Ответить | Цитировать Сообщить модератору
 Re: Обход ненаправленного графа с циклическими связями  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20538
Totos
Вариант 1: При помощи конструкции WITH Recursive - не подошел (или я не смог) из-за наличия петель;
Вероятно, Вы на очередном шаге рекурсии не отсеиваете те узлы, которые обработаны на предыдущих витках рекурсии.
25 авг 17, 12:37    [20749025]     Ответить | Цитировать Сообщить модератору
 Re: Обход ненаправленного графа с циклическими связями  [new]
Дедушка
Member

Откуда: Город трёх революций
Сообщений: 5111
Totos,

Вариант 0: прочитать про алгоритмы на графах, выбрать подходящий и потом реализовывать
25 авг 17, 13:09    [20749118]     Ответить | Цитировать Сообщить модератору
 Re: Обход ненаправленного графа с циклическими связями  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3712
Totos
Есть граф, характеризующий связи между организациями на основании взаимоотношений владения.

При этом возможно:
- как перекрестное владение (А владеет Б и Б владеет А),
- так и кольцевое владение (А владеет Б, Б владеет С, С владеет А).

Требуется: для конкретной организации А узнать всех её прямых и косвенных владельцев.


Рассматривал следующие варианты реализации:

Вариант 1: При помощи конструкции WITH Recursive - не подошел (или я не смог) из-за наличия петель;

Вариант 2: Есть вариантный организации дерева при помощи типа данных HierarchyID,
но для меня это пока сложно (не являюсь специализированным программистом MS SQL), нет времени на детальное изучение (конкретная задача - короткие сроки), не уверен, что мне подойдет (на основании поверхностного изучения сложилось мнение, что данный тип подходит для деревьев).

Вариант 3: Создать рекурсивную функцию в которую передавать список уже пройденных узлов
и проверять их на каждой итерации для исключения возможности зацикливания. Идентификаторы организаций передавать в виде строки, разделенной запятыми (потом разбирать строку - парсить).

Пока остановился на Варианте №3, но может кто-нибудь подскажет более оптимальное решение, если есть ?

Спасибо.


Вам бы немного вникнуть в математику, какую-нибудь теориь графов для чайников хотя бы.

А потом установить SQLServer 2017, там есть функционал для обработки графов
25 авг 17, 13:15    [20749138]     Ответить | Цитировать Сообщить модератору
 Re: Обход ненаправленного графа с циклическими связями  [new]
aleks222
Guest
Totos
может кто-нибудь подскажет более оптимальное решение, если есть ?

Спасибо.


Наиболее оптимальным решением является "описание желаемой формы представления результата".

После чего все становится тривиальным.
25 авг 17, 13:43    [20749248]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить