Граф(ин) 7.7. (дополнение)

22.11.10

Разработка - Математика и алгоритмы

Строим ориентированные графы.

Скачать файлы

Наименование Файл Версия Размер
Сохраненная конфигурация
.zip 45,56Kb
19
.zip 45,56Kb 19 Скачать

На мысль дополнить статью Граф(ин) 7.7. меня натолкнула активная дискуссия в теме Реально написать хитрый запрос. Я решил попробовать построить модель ориентированного графа не на справочниках (это статично) на ТЗ с возможностью сделать «разузлование». Начнем.

ТЗ_Дуги будет иметь у нас две колонки «НачУзел» и «КонУзел». Тип - Число (номер строки ТЗ_Узлы).

ТЗ_Узлы заведем с колонками «Содержимое» (тип - Справочник.Некий) и «Количество» (Число). Это для того, чтобы для примера решить задачу, сформулированную в обсуждении Ish_2. Еще две колонки - «ДугиВход» и «ДугиИсход» - это СпискиЗначений (числовых) - номеров строк ТЗ_Дуги.

Справочник Некий по условию имеет реквизиты «Влад» (тип - Справочник.Некий) и «Количество». Разумеется, владельца может и не быть (граф не обязан быть связным).

	 Процедура Сформировать()
    Некий = СоздатьОбъект("Справочник.Некий");
    Некий.ВыбратьЭлементы();
    Пока Некий.ПолучитьЭлемент() = 1 Цикл
        кСтр = 0;
        Если ТЗ_Узлы.НайтиЗначение(Некий.ТекущийЭлемент(), кСтр, "Содержимое") = 0 Тогда
            ТЗ_Узлы.НоваяСтрока();
            ТЗ_Узлы.Содержимое = Некий.ТекущийЭлемент();
            ТЗ_Узлы.ДугиВход = СоздатьОбъект("СписокЗначений");
            ТЗ_Узлы.ДугиИсход = СоздатьОбъект("СписокЗначений");
            ТЗ_Узлы.Количество = Некий.Количество;
            кСтр = ТЗ_Узлы.КоличествоСтрок();
        КонецЕсли;
        Если Некий.Влад.Выбран() = 0 Тогда
            Продолжить; // Новой дуги не найдено
        Иначе //Добавим дугу, конец которой - кСтр
            лСтр = 0;
            Если ТЗ_Узлы.НайтиЗначение(Некий.Влад, лСтр, "Содержимое") = 0 Тогда
                ТЗ_Узлы.НоваяСтрока();
                ТЗ_Узлы.Содержимое = Некий.Влад;
                ТЗ_Узлы.ДугиВход = СоздатьОбъект("СписокЗначений");
                ТЗ_Узлы.ДугиИсход = СоздатьОбъект("СписокЗначений");
                ТЗ_Узлы.Количество = Некий.Влад.Количество;
                лСтр = ТЗ_Узлы.КоличествоСтрок();
            КонецЕсли;
            //Теперь начало дуги - лСтр
            ТЗ_Дуги.НоваяСтрока();
            ТЗ_Дуги.НачУзел = лСтр;
            ТЗ_Дуги.КонУзел = кСтр;
            нДуга = ТЗ_Дуги.КоличествоСтрок();
            ТЗУзлы.ПолучитьСтрокуПоНомеру(лСтр);
            ТЗ_Узлы.ДугиИсход.Установить("Исход"+нДуга, нДуга);
            ТЗ_Узлы.ПолучитьСтрокуПоНомеру(кСтр);
            ТЗ_Узлы.ДугиВход.Установить("Вход"+нДуга, нДуга);
        КонецЕсли;
    КонецЦикла;
КонецПроцедуры

Вот, собственно и все. Алгоритмом сложности  N*log N мы получили полную картину устройства ссылок в справочнике. Никаких зацикливаний. Никаких ограничений на структуру графа кроме запрета кратных дуг. Один проход. Допускается даже совпадение начального и конечного узлов дуги...

Начало статьи было чисто умозрительным. Однако ж без реального моделирования не обойтись. К тому же Ish_2 предельно конкретизировал задачу: граф представлен набором (справочником) размеченных дуг {НачУзел, КонУзел, Количество}. Рассуждения о деревьях признаны неуместными - только произвольные графы; статья Как не «попасть на миллион» (от ildarovich) "не катит".

Ну что же. Делаем махонькую конфигурацию, заполняем справочник номенклатурных позиций из 1000 наименований (это узлы будущего графа) и начинаем "развлекаться" с дугами. Будем случайным образом строить графы с количеством дуг от 1000 до 5000 и исследовать их на зацикленность. Только добавим еще одно ограничение: длина пути не должна превышать 7, что вполне в рамках упомянутого обсуждения на форуме.

Алгоритм обхода - стандартный "вширь". Надо заметить, что в данных жестких условиях (нет никакой информации о структуре) обходы "вширь" и "вглубь" должны давать одинаковые результаты, поскольку требуется перечислить все пути, а не просто побывать в каждой вершине или на каждой дуге.

В приведенной конфигурации в качестве перечня путей используется СписокЗначений - Строк (номера вершин с разделителями). 

Разузловываются все вершины, не имеющие предков.

На последнем скрине приведены (в секундах) времена поиска циклов и последующего разузлования. 


См. также

Библиотека процедур и функций для технологической платформы "1С: Предприятие 7.7"

Универсальные функции Платформа 1С v7.7 Россия Абонемент ($m)

В библиотеку собраны различные функции по работе с документами, журналами, типами данных, строками, датой и временем, таблицами значений, Excel, файлами, XML, JSON, Http-сервисами, SMTP серверами и т.п.

1 стартмани

22.12.2023    657    9    user706545_kseg1971    0    

4

1С 7.7 и новый 1С:Контрагент

Универсальные функции Платформа 1С v7.7 Конфигурации 1cv7 Россия Бесплатно (free)

Получение реквизитов контрагентов из 1С:Контрагент для старых конфигураций под 1с 7.7.

25.04.2022    1820    zhenyat    7    

6

Печать таблицы значений в 1С 7.7 при отладке

Универсальные функции Платформа 1С v7.7 Россия Бесплатно (free)

Функция выводит таблицу значений в табличный документ. (v7.7) Особенно полезно при отладке. Не нужно вносить изменения в код, вызываем функцию как вычисляемое выражение при останове. Если таблица обрабатывается в несколько этапов, можно вывести её после каждого и визуально проследить эволюцию.

30.06.2021    4399    Zoltan_Black    11    

2

Установка принтера по умолчанию для 1С 7.7

Универсальные функции Платформа 1С v7.7 Конфигурации 1cv7 Абонемент ($m)

Установка принтера по умолчанию в 1С 7.7. Обработка может быть полезна в том случае, когда нужно установить принтер по умолчанию, а доступа к рабочему столу нет (например, терминальный режим без рабочего стола или remoteApp)

1 стартмани

13.02.2019    13286    4    alsen    3    

4

Формирование строки json в 1С: 7.7

Универсальные функции Платформа 1С v7.7 Конфигурации 1cv7 1С:Комплексная 7.7 Абонемент ($m)

Предлагается набор функций 1с 7.7 для формирования строки json стандартными средствами.

1 стартмани

10.12.2018    10096    malovandrey    2    

18

Как создать индикатор в 1С:Предприятии 7.7

Универсальные функции Работа с интерфейсом Платформа 1С v7.7 Конфигурации 1cv7 Россия Абонемент ($m)

В статье дано описание создания индикатора на форме в среде разработки 1С:Предприятие 7.7 исключительно типовыми средствами.

1 стартмани

27.09.2016    18672    2    HAMMER_59    6    

2
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Alraune 1502 13.11.10 15:25 Сейчас в теме
Я правильно понимаю, на скринах представлены составляющие спецификации?
2. Арчибальд 2706 13.11.10 15:45 Сейчас в теме
(1) Не только. В спецификации циклы недопустимы, тк что там сломается и циклический запрос и рекурсия. А тут я даю механизм анализа существующего справочника с реквизитом-ссылкой на собственный элемент. Если этот справочник представляет собой спецификацию - то это способ проверки корректности спецификации. Если справочник представляет схему (алгоритм) вычислений, управляемых данными (в идеологии Дракона) то модно "замутить" что-то с оптимизацией вычислений. Обход деревьев тоже легко отсюда строится. И т.д.
3. Ish_2 1104 13.11.10 17:41 Сейчас в теме
Замечания.
1. Задача без тестового примера - ничто.
2. Эта задача, старая как мир, имеет множество вариантов и реализаций решения .
3. Очередная реализация , без объяснения её преимуществ бессмысленна.

Например, ИНТЕРЕС ПРЕДСТАВЛЯЕТ реализация , дающая максимальное быстродействие для очень больших деревьев.

Сделай себе миллион узлов ( по примеру http://infostart.ru/forum/forum14/topic35991/
по схеме подчинения в 7 уровней 1-10-10-10-10-10-10 и расскажи нам о быстродействии.
У Владимира это заняло 3 мин. А у тебя ?

Или покажи в чем какие-то другие преимущества твоей реализации.



5. hogik 443 14.11.10 02:45 Сейчас в теме
(3)
Игорь.
А вдруг у Александра используется DBF-ная версия 1С-а в локальном (терминальном) режиме. А компьютер собран на процессоре AMD - эти процессоры лучше работают на наших задачах. Тогда он, точно, побьет наши достижения в минутах. ;-)
Не надо пугать людей "минутами". Не все будут читать тему форума в 100 сообщений. И могут решить, что я выжил из ума на старости лет - сравниваю скорости процессоров Вашей и своей машины. ;-)
P.S. Прошу прощения у Автора публикации за данное, моё, сообщение. Но, уж...
6. Арчибальд 2706 14.11.10 11:28 Сейчас в теме
(5) Именно DBF :D Локально - чего мне по серверам толкаться с тестовой базой. Процессор, правда Intel Core2.
(4) Запрос сам по себе мне неинтересен, тем более, что он, похоже и не сработает без предварительных проверок структуры графа. Интересно моделирование данных. В свое время довелось заниматься автоматизацией распараллеливания вычислений, основанной на графах. Узел графа - вычислительный модуль, дуга - таблица данных. По готовности входов - выделение модулю процессора и запуск. Ностальгия, однако.
9. Арчибальд 2706 15.11.10 08:34 Сейчас в теме
(3)
Например, ИНТЕРЕС ПРЕДСТАВЛЯЕТ реализация , дающая максимальное быстродействие для очень больших деревьев.
Я, вообще-то не о деревьях писал, а о произвольных графах, "запрятанных", в частности, в справочниках из темы форума. А если точно известно, что исследуемый граф - это дерево, задача существенно упрощается. Вот цитата по ссылке http://infostart.ru/public/20797/
Впрочем, использование рекурсии не является единственным решением для этой задачи. Существует еще один оригинальный алгоритм - поуровневый обход дерева (предложен Арчибальдом).
При прочих равных условиях выполнение кода с использованием рекурсии заняло 0,086753 секунды, выполнение кода с использованием нескольких вложенных циклов – 0,050159 секунды, выполнение кода поуровневого обхода дерева – 0,087718 секунды.
Отмечу только, что я-то предлагал в комментариях текст семерочный.
10. Ish_2 1104 15.11.10 09:00 Сейчас в теме
(9) Поймал. Конечно, речь идет о произвольном графе.
Вот я и отбираю алгоритмы и их реализации для СУБД. Как ты догадываешься , их в интернете вагон и маленькая тележка.

1 . Первым важнейшим критерием отбора , конечно, является их эффективность (быстродействие).
2. Вторым важнейшим критерием отбора , конечно , является наличие эффективного контроля зацикливания.

Я смотрю на твою обработку и думаю : Зачем она ? Что в ней такого ?
Ты ни слова не написал по этим двум пунктам по первому пункту.
Получается , что автор выставил свою обработку просто так ... дескать , а можно и вот так . Я пожимаю плечами : пожалуй , можно ... и что ?

Вот если бы ты привел реализовал тест для графа из форума 1-10-10-10-10-10-10.
Мы бы обсудили что-то по первому пункту - чем хорош твой алгоритм.
11. Арчибальд 2706 15.11.10 09:38 Сейчас в теме
(10) В качестве первого критерия я бы все же указал работоспособность. Очень эффективные неработающие алгоритмы меня как-то не прельщают.
Моя обработка эффективно фиксирует топологию графа. Такой же алгоритм можно запускать в процедуре ПриЗаписи справочника Некий для блокировки зацикливания. Ну, а если циклов гарантированно не будет, тогда уж можно начинать искать алгоритм по второму важнейшему критерию - быстродействию.
12. Ish_2 1104 15.11.10 10:17 Сейчас в теме
(11) Работоспособность - как критерий идет нулевым номером , который опускается по умолчанию ,как само собой разумеещееся. Хм.. ты рассматриваешь работоспособность как некое достижение ?
Ну, а если циклов гарантированно не будет, тогда уж можно начинать искать алгоритм по второму важнейшему критерию - быстродействию.


Как это ? Нашли алгоритм , который работоспособен , добились удаления зациклинности и ... пошли искать другой алгоритм ? более эффективный ?
13. Арчибальд 2706 15.11.10 10:35 Сейчас в теме
(12) Займемся цитированием. Тебя
29.

Ish_2 02.11.10 22:02

Грамотные , значит... Вы тут меня не пугайте : "ациклический граф", "динамические списки", "такого не может быть!"...
Может .
Даёшь "Циклический граф" и "Адинамические списки" !
В этом ВСЯ СОЛЬ ЗАДАЧИ . В узлах могут быть ЛЮБЫЕ Элементы.
Отсылаю вас к справочнику СпецификацияНоменклатуры в БП 1.6.
Задача из тривиальной превращается в нечто интересное.
И это нечто я собираюсь решать. Без рекурсии. Только средствами 1с.
Будем надеяться , всё получится .
32.

Ish_2 02.11.10 22:56

Дана таблица
Владелец , Номенклатура, Количество.

Колонки Владелец и Номенклатура - одного типа . Таблица заполнена одному Богу известно как.
Для выбранной пользователем Номенклатуры нужно получить получить плоскую таблицу
Номенклатура , Количество. Т.е раскрутить дерево до элементов , которые не имеют подчиненных("детей").

Так вот, если ты допускаешь циклы, то забудь про дерево. И обязательно надо получить структуру графа. В этом СОЛЬ задачи (которая у меня решена): получить юзабельную модель данных. Обойти граф известной структуры - это уже дело техники. Обойти дерево - дело простой техники.
14. Ish_2 1104 15.11.10 10:51 Сейчас в теме
(13) Опять поймал. На смешении понятий "дерева" и "графа".
Но замени "дерево" на "граф" и все встанет на свои места.

И обязательно надо получить структуру графа. В этом СОЛЬ задачи (которая у меня решена): получить юзабельную модель данных.


В моей таблице СпецификацииНоменклатуры с колонками Владелец, Номенклатура,Количество граф уже описан
самым полным образом. Зачем мне находить его структуру ? Она уже есть .
СОЛЬ ЗАДАЧИ в том , что его( граф-таблицу) нужно обходить сразу , одновременно решая задачу разузлования и контроля зацикленности.
Иначе алгоритм получится жутким и неэффективным.
15. Арчибальд 2706 15.11.10 11:15 Сейчас в теме
(14) У нас подходы разные. Задача разузлования в циклическом графе решения не имеет. Я проверяю зацикленность и отказываюсь от решения. Ты же предлагаешь действовать по понятиям Кристобаля Хозевича Хунты, которому было западло заниматься задачами, имеющими решение. Начнем, мол, решать, и поэффективнее (побыстрее) зайдем в тупик (цикл). Ну, Хунта - маг и романтик. Но и он бы не стал искать решение неразрешимой, возможно, задачи средствами 1С.
4. hogik 443 13.11.10 20:45 Сейчас в теме
Александр.
Ставлю плюс на эту статью. И на предыдущую - плюс.
И огромный минус за игнорирование слова "запрос" в теме форума. ;-)
Т.к. "китайскими палочками"(с) любой алгоритм трудно "кушать".
Кроме выходных (внешних) форм.
Какой инструмент - такой и результат. :-(
Но результатов много... ;-)

7. ildarovich 7850 15.11.10 01:07 Сейчас в теме
(0) Мне кажется, следует четче определить назначение процедуры Сформировать().
Ведь на самом деле в ней происходит только преобразования информации о связях графа из таблицы справочника в таблицу значений. Никакие другие прикладные задачи при этом не решаются, то есть это всего лишь подготовительный этап перед применением любого алгоритма на графах с использованием таблицы значений. К тому же получаемая информация трижды избыточна: информационной достаточностью будет обладать сама по себе таблица ТЗ_Дуги, или одна таблица ТЗ_Узлы, в которой заполнена только колонка ДугиВход, а также таблица ТЗ_Узлы, где заполнена только колонка ДугиИсход. Любая из этих таблиц позволит восстановить остальные.
Понятно, что избыточность позволит ускорить некоторые алгоритмы, но без их указания все эти таблицы вместе не кажутся необходимыми.
Арчибальд; +1 Ответить
8. Арчибальд 2706 15.11.10 07:51 Сейчас в теме
(7)
Любая из этих таблиц позволит восстановить остальные.
ТЗ_Дуги и в самом деле дает полное представление о топологии графа, и в ТЗ_Узлы колонки ДугиВход и ДугиИсход избыточны. Это наследие описанного в 6 посте :)
16. Ish_2 1104 15.11.10 11:41 Сейчас в теме
Я проверяю зацикленность и отказываюсь от решения.

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


P.S. ты не думай , я веду граф в красной книжице как ты меня обозвал.
Новая Запись - "Хунта" ( пока незацикленная)
17. Ish_2 1104 22.11.10 12:03 Сейчас в теме
Браво !
(ты уж прости меня - я подумал , что ты дрогнул)
Оставьте свое сообщение