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

Программирование - Практика программирования

32
Множество статей на Инфостарте описывают, как работать с компонентой 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! Ну или пишите в личку.

32

См. также

Комментарии
Сортировка: Древо
1. lunjio 49 23.05.18 23:30 Сейчас в теме
Реклама ) Изначально не вник, подумал это бит.
van_za; Dream_kz; +2 Ответить
3. user621724_Dimav1979 259 24.05.18 07:51 Сейчас в теме
Статья ниочем
manuel; lunjio; rpgshnik; +3 Ответить
5. sloneg 43 24.05.18 11:17 Сейчас в теме
(3) Буду рад, если кому-то окажется полезной.
4. kalyaka 379 24.05.18 09:03 Сейчас в теме
В статье содержится идея. Интересно было бы увидеть и практическую реализацию.
Жду от автора продолжения, вот темы:
"Реализация графического вывода в табличный документ с использованием апплета"
"Реализация графического вывода в табличный документ с использованием html+svg"

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

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


Не обижайтесь, Сергей. Я не умаляю Ваших заслуг, просто писал именно про орграфы. Если хотите - добавлю ссылки на Вас и коллегу))
11. pm74 124 24.05.18 14:00 Сейчас в теме
(9) еще можно добавить пару слов про графическую схему , с помощью которой тоже можно нарисовать ориентированный граф
а если заморочиться то стрелки можно нарисовать и в табличном документе ))
12. sloneg 43 24.05.18 14:03 Сейчас в теме
(11) Я сначала рисовал стрелки в табличном документе, пришлось геометрию вспоминать:)
Потом переделал на SVG и вообще убрал стрелки.
13. vikontart 05.06.18 16:57 Сейчас в теме
Добрый день!
Очень понравилась идея рисования SVG в 1С, но почему-то поле HTML документа на форме отказывается отображать svg картинки, а в если код вставить в макет, то код пропадает. Хотя если загрузить просто html страницу с svg, то она отображается. Не подскажете как это реализовать, хотя бы в общих чертах или с чего начать, уж очень интересно! Заранее спасибо!
14. sloneg 43 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. sloneg 43 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. sloneg 43 08.06.18 11:30 Сейчас в теме
(16) можно убрать часть <style>...</style>
18. vikontart 08.06.18 17:37 Сейчас в теме
(16) Спасибо большое! Теперь заработало.
Оставьте свое сообщение