pyk.kcfg.minimize module

class KCFGMinimizer(kcfg: KCFG)

Bases: object

kcfg: KCFG

lift_edge(b_id: NodeIdLike) → None

Lift an edge up another edge directly preceding it.

A –M steps–> B –N steps–> C becomes A –(M + N) steps–> C. Node B is removed.

Parameters:

b_id – the identifier of the central node B of a sequence of edges A –> B –> C.

Raises:

AssertionError – If the edges in question are not in place.

lift_edges() → bool

Perform all possible edge lifts across the KCFG.

The KCFG is transformed to an equivalent in which no further edge lifts are possible.

Given the KCFG design, it is not possible for one edge lift to either disallow another or allow another that was not previously possible. Therefore, this function is guaranteed to lift all possible edges without having to loop.

Returns:

An indicator of whether or not at least one edge lift was performed.

lift_split_edge(b_id: NodeIdLike) → None

Lift a split up an edge directly preceding it.

A –M steps–> B –[cond_1, …, cond_N]–> [C_1, …, C_N] becomes A –[cond_1, …, cond_N]–> [A #And cond_1 –M steps–> C_1, …, A #And cond_N –M steps–> C_N]. Node B is removed.

Parameters:

b_id – The identifier of the central node B of the structure A –> B –> [C_1, …, C_N].

Raises:

• AssertionError – If the structure in question is not in place.

• AssertionError – If any of the cond_i contain variables not present in A.

lift_split_split(b_id: NodeIdLike) → None

Lift a split up a split directly preceding it, joining them into a single split.

A –[…, cond_B, …]–> […, B, …] with B –[cond_1, …, cond_N]–> [C_1, …, C_N] becomes A –[…, cond_B #And cond_1, …, cond_B #And cond_N, …]–> […, C_1, …, C_N, …]. Node B is removed.

Parameters:

b_id – the identifier of the node B of the structure A –[…, cond_B, …]–> […, B, …] with B –[cond_1, …, cond_N]–> [C_1, …, C_N].

Raises:

AssertionError – If the structure in question is not in place.

lift_splits() → bool

Perform all possible split liftings.

The KCFG is transformed to an equivalent in which no further split lifts are possible.

Returns:

An indicator of whether or not at least one split lift was performed.

minimize() → None

Minimize KCFG by repeatedly performing the lifting transformations.

The KCFG is transformed to an equivalent in which no further lifting transformations are possible. The loop is designed so that each transformation is performed once in each iteration.