Ex4pm.Engine.Discovery.InductiveMiner (ex4pm v26.9.9)

Copy Markdown View Source

Single-pass, rediscoverable process discovery over a real event log — an Inductive-Miner-family algorithm operating on the directly-follows graph (DFG).

Scope (stated honestly, not overclaimed)

Implemented and tested:

  • directly-follows graph construction (real edge/frequency counts from the log)
  • exclusive-choice cut detection (Definition: activity sets A1, ..., An such that no DFG edge crosses between any two parts in either direction)
  • sequence cut detection (a partial order over parts such that every edge between two parts points only "forward" — no edge points from a later part back to an earlier one)
  • recursive discovery over the base case (single activity) and recursive projection of the sub-logs induced by a detected cut

Explicitly not implemented in this pass (documented follow-up, not faked):

  • parallel cut (interleaving with no cut-crossing constraint save that both directions must be present between every pair of parts)
  • loop cut (a "body"/"redo" split with the classical do-part / redo-part structural constraints)
  • fall-through handling (flower model / activity-once-per-trace, etc.)

When neither implemented cut applies, mine/1 returns {:partial, %FlowerFallback{...}} rather than silently returning an incorrect tree — this keeps the module's claims falsifiable: every returned %ProcessTree{} node is backed by a cut this module actually detected.

This module has no dependency on Ex4pmEngine.InductiveMiner (the POWL 2.0 $PM^\times$ engine already in the repo) — it is a separate, smaller, from-scratch DFG-cut implementation per the task's explicit ask for a new module under the Ex4pm.Engine.* namespace.

Summary

Types

activity()
event_log()
trace()

Functions

alphabet(log)

Returns the alphabet (unique activity set) of an event log.

detect_exclusive_choice_cut(sigma, dfg)

Detects an exclusive-choice cut: a partition of sigma into 2+ parts such that no directly-follows edge in dfg crosses between any two distinct parts (in either direction). Connected components of the "has an edge between them" relation on activities give the candidate parts; a cut exists iff that relation yields 2 or more components.

detect_sequence_cut(sigma, dfg)

Detects a sequence cut: a partition of sigma into 2+ parts and a total order over those parts such that every directly-follows edge between two distinct parts points strictly forward in that order (never backward). Parts are seeded from the exclusive-choice partition's connected components only when at least one cross-part edge exists (otherwise it is an exclusive choice, not a sequence) — built by topologically sorting the "part reaches part" relation derived from dfg.

directly_follows_graph(log)

Computes the directly-follows graph of a log: a map from {a, b} activity pairs to the real number of times b directly follows a across all traces.

mine(log)

Discovers a process tree from a real event log via recursive DFG-cut detection. Returns {:ok, %ProcessTree{}} when the base case or an implemented cut (exclusive-choice, sequence) fully explains the log's alphabet at every recursion level, or {:partial, %FlowerFallback{}} the moment an unimplemented case (parallel/loop/fall-through) is hit anywhere in the recursion — the whole result is downgraded to :partial, it is never silently reported as :ok with a wrong tree.

Types

activity()

@type activity() :: String.t()

event_log()

@type event_log() :: [trace()]

trace()

@type trace() :: [activity()]

Functions

alphabet(log)

@spec alphabet(event_log()) :: [activity()]

Returns the alphabet (unique activity set) of an event log.

detect_exclusive_choice_cut(sigma, dfg)

@spec detect_exclusive_choice_cut([activity()], %{
  required({activity(), activity()}) => pos_integer()
}) ::
  {:ok, [[activity()]]} | :none

Detects an exclusive-choice cut: a partition of sigma into 2+ parts such that no directly-follows edge in dfg crosses between any two distinct parts (in either direction). Connected components of the "has an edge between them" relation on activities give the candidate parts; a cut exists iff that relation yields 2 or more components.

detect_sequence_cut(sigma, dfg)

@spec detect_sequence_cut([activity()], %{
  required({activity(), activity()}) => pos_integer()
}) ::
  {:ok, [[activity()]]} | :none

Detects a sequence cut: a partition of sigma into 2+ parts and a total order over those parts such that every directly-follows edge between two distinct parts points strictly forward in that order (never backward). Parts are seeded from the exclusive-choice partition's connected components only when at least one cross-part edge exists (otherwise it is an exclusive choice, not a sequence) — built by topologically sorting the "part reaches part" relation derived from dfg.

directly_follows_graph(log)

@spec directly_follows_graph(event_log()) :: %{
  required({activity(), activity()}) => pos_integer()
}

Computes the directly-follows graph of a log: a map from {a, b} activity pairs to the real number of times b directly follows a across all traces.

mine(log)

@spec mine(event_log()) ::
  {:ok, Ex4pm.Engine.Discovery.InductiveMiner.ProcessTree.t()}
  | {:partial, Ex4pm.Engine.Discovery.InductiveMiner.ProcessTree.t(),
     [Ex4pm.Engine.Discovery.InductiveMiner.FlowerFallback.t()]}

Discovers a process tree from a real event log via recursive DFG-cut detection. Returns {:ok, %ProcessTree{}} when the base case or an implemented cut (exclusive-choice, sequence) fully explains the log's alphabet at every recursion level, or {:partial, %FlowerFallback{}} the moment an unimplemented case (parallel/loop/fall-through) is hit anywhere in the recursion — the whole result is downgraded to :partial, it is never silently reported as :ok with a wrong tree.