На мысль дополнить статью Граф(ин) 7.7. меня натолкнула активная дискуссия в теме Реально написать хитрый запрос. Я решил попробовать построить модель ориентированного графа не на справочниках (это статично) на ТЗ с возможностью сделать «разузлование». Начнем.
ТЗ_Дуги будет иметь у нас две колонки «НачУзел» и «КонУзел». Тип - Число (номер строки ТЗ_Узлы).
ТЗ_Узлы заведем с колонками «Содержимое» (тип - Справочник.Некий) и «Количество» (Число). Это для того, чтобы для примера решить задачу, сформулированную в обсуждении Ish_2. Еще две колонки - «ДугиВход» и «ДугиИсход» - это СпискиЗначений (числовых) - номеров строк ТЗ_Дуги.
Справочник Некий по условию имеет реквизиты «Влад» (тип - Справочник.Некий) и «Количество». Разумеется, владельца может и не быть (граф не обязан быть связным).
Процедура Сформировать()
Некий = СоздатьОбъект("Справочник.Некий");
Некий.ВыбратьЭлементы();
Пока Некий.ПолучитьЭлемент() = 1 Цикл
кСтр = 0;
Если ТЗ_Узлы.НайтиЗначение(Некий.ТекущийЭлемент(), кСтр, "Содержимое") = 0 Тогда
ТЗ_Узлы.НоваяСтрока();
ТЗ_Узлы.Содержимое = Некий.ТекущийЭлемент();
ТЗ_Узлы.ДугиВход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.ДугиИсход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.Количество = Некий.Количество;
кСтр = ТЗ_Узлы.КоличествоСтрок();
КонецЕсли;
Если Некий.Влад.Выбран() = 0 Тогда
Продолжить; // Новой дуги не найдено
Иначе //Добавим дугу, конец которой - кСтр
лСтр = 0;
Если ТЗ_Узлы.НайтиЗначение(Некий.Влад, лСтр, "Содержимое") = 0 Тогда
ТЗ_Узлы.НоваяСтрока();
ТЗ_Узлы.Содержимое = Некий.Влад;
ТЗ_Узлы.ДугиВход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.ДугиИсход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.Количество = Некий.Влад.Количество;
лСтр = ТЗ_Узлы.КоличествоСтрок();
КонецЕсли;
//Теперь начало дуги - лСтр
ТЗ_Дуги.НоваяСтрока();
ТЗ_Дуги.НачУзел = лСтр;
ТЗ_Дуги.КонУзел = кСтр;
нДуга = ТЗ_Дуги.КоличествоСтрок();
ТЗУзлы.ПолучитьСтрокуПоНомеру(лСтр);
ТЗ_Узлы.ДугиИсход.Установить("Исход"+нДуга, нДуга);
ТЗ_Узлы.ПолучитьСтрокуПоНомеру(кСтр);
ТЗ_Узлы.ДугиВход.Установить("Вход"+нДуга, нДуга);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Вот, собственно и все. Алгоритмом сложности N*log N мы получили полную картину устройства ссылок в справочнике. Никаких зацикливаний. Никаких ограничений на структуру графа кроме запрета кратных дуг. Один проход. Допускается даже совпадение начального и конечного узлов дуги...
Начало статьи было чисто умозрительным. Однако ж без реального моделирования не обойтись. К тому же Ish_2 предельно конкретизировал задачу: граф представлен набором (справочником) размеченных дуг {НачУзел, КонУзел, Количество}. Рассуждения о деревьях признаны неуместными - только произвольные графы; статья Как не «попасть на миллион» (от ildarovich) "не катит".
Ну что же. Делаем махонькую конфигурацию, заполняем справочник номенклатурных позиций из 1000 наименований (это узлы будущего графа) и начинаем "развлекаться" с дугами. Будем случайным образом строить графы с количеством дуг от 1000 до 5000 и исследовать их на зацикленность. Только добавим еще одно ограничение: длина пути не должна превышать 7, что вполне в рамках упомянутого обсуждения на форуме.
Алгоритм обхода - стандартный "вширь". Надо заметить, что в данных жестких условиях (нет никакой информации о структуре) обходы "вширь" и "вглубь" должны давать одинаковые результаты, поскольку требуется перечислить все пути, а не просто побывать в каждой вершине или на каждой дуге.
В приведенной конфигурации в качестве перечня путей используется СписокЗначений - Строк (номера вершин с разделителями).
Разузловываются все вершины, не имеющие предков.
На последнем скрине приведены (в секундах) времена поиска циклов и последующего разузлования.
