Process mining alpha algo

prom_alpha.py

import itertools as it

# alpha step 1
def activities(traces):
    a = set()
    for trace in traces:
        a |= set(trace)
    return a

# alpha step 2
def inputs(traces):
    return set(t[0] for t in traces)

# alpha step 3
def outputs(traces):
    return set(t[-1] for t in traces)

def partition(trace):
    return [(trace[i], trace[i+1]) for i in range(len(trace) - 1)]

def directly_follows(traces):
    df = set()
    for trace in traces:
        df |= set(partition(trace))
    return df

def follows(df):
    return set((a, b) for a, b in df if (b, a) not in df)

def parallel(df):
    return set((a, b) for a, b in df if (b, a) in df)

def separated(df, activities):
    return set((a, b) for a in activities for b in activities
            if (a, b) not in df and (b, a) not in df)

def relations(traces):
    act = activities(traces)
    df = directly_follows(traces)
    return {
        'activities': act,
        'inputs': inputs(traces),
        'outputs': outputs(traces),
        'df': df,
        'follows': follows(df),
        'parallel': parallel(df),
        'separated': separated(df, act)
    }

def nonempty_subsets(S):
    return [A for i in range(1, len(S)+1)
            for A in it.combinations(S, i)]

# alpha step 4
def possible_places(relations):
    pp = set()
    act = relations['activities']
    follows = relations['follows']
    sep = relations['separated']
    # all nonempty subsets - probably a quicker way to do this
    SS = nonempty_subsets(act)
    for A in SS:
        for B in SS:
            # places with A incoming, B outgoing
            # no elements of A follow each other; B similar
            if all((a, b) in follows for a in A for b in B) and \
                all((a1, a2) in sep for a1 in A for a2 in A) and \
                all((b1, b2) in sep for b1 in B for b2 in B):
                    ## can't use set() as key, use frozenset()
                    pp.add((frozenset(A), frozenset(B)))
    return pp

# alpha step 5
def maximal_pairs(poss_places):
    mp = set()
    for A, B in poss_places:
        pp = [(Ap, Bp) for Ap, Bp in poss_places if A <= Ap and B <= Bp]
        mp.add(max(pp, key=lambda (x, y): len(x) + len(y)))
    return mp

# alpha step 6
def place_dict(max_pairs):
    n = len(max_pairs)
    p = {"INPUT": -1, "OUTPUT": n}
    for i, x in enumerate(max_pairs):
        p[x] = i
    return p

# alpha step 7
def transitions(places, max_pairs, rel):
    n = len(max_pairs)
    t = set()
    t |= set((a, places[(A, B)]) for A, B in max_pairs for a in A)
    t |= set((places[(A, B)], b) for A, B in max_pairs for b in B)
    t |= set((-1, x) for x in rel['inputs'])
    t |= set((x, n) for x in rel['outputs'])
    return t

# alpha step 8
def alpha(traces):
    rel = relations(traces)
    TL = rel['activities']
    XL = possible_places(rel)
    YL = maximal_pairs(XL)
    PL = place_dict(YL)
    FL = transitions(PL, YL, rel)
    return (PL, TL, FL)

def main():
    ## L1
    traces = ['a b c d'.split(), 'a c b d'.split(), 'a e d'.split()]
    print alpha(traces)

if __name__ == '__main__':
    main()