Extensive Playout of a Process Tree

Extensive Playout of a Process Tree

An extensive playout operation permits to obtain (up to the provided limits) the entire language of the process model. Doing an extensive playout operation on a Petri net can be incredibly expensive (the reachability graph needs to be explored). Process trees, with their bottom-up structure, permit to obtain the entire language of an event log in a much easier way, starting from the language of the leafs (that is obvious) and then following specific merge rules for the operators.

However, since the language of a process tree can be incredibly vast (when parallel operators are involved) or also infinite (when loops are involved), the extensive playouts is possible up to some limits:

  • A specification of the maximum number of occurrences for a loop must be done, if a loop is there. This stops an extensive playout operation at the given number of occurences.
  • Since the number of different executions, when loops are involved, is still incredibly big, it is possible to specify the maximum length of a trace to be returned. So, traces that are above the maximum length are automatically discarded.
  • For further limiting the number of different executions, the maximum number of traces returned by the algorithm might be provided.

Moreover, from the structure of the process tree, it is easy to infer the minimum length of a trace allowed by the process model (always following the bottom-up approach).

Some reasonable settings for the extensive playout are the following:

  • Overall, the maximum number of traces returned by the algorithm is set to 100000.
  • The maximum length of a trace that is an output of the playout is, by default, set to the minimum length of a trace accepted by a process tree.
  • The maximum number of loops is set to be the minimum length of a trace divided by two.

These parameters are respectively:

  • Parameters.MAX_TRACE_LENGTH
  • Parameters.MAX_LOOP_OCC

In the following, we see how the playout can be executed.

from pm4py.objects.log.importer.xes import importer as xes_importer
import os

log = xes_importer.apply(os.path.join("tests", "input_data", "receipt.xes"))

First, a log can be imported:

from pm4py.algo.discovery.inductive import algorithm as inductive_miner

tree = inductive_miner.apply_tree(log)

Then, a process tree can be discovered using the inductive miner algorithm. We specify to retrieve traces of length at most equal to 3, and we want to retrieve at most 100000 traces.

from pm4py.simulation.tree_playout import algorithm as tree_playout

playout_variant = tree_playout.Variants.EXTENSIVE
param = tree_playout.Variants.EXTENSIVE.value.Parameters

simulated_log = tree_playout.apply(tree, variant=playout_variant,
                                   parameters={param.MAX_TRACE_LENGTH: 3, param.MAX_LIMIT_NUM_TRACES: 100000})

We see that we get 486 traces back from this operation.