На мысль дополнить статью Граф(ин) 7.7. меня натолкнула активная дискуссия в теме Реально написать хитрый запрос. Я решил попробовать построить модель ориентированного графа не на справочниках (это статично) на ТЗ с возможностью сделать «разузлование». Начнем.
ТЗ_Дуги будет иметь у нас две колонки «НачУзел» и «КонУзел». Тип — Число (номер строки ТЗ_Узлы).
ТЗ_Узлы заведем с колонками «Содержимое» (тип — Справочник.Некий) и «Количество» (Число). Это для того, чтобы для примера решить задачу, сформулированную в обсуждении Ish_2. Еще две колонки — «ДугиВход» и «ДугиИсход» — это СпискиЗначений (числовых) — номеров строк ТЗ_Дуги.
Справочник Некий по условию имеет реквизиты «Влад» (тип — Справочник.Некий) и «Количество». Разумеется, владельца может и не быть (граф не обязан быть связным).
Процедура Сформировать()
Некий = СоздатьОбъект("Справочник.Некий");
Некий.ВыбратьЭлементы();
Пока Некий.ПолучитьЭлемент() = 1 Цикл
кСтр = 0;
Если ТЗ_Узлы.НайтиЗначение(Некий.ТекущийЭлемент(), кСтр, "Содержимое") = 0 Тогда
ТЗ_Узлы.НоваяСтрока();
ТЗ_Узлы.Содержимое = Некий.ТекущийЭлемент();
ТЗ_Узлы.ДугиВход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.ДугиИсход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.Количество = Некий.Количество;
кСтр = ТЗ_Узлы.КоличествоСтрок();
КонецЕсли;
Если Некий.Влад.Выбран() = 0 Тогда
Продолжить; // Новой дуги не найдено
Иначе //Добавим дугу, конец которой - кСтр
лСтр = 0;
Если ТЗ_Узлы.НайтиЗначение(Некий.Влад, лСтр, "Содержимое") = 0 Тогда
ТЗ_Узлы.НоваяСтрока();
ТЗ_Узлы.Содержимое = Некий.Влад;
ТЗ_Узлы.ДугиВход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.ДугиИсход = СоздатьОбъект("СписокЗначений");
ТЗ_Узлы.Количество = Некий.Влад.Количество;
лСтр = ТЗ_Узлы.КоличествоСтрок();
КонецЕсли;
//Теперь начало дуги - лСтр
ТЗ_Дуги.НоваяСтрока();
ТЗ_Дуги.НачУзел = лСтр;
ТЗ_Дуги.КонУзел = кСтр;
нДуга = ТЗ_Дуги.КоличествоСтрок();
ТЗУзлы.ПолучитьСтрокуПоНомеру(лСтр);
ТЗ_Узлы.ДугиИсход.Установить("Исход"+нДуга, нДуга);
ТЗ_Узлы.ПолучитьСтрокуПоНомеру(кСтр);
ТЗ_Узлы.ДугиВход.Установить("Вход"+нДуга, нДуга);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Вот, собственно и все. Алгоритмом сложности N*log N мы получили полную картину устройства ссылок в справочнике. Никаких зацикливаний. Никаких ограничений на структуру графа кроме запрета кратных дуг. Один проход. Допускается даже совпадение начального и конечного узлов дуги…
Начало статьи было чисто умозрительным. Однако ж без реального моделирования не обойтись. К тому же Ish_2 предельно конкретизировал задачу: граф представлен набором (справочником) размеченных дуг {НачУзел, КонУзел, Количество}. Рассуждения о деревьях признаны неуместными — только произвольные графы; статья Как не «попасть на миллион» (от ildarovich) «не катит».
Ну что же. Делаем махонькую конфигурацию, заполняем справочник номенклатурных позиций из 1000 наименований (это узлы будущего графа) и начинаем «развлекаться» с дугами. Будем случайным образом строить графы с количеством дуг от 1000 до 5000 и исследовать их на зацикленность. Только добавим еще одно ограничение: длина пути не должна превышать 7, что вполне в рамках упомянутого обсуждения на форуме.
Алгоритм обхода — стандартный «вширь». Надо заметить, что в данных жестких условиях (нет никакой информации о структуре) обходы «вширь» и «вглубь» должны давать одинаковые результаты, поскольку требуется перечислить все пути, а не просто побывать в каждой вершине или на каждой дуге.
В приведенной конфигурации в качестве перечня путей используется СписокЗначений — Строк (номера вершин с разделителями).
Разузловываются все вершины, не имеющие предков.
На последнем скрине приведены (в секундах) времена поиска циклов и последующего разузлования.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Я правильно понимаю, на скринах представлены составляющие спецификации?
(1) Не только. В спецификации циклы недопустимы, тк что там сломается и циклический запрос и рекурсия. А тут я даю механизм анализа существующего справочника с реквизитом-ссылкой на собственный элемент. Если этот справочник представляет собой спецификацию — то это способ проверки корректности спецификации. Если справочник представляет схему (алгоритм) вычислений, управляемых данными (в идеологии Дракона) то модно «замутить» что-то с оптимизацией вычислений. Обход деревьев тоже легко отсюда строится. И т.д.
Замечания.
1. Задача без тестового примера — ничто.
2. Эта задача, старая как мир, имеет множество вариантов и реализаций решения .
3. Очередная реализация , без объяснения её преимуществ бессмысленна.
Например, ИНТЕРЕС ПРЕДСТАВЛЯЕТ реализация , дающая максимальное быстродействие для очень больших деревьев.
Сделай себе миллион узлов ( по примеру
по схеме подчинения в 7 уровней 1-10-10-10-10-10-10 и расскажи нам о быстродействии.
У Владимира это заняло 3 мин. А у тебя ?
Или покажи в чем какие-то другие преимущества твоей реализации.
Александр.
Ставлю плюс на эту статью. И на предыдущую — плюс.
И огромный минус за игнорирование слова «запрос» в теме форума. 😉
Т.к. «китайскими палочками»(с) любой алгоритм трудно «кушать».
Кроме выходных (внешних) форм.
Какой инструмент — такой и результат. 🙁
Но результатов много… 😉
(3)
Игорь.
А вдруг у Александра используется DBF-ная версия 1С-а в локальном (терминальном) режиме. А компьютер собран на процессоре AMD — эти процессоры лучше работают на наших задачах. Тогда он, точно, побьет наши достижения в минутах. 😉
Не надо пугать людей «минутами». Не все будут читать тему форума в 100 сообщений. И могут решить, что я выжил из ума на старости лет — сравниваю скорости процессоров Вашей и своей машины. 😉
P.S. Прошу прощения у Автора публикации за данное, моё, сообщение. Но, уж…
(5) Именно DBF 😀 Локально — чего мне по серверам толкаться с тестовой базой. Процессор, правда Intel Core2.
(4) Запрос сам по себе мне неинтересен, тем более, что он, похоже и не сработает без предварительных проверок структуры графа. Интересно моделирование данных. В свое время довелось заниматься автоматизацией распараллеливания вычислений, основанной на графах. Узел графа — вычислительный модуль, дуга — таблица данных. По готовности входов — выделение модулю процессора и запуск. Ностальгия, однако.
(0) Мне кажется, следует четче определить назначение процедуры Сформировать().
Ведь на самом деле в ней происходит только преобразования информации о связях графа из таблицы справочника в таблицу значений. Никакие другие прикладные задачи при этом не решаются, то есть это всего лишь подготовительный этап перед применением любого алгоритма на графах с использованием таблицы значений. К тому же получаемая информация трижды избыточна: информационной достаточностью будет обладать сама по себе таблица ТЗ_Дуги, или одна таблица ТЗ_Узлы, в которой заполнена только колонка ДугиВход, а также таблица ТЗ_Узлы, где заполнена только колонка ДугиИсход. Любая из этих таблиц позволит восстановить остальные.
Понятно, что избыточность позволит ускорить некоторые алгоритмы, но без их указания все эти таблицы вместе не кажутся необходимыми.
(7)
ТЗ_Дуги и в самом деле дает полное представление о топологии графа, и в ТЗ_Узлы колонки ДугиВход и ДугиИсход избыточны. Это наследие описанного в 6 посте 🙂
(3)
Я, вообще-то не о деревьях писал, а о произвольных графах, «запрятанных», в частности, в справочниках из темы форума. А если точно известно, что исследуемый граф — это дерево, задача существенно упрощается. Вот цитата по ссылке
При прочих равных условиях выполнение кода с использованием рекурсии заняло 0,086753 секунды, выполнение кода с использованием нескольких вложенных циклов – 0,050159 секунды, выполнение кода поуровневого обхода дерева – 0,087718 секунды.
Отмечу только, что я-то предлагал в комментариях текст семерочный.
(9) Поймал. Конечно, речь идет о произвольном графе.
Вот я и отбираю алгоритмы и их реализации для СУБД. Как ты догадываешься , их в интернете вагон и маленькая тележка.
1 . Первым важнейшим критерием отбора , конечно, является их эффективность (быстродействие).
2. Вторым важнейшим критерием отбора , конечно , является наличие эффективного контроля зацикливания.
Я смотрю на твою обработку и думаю : Зачем она ? Что в ней такого ?
Ты ни слова не написал
по этим двум пунктампо первому пункту.Получается , что автор выставил свою обработку просто так … дескать , а можно и вот так . Я пожимаю плечами : пожалуй , можно … и что ?
Вот если бы ты привел реализовал тест для графа из форума 1-10-10-10-10-10-10.
Мы бы обсудили что-то по первому пункту — чем хорош твой алгоритм.
(10) В качестве первого критерия я бы все же указал работоспособность. Очень эффективные неработающие алгоритмы меня как-то не прельщают.
Моя обработка эффективно фиксирует топологию графа. Такой же алгоритм можно запускать в процедуре ПриЗаписи справочника Некий для блокировки зацикливания. Ну, а если циклов гарантированно не будет, тогда уж можно начинать искать алгоритм по второму важнейшему критерию — быстродействию.
(11) Работоспособность — как критерий идет нулевым номером , который опускается по умолчанию ,как само собой разумеещееся. Хм.. ты рассматриваешь работоспособность как некое достижение ?
Как это ? Нашли алгоритм , который работоспособен , добились удаления зациклинности и … пошли искать другой алгоритм ? более эффективный ?
(12) Займемся цитированием. Тебя
29.
Ish_2 02.11.10 22:02
Грамотные , значит… Вы тут меня не пугайте : «ациклический граф», «динамические списки», «такого не может быть!»…
Может .
Даёшь «Циклический граф» и «Адинамические списки» !
В этом ВСЯ СОЛЬ ЗАДАЧИ . В узлах могут быть ЛЮБЫЕ Элементы.
Отсылаю вас к справочнику СпецификацияНоменклатуры в БП 1.6.
Задача из тривиальной превращается в нечто интересное.
И это нечто я собираюсь решать. Без рекурсии. Только средствами 1с.
Будем надеяться , всё получится .
32.
Ish_2 02.11.10 22:56
Дана таблица
Владелец , Номенклатура, Количество.
Колонки Владелец и Номенклатура — одного типа . Таблица заполнена одному Богу известно как.
Для выбранной пользователем Номенклатуры нужно получить получить плоскую таблицу
Номенклатура , Количество. Т.е раскрутить дерево до элементов , которые не имеют подчиненных(«детей»).
Так вот, если ты допускаешь циклы, то забудь про дерево. И обязательно надо получить структуру графа. В этом СОЛЬ задачи (которая у меня решена): получить юзабельную модель данных. Обойти граф известной структуры — это уже дело техники. Обойти дерево — дело простой техники.
(13) Опять поймал. На смешении понятий «дерева» и «графа».
Но замени «дерево» на «граф» и все встанет на свои места.
В моей таблице СпецификацииНоменклатуры с колонками Владелец, Номенклатура,Количество граф уже описан
самым полным образом. Зачем мне находить его структуру ? Она уже есть .
СОЛЬ ЗАДАЧИ в том , что его( граф-таблицу) нужно обходить сразу , одновременно решая задачу разузлования и контроля зацикленности.
Иначе алгоритм получится жутким и неэффективным.
(14) У нас подходы разные. Задача разузлования в циклическом графе решения не имеет. Я проверяю зацикленность и отказываюсь от решения. Ты же предлагаешь действовать по понятиям Кристобаля Хозевича Хунты, которому было западло заниматься задачами, имеющими решение. Начнем, мол, решать, и поэффективнее (побыстрее) зайдем в тупик (цикл). Ну, Хунта — маг и романтик. Но и он бы не стал искать решение неразрешимой, возможно, задачи средствами 1С.
Это трусость.
Сравни : Я устанавливаю зацикленность данной ветки — ставлю стопор и продолжаю движение по другой ветке. И в итоге на выходе имею
1. список всех зацикленных веток (граф ошибок)
2. плоскую таблицу разузлования ( в которой могут присутствовать ошибочные номенклатуры , т.е. номенклатуры с признаком стопора)
Почувствуй разницу.
P.S. ты не думай , я веду граф в красной книжице как ты меня обозвал.
Новая Запись — «Хунта» ( пока незацикленная)
Браво !
(ты уж прости меня — я подумал , что ты дрогнул)