Строим графы средствами 1С (без GraphViz)

23.05.18

Разработка - Работа с интерфейсом

Множество статей на Инфостарте описывают, как работать с компонентой GraphViz, чтобы построить ориентированный граф. Но практически нет материалов, как работать с такими графами средствами 1С. Сегодня я расскажу, как красиво строить графы с минимальным пересечением. Нам этот метод пригодился для отрисовки алгоритмов в БИТ.Финансе, т.к. типовой механизм не устраивал. Еще это может быть полезно для визуализации различных зависимостей: расчета себестоимости, графы аффилированности компаний и т.д. Надеюсь, эта статья поможет сделать мир 1С красивее и гармоничней:) Итак, поехали...

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

Посмотрим как дела обстоят в конфигурациях 1С, без использования типовых бизнес-процессов.

Как графы строят в конфигурации Управление Холдингом:

 

Как графы строят в БИТ.Финанс:

 

Как видите, самые частые ошибки:

1. Некорректное расположение вершин по вертикали: вершина-источник и вершина-приемник могут находится на одном уровне;

2. Пересечение ребер, там где их можно избежать;

3. Некорректное расположение вершин по горизонтали. В примере БИТа вершина финансист должна быть сильно левее.

Как получается строить графы у нас:

 

Тренироваться будем на примере процессов БИТ.Финанс. Сразу хочу предупредить, что готового кода здесь нет.

Часть первая: теория.

0. Исходный граф

Для примера я взял вот такой граф. В конце статьи вы увидите, каким он в результате получился.

1. Проверка на ацикличность. Построение матрицы смежности.

1.1. Алгоритм проверки на ацикличность.

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

Изначально все вершины графа имеют статус "Не посещалась" (белый цвет). Начинаем последовательно идти по вершинам графа и помечаем их статусом "В обработке" (серый цвет). Если у вершины нет необработанных дочерних вершин, то отмечаем ее как "Обработана" (черный цвет). Если в процессе обхода одной ветки попадаем на статус "В обработки" (серый цвет), значит есть цикл. Далее обходим непосещенные вершины пока они не закончатся. ВАЖНО! В черные вершины второй раз не заходим!

Пример: ациклический граф (корректный граф).

Ациклический граф

Пример: циклический граф (некорректный граф).

Циклический граф

На этом этапе мы определили является ли граф ациклическим.

1.2. Матрица смежности

Пока обходим граф для проверки ацикличности, заодно строим матрицу смежности. Матрица смежности - это матричное представление графа, где единицей указывается связь между вершинами:

Наш граф:

Матрица граф

Матрица для него будет такой:

Матрица смежности

В строках указаны вершины-источники, в колонках вершины-приемники. Видно что вершина 1 и вершина 2 связаны ребром и т.д.

На данном этапе мы получили матричное представление графа.

2. Поуровневое расположение вершин графа.

Поуровневое расположение вершин необходимо для исключения ошибок расположения вершин по вертикали, например, чтобы вершина-приемник не была выше вершины-источника.

Пример расположения:

Граф надо расположить по уровням таким образом, чтобы:

1. Вершины-источники были выше чем вершины-приемники.

2. Ребро должно быть не длиннее одного уровня. Достигается это с помощью добавления фиктивных вершин.

3. Опционально: могут быть условия на предельную ширину/высоту и т.д. В данном материале дополнительные условия не рассматриваем. Ниже будут ссылки с более подробной информацией.

Если изобразить визуально.

Исходный граф:

Исходный

Граф, разбитый по уровням. Слева с фиктивными вершинами, справа - результат:   

По уровням

Алгоритм состоит из двух частей: проход от стоков (вершин без исходящих ребер) и проход от вершин-источников. Зачем проходить два раза? Потому что ширина при разных проходах может различаться. Оптимальнее выбирать наименьшую ширину.

Начнем с прохода от стоков.

2.1. Берем вершины, которые не имеют исходящих ребер (конечные точки). Располагаем на исходном уровне.

2.2. Берем вершины, которые входят в эту вершину с одним ребром (без альтернативных путей).

2.3. Повторяем п.2 n-раз пока не обойдем все вершины.

2.4. Достраиваем ребра длиннее одного уровня, через фиктивные вершины.

Исходный граф:

Исходный граф

Гифка прохода от стоков:

  По уровням

Проход в обратную сторону по тому же алгоритму, только начинается от вершин-источников.

От истоков

Дальше выбирается минимальная ширина графа: минимальное количество вершин на одном уровне. В нашем случае ширина одинаковая, поэтому берем любой из вариантов.

Я взял вариант с пересечениями, чтобы продемонстрировать следующий шаг.

3. Минимизация количества пересечения ребер.

После расположения графа по уровням, может случится так что некоторые ребра имеют пересечения. Цель третьего шага: минимизация пересечений.

Алгоритм очень простой: 

3.1. Обходим граф (поиск в глубину) и нумеруем вершины, в том числе фиктивные.

3.2. Упорядочиваем на каждом уровне вершины по возрастанию.

Минимизация пересечений

Переходим к заключительному шагу.

4. Размещение вершин графа внутри одного уровня (по оси x-координат).

Нам нужно красиво расположить наши вершины на каждом уровне. Один из самых простых вариантов - выравнивание по центру. Но есть более сложные варианты.

Мой результат для исходного графа

Результат

Подробная информация по вариантам размещения по x-координатам изложена здесь. Там же можно почитать более подробно о поуровневом расположении графов, например, как построить циклический граф таким способом, как минимизировать высоту или ширину графа и много-много другого. 

И самое крутое - апплет на java. Можно поиграться с различными вариантами расположения. Ссылка на апплет.

5. Визуализация HTML + SVG.

Визуализировать можно с помощью табличного документа - рисовать линии по координатам. Это самый простой и понятный вариант. Так делает БИТ, да и в Консолидации также, скорее всего.

Но мы пошли другим путем. Взяли координаты наших вершин и нарисовали их с помощью HTML + SVG. С помощью SVG можно унылый табличный документ превратить в красоту. Здесь обучалка по основным возможностям SVG. Мне очень понравилось работать с этим форматом, попробуйте и вы:)

Часть вторая: практика.

А практику можно пройти у нас в компании. Мы покажем, как это реализовано у нас, и научим подобным крутым штукам.

У нас открыты вакансии программистов и аналитиков как на проектную работу, так и в штат. Welcome! Ну или пишите в личку.

Граф Орграф Алгоритм GraphViz Визуализация SVG

См. также

Богатый редактор картинок, хранимых в базе, с возможностью РИСОВАНИЯ. Редактор внешних файлов картинок. Объект, расширяющий возможности работы с картинками из встроенного языка (Три в одном) + Обработка «Стандартизация картинок»

Работа с интерфейсом Рабочее место Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

Обработка предназначена для редактирования картинок в режиме «Предприятие», с возможностью РИСОВАТЬ на них. Поддерживается работа как в обычных формах (толстый клиент) так и на управляемых формах (тонкий клиент). Обработка позволяет редактировать как картинки, хранимые в базе, так и графические файлы с диска на файловой системе. Помимо базовых функций (изменение размеров, преобразование формата, обрезание картинки, повороты и т.п.) – редактор имеет богатый набор инструментов для рисования. Доступна функция вставки изображения из буфера обмена. Также обработка может быть использована из встроенного языка как объект для редактирования картинок. Объект может быть использован: на стороне клиента, на стороне сервера, из внешнего соединения. Данная обработка будет особенно полезна тем, кто вносит картинки в базу (изображения номенклатуры, фотографии физических лиц и т.п.). Функционал реализуется с использованием JavaScript и бесплатного ПО ImageMagick (без использования внешних компонент).

6000 руб.

16.01.2015    61797    43    59    

80

[Расширения] Динамическое управление видимостью и доступностью элементов форм (УФ) (8.3.6+)

Работа с интерфейсом Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Платные (руб)

Механизм «Динамическое управление доступом к элементам форм объектов 1С8» предназначен для обеспечения возможности оперативного управления видимостью и доступностью элементов форм документов и справочников продуктов фирмы «1С» «1С:Предприятие 8». Решение универсальное, встраивается в любую конфигурацию с минимальными доработками, что позволяет без проблем обновлять типовые решения.

5000 руб.

14.01.2016    54403    16    21    

42

Управление дашбордами

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Обработка предназначена для создания и управления дашбордами.

2400 руб.

29.06.2020    16698    21    4    

35

Новогоднее оформление для 1С

Работа с интерфейсом Платформа 1С v8.3 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Зарплата и Управление Персоналом 3.x 1С:Управление нашей фирмой 3.0 Бесплатно (free)

Добавьте новогоднего настроения! Расширение создает декорацию в виде гирлянды на некоторых формах объектов.

27.12.2023    10738    750    elcoan    45    

106

Конструктор HTML, CSS и javascript

Инструментарий разработчика Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

Подходит для создания web-страниц для замены управляемых форм 1С, красивых отчетов, интерфейса мобильного приложения на платформе 1С и для простых страниц веб-сайтов.

2 стартмани

10.04.2023    9615    151    acces969    31    

118

Модель состояния для MVC

Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

"MVC плохо применима в 1С" - познакомьтесь с моделью состояния и, возможно, ваше мнение поменяется! Представленное решение является эволюционным развитием идеи реализации MVC для 1С. В новой версии добавлены DSL для описания модели состояния, а также параметризация свойств параметров и элементов формы.

1 стартмани

05.07.2022    3665    kalyaka    2    

27

Табло очереди заказов на экран телевизора

WEB-интеграция Работа с интерфейсом Платформа 1С v8.3 1С:Розница 2 Платные (руб)

Связка из веб-приложения и расширения для 1С: Розница 2.3.

3600 руб.

29.04.2022    12080    1    5    

10
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. lunjio 66 23.05.18 23:30 Сейчас в теме
Реклама ) Изначально не вник, подумал это бит.
van_za; Dream_kz; +2 Ответить
2. пользователь 24.05.18 05:43
Сообщение было скрыто модератором.
...
3. user621724_Dimav1979 401 24.05.18 07:51 Сейчас в теме
Статья ниочем
dajen; for_sale; romankoav; manuel; lunjio; rpgshnik; +6 2 Ответить
5. slozhenikin_com 302 24.05.18 11:17 Сейчас в теме
(3) Буду рад, если кому-то окажется полезной.
4. kalyaka 1053 24.05.18 09:03 Сейчас в теме
В статье содержится идея. Интересно было бы увидеть и практическую реализацию.
Жду от автора продолжения, вот темы:
"Реализация графического вывода в табличный документ с использованием апплета"
"Реализация графического вывода в табличный документ с использованием html+svg"

А также выложенного решения движка расчета графа для заданной матрицы смежности. На входе матрица, на выходе рассчитанные координаты вершин.
6. slozhenikin_com 302 24.05.18 11:19 Сейчас в теме
(4) Если статья будет достаточно популярной, возьмусь за продолжение)
7. ildarovich 7850 24.05.18 12:01 Сейчас в теме
Приведу ссылку на свое решение, которое здесь почему-то не упомянуто:
"Как нарисовать граф на 1С".
Тогда поддержки SVG еще не было, поэтому стрелки на связях не рисовались.
Сейчас это нетрудно исправить.
Также интересно решение из Анализатор сложных запросов (консоль запросов с графом), где автор потратил немало времени (по его словам) на практическое решение той же, только чуть более конкретной задачи и получил красивый результат.
8. slozhenikin_com 302 24.05.18 12:56 Сейчас в теме
(7) Я в своей статье раскрыл тему ориентированных графов. Это несколько другая тема и к тому же я ничего у вас не заимствовал, поэтому ничего странного))

Анализатор надо глянуть. Спасибо.
9. ildarovich 7850 24.05.18 13:51 Сейчас в теме
(8) Ну, если хотите спорить, уточню. Конкретно меня зацепили вот эти слова:
Множество статей на Инфостарте описывают, как работать с компонентой GraphViz, чтобы построить ориентированный граф. Но практически нет материалов, как работать с такими графами средствами 1С.
Поэтому я и привел две ссылки в ответ на слова "практически нет".
А с точки зрения минимизации пересечений ориентированный граф или нет - разницы мало.
10. slozhenikin_com 302 24.05.18 13:58 Сейчас в теме
(9) Уточняю
Множество статей на Инфостарте описывают, как работать с компонентой GraphViz, чтобы построить ориентированный граф. Но практически нет материалов, как работать с такими графами средствами 1С.


Не обижайтесь, Сергей. Я не умаляю Ваших заслуг, просто писал именно про орграфы. Если хотите - добавлю ссылки на Вас и коллегу))
11. pm74 199 24.05.18 14:00 Сейчас в теме
(9) еще можно добавить пару слов про графическую схему , с помощью которой тоже можно нарисовать ориентированный граф
а если заморочиться то стрелки можно нарисовать и в табличном документе ))
12. slozhenikin_com 302 24.05.18 14:03 Сейчас в теме
(11) Я сначала рисовал стрелки в табличном документе, пришлось геометрию вспоминать:)
Потом переделал на SVG и вообще убрал стрелки.
13. vikontart 05.06.18 16:57 Сейчас в теме
Добрый день!
Очень понравилась идея рисования SVG в 1С, но почему-то поле HTML документа на форме отказывается отображать svg картинки, а в если код вставить в макет, то код пропадает. Хотя если загрузить просто html страницу с svg, то она отображается. Не подскажете как это реализовать, хотя бы в общих чертах или с чего начать, уж очень интересно! Заранее спасибо!
14. slozhenikin_com 302 05.06.18 20:10 Сейчас в теме
(13) Попробуйте добавить в <head>

<met a http-equiv="X-UA-Compatible" content="IE=9">
15. vikontart 06.06.18 13:41 Сейчас в теме
(14) Пробую, не получается((
Может быть дело в том, что я использую тонкий клиент?
Буду очень признателен если приложите минимальный пример работающего макета)
16. slozhenikin_com 302 08.06.18 11:29 Сейчас в теме
(15) Вот пример. Не знаю загрузится или нет.

<html>
<head>   
<meta http-equiv="X-UA-Compatible" content="IE=9">
<meta charset="UTF-8">
<style type="text/css">
	body {
		overflow:    auto;
		margin-top:  2px;
		margin-left: 2px;
		margin-right: 2px;
		font-family: Arial; 
		font-size:   10pt;}
	table {
		width:       100%;
		font-family: Arial; 
		font-size:   10pt;
		border: 0px solid;}
	td {vertical-align: top;}
 	a:link {
		color: #006699; text-decoration: none;}
	a:visited {
		color: #006699; text-decoration: none;}
	a:hover {
		color: #006699; text-decoration: underline;}
	p {
		margin-top: 7px;}
	img {border: 0px;}
</style>
<body>
<svg width="500pt" height="1000pt" version="1.1" xmlns="http://www.w3.org/2000/svg">
<g>
<line x1="291.9" x2="291.9" y1="131.25" y2="157.5" stroke="gray" stroke-width="2"/>
</g>
<g>
<line x1="291.9" x2="291.9" y1="210" y2="236.25" stroke="gray" stroke-width="2"/>
</g>
<g>
<rect x="239.4" y="78.75" rx="20" ry="20" width="105" height="52.5"
stroke="black" fill="#ffffff"  fill-opacity="0.5" stroke-width="3"/>
<text text-anchor="middle" x="291.9" y="108" font-family="Verdana" font-size="10.00" font-variant="bold">Старт</text>
</g>
<g>
<rect x="239.4" y="157.5" rx="5" ry="5" width="105" height="52.5"
stroke="black" fill="#DEF3FF"  stroke-width="3"/>
<text text-anchor="middle" x="291.9" y="178" font-family="Verdana" font-size="10.00" font-variant="bold">Рук. департамента</text>
<text text-anchor="middle" 
 x="291.9" y="195.5" font-family="Verdana" font-size="10.00" font-variant="bold">ФИО</text>
</g>
<g>
<rect x="239.4" y="236.25" rx="20" ry="20" width="105" height="52.5"
stroke="black" fill="#DEF3FF"  fill-opacity="0.5" stroke-width="3"/>
<text text-anchor="middle" x="291.9" y="256.75" font-family="Verdana" font-size="10.00" font-variant="bold">Персональная</text>
<text text-anchor="middle" 
 x="291.9" y="274.25" font-family="Verdana" font-size="10.00" font-variant="bold">ФИО</text>
</g>
</svg>
</body>
</html>
Показать
manuel; Бубузяка; +2 Ответить
17. slozhenikin_com 302 08.06.18 11:30 Сейчас в теме
(16) можно убрать часть <style>...</style>
18. vikontart 08.06.18 17:37 Сейчас в теме
(16) Спасибо большое! Теперь заработало.
19. for_sale 971 01.07.19 16:27 Сейчас в теме
Сразу хочу предупредить, что готового кода здесь нет.


Эта фраза перебрасывает статью куда-то в область категории "Смотрите, как я умею!". Примеры кода помогли бы ей обрести более полезный вид.
20. slozhenikin_com 302 01.07.19 16:46 Сейчас в теме
(19)
Эта фраза перебрасывает статью куда-то в область категории "Смотрите, как я умею!". Примеры кода помогли бы ей обрести более полезный вид.


Не так.
Статья из области: смотрите какой классный алгоритм нашел, давайте объясню как это работает. Написать код по статье для ведущего программиста вполне реально.
Вторая область статьи: смотрите какие классные штуки мы делаем - приходите к нам работать.

Когда-нибудь выложу код, но сейчас не готов.
21. RustIG 1351 02.11.19 06:39 Сейчас в теме
(0) спасибо за обзор!
не все ссылки работают....
в последней статье про ЭластикАлерт - ссылка также не работает...
Оставьте свое сообщение