Comments 6
Не совсем по теме, но про графы. Орграф. К нему матрица смежности и инцидентности. В матрице смежности указывают только +1 (исходящие ветви). Может есть какое название для матрицы смежности, где указывают и "-1" (входящие ветви).
"-1" - в такой матрице "смежности -" вроде как и избыточны, но все равно могут найти применение, хотя бы визуально становится понятнее какие входы \ выходы у вершины.
Второе. Если какие - либо подходы матричного анализа workflow?
т.е. есть алгоритм, он преобразуется в граф и далее через анализ его матриц (смежности, инцидентности, достижимости и др.) строится вывод о параметрах самого workflow - алгоритма.
Про "кодогенерации" - как то подобное можно без нее решить (аналитически)? Например только математикой из анализа матриц, полученных из графа?
В матрице смежности достаточно информации, чтобы визуально понять, какие входы/выходы у вершины, достаточно посмотреть соответственно на столбец/строку этой вершины. Добавление "-1" в матрицу смежности ограничит множество графов, которые можно с её помощью представить, - если есть дуга i-j, в такой матрице нельзя описать дугу j-i.
С помощью матриц можно решить задачу о паросочетании, преобразовав ее в задачу о назначениях, но такая матрица (в данном контексте) будет разреженной, и многие алгоритмы тогда будут не эффективны.
Основная цель такого подхода - многократное выполнение сгенерированного кода с разными исходными данными. Можно, конечно, выполнять вычисления прямо по ходу получения порядка этих вычислений, но так или иначе, мы будем выполнять полученную последовательность инструкций, а это не что иное, как кодогенерация. А решить систему нелинейных уравнений аналитически можно далеко не всегда.
Какие есть подходы (примеры) матричного анализа workflow? Если есть workflow - процесс в какой - либо нотации (EPC, basic flowchart и т.п.) полагаю, что только графовой теории недостаточно для формирования из workflow эквивалентного графа и дальнейшего его анализа по матрице смежности, инцидентности и т.п.?
Со второго раза вопрос понял, с этими понятиями не работал. Полагаю, что в некоторых случаях такие нотации можно анализировать с помощью цепей Маркова и теории массового обслуживания. Есть ещё сети Петри.
Заключение
Попытки математической формализации прикладных BPMN \ YAWL через сети Петри и алгебры процессов (CCS, CSP, ACP, pi-calculus, actor model и др.) или другим математическим аппаратом на данный момент нельзя считать успешными: ...
https://habr.com/ru/articles/786286/
Думал может что-то все же есть на этот счет.
Разворачиваем систему уравнений в граф
В моем вопросе это бы звучало: Разворачиваем систему workflow в граф
Добрый день. Очень интересная статья, добавила к себе в закладки. Я тоже интересуюсь этой тематикой (дискретной оптимизацией и графами). Замечу, что для графов обычно используют не матрицы, а списки инцидентности, особенно для разреженных графов. Для орграфа таких списков будет два: для входящих и выходящих дуг. И, к стыду своему, не знала, что минимальное множество обратных дуг - NP- полная задача. Когда один раз возникла подобная задача для орграфа расчета себестоимости продукции (брак отправляли в металлолом, возникали циклы), с помощью поиска в глубину сформировала множество обратных дуг, благо критерий обратной дуги известен. Спасибо за информацию))
Разворачиваем систему уравнений в граф