Currently I am working on an algorithm to reduce the number of loop iterations in traces to what is minimum necessary.

More exactly, this:

trace = ["a", "b", "b", "b", "c"]

should be reduced to:

new_trace = ["a", "b", "b", "c"]

so that the information about "b" following "b" is not lost.

Another example is:

trace = ["a", "b", "c", "d", "b", "c", "d", "b", "c", "d", "e"]

should be reduced to:

new_trace = ["a", "b", "c", "d", "b", "c", "d", "e"]

I also implemented an algorithm in Python which does exactly that:

def reduce_cycles(trace_variant: List[str], loop_retain_factor: int) -> List[str]:
    original_edges = list(zip(trace_variant, trace_variant[1:]))
    trace_follows_graph = Counter(original_edges)

    trace_graph = nx.DiGraph()
    trace_graph.add_edges_from(original_edges)
    trace_cycles: Generator[List[str], None, None] = nx.simple_cycles(trace_graph)

    edges_per_cycle = map(
        lambda cycle: list(zip(cycle, cycle[1:] + cycle[0:1])), trace_cycles
    )

    # reduce number of edges for cycles in trace
    for cycle_edges in edges_per_cycle:
        reduce_cycle_weight = min(itemgetter(*cycle_edges)(trace_follows_graph))

        for cycle_edge in cycle_edges:
            trace_follows_graph[cycle_edge] -= reduce_cycle_weight - loop_retain_factor

    # does not exactly work
    # especially not for examples such as trace_variant = ["a", "b", "c", "b", "c", "d", "c", "b", "e"]
    def replay_edge(acc: List[Edge], new: Edge):
        if trace_follows_graph[new] > 0:
            trace_follows_graph[new] -= 1
            return acc + [new]
        return acc

    new_trace_edges = reduce(replay_edge, original_edges, [])
    new_trace_variant = list(map(itemgetter(0), new_trace_edges))

    # add final event
    new_trace_variant.append(new_trace_edges[-1][-1])
    return new_trace_variant

But as you can obviously see the algorithm is not exactly performant. Especially as there normally is a huge amount of traces, meaning this function will be called for each trace. So I was wondering if there maybe already exists an algorithm which can solve this problem more efficiently or if anyone else has an idea how to improve this implementation performancewise.

I'd appreciate your help!

EDIT: abcbcbcdcbe should become abcdcbe

Or if you construct a directed graph from the following trace: abcdbcdbcdbcdbcde

it should become abcdbcde

EDIT2: I've updated the code, the description and one graph, as the comment from @kcsquared made me reevaluate this problem.

To sum up what I want is that when passing a trace to the function/algorithm it should remove all repetitions, unless removing a repetition would remove an edge in the corresponding directed graph.

• I've already figured out how to get the "repetitions"/cycles in the graph
• And I think I figured out how to update the edge weights (the edge weight of node A and B corresponds to how often B follows A in the original trace)
• I am a little bit stuck on how to get the trace afterward

Again any help appreciated.