Анализ процессов, Графы

Работа с сетями Петри с помощью pm4py.

Время прочтения: 3 мин.

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

Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами и динамических систем. Также является одним из видов графов в библиотеке pm4py, с помощью которых можно изобразить процесс. В случае с pm4py переходами являются прямоугольники со стадиями процесса, а окружности – позициями. Сеть Петри можно создать как с помощью логов процесса, так и вручную. Логи файла могут быть xes-файлами или csv-файлами.

Пример создания сети Петри из логов:

<code>
#Импорт библиотеки для работы с csv-файлом
from pm4py.objects.log.importer.csv import factory as csv_import
#Создание сети Петри из лога
log = csv_import.import_event_stream(os.getcwd()+"\\Data.csv")
from pm4py.algo.discovery. inductive import factory as inductive_miner
net, initial_marking, final_marking = inductive_miner.apply(log)
</code>
Пример создания сети Петри вручную:
<code>
 # создание пустой сети Петри
 from pm4py.objects.petri.petrinet import PetriNet, Marking
 net = PetriNet("new_petri_net")
 # создание источника
 source = PetriNet.Place("source")
 sink = PetriNet.Place("sink")
#Создание позиции
 p_1 = PetriNet.Place("p_1")
 # добавления в Сеть Петри
 net.places.add(source)
 net.places.add(sink)
 net.places.add(p_1)
</code>

Также можно определить циклы в сети Петри. Цикл в сети Петри — это набор позиций и переходов, которые могут повторяться несколько раз (во время выполнения процесса).

Сначала применяется индуктивный майнер (один из видов сети Петри, направлена на построение надёжной сети.), потом мы получаем циклы. Переменная cylces содержит списки позиций, которые входят в циклы.

<code> 
 from pm4py.algo.discovery.inductive import factory as inductive_miner
 net, initial_marking, final_marking = inductive_miner.apply(log)
 from pm4py.objects.petri import utils
 cycles = utils.get_cycles_petri_net_places(net)
</code>

Результатом является список циклов.

Кроме этого, в данном графе можно определить «сильно связанные» компоненты (подсети, в которых путь в графе существует между каждым элементом).

Для этого также необходимо использовать индуктивный майнер.

<code>
net, initial_marking, final_marking = inductive_miner.apply(log)
from pm4py.objects.petri import utils
scc = utils.get_strongly_connected_subnets(net) 
</code>

Пример вы можете увидеть на рисунке 1.

Рисунок 1 «Сильно связанные» элементы графа

В итоге мы рассмотрели основные операции, которые можно произвести с сетями Петри с помощью библиотеки pm4py.

Советуем почитать