Multiple assignments simplification

[George Sakkis]

<bearophileHUGS at lycos.com> wrote:

> [snipped]
>
> Do you know some algorithm (or you can give some suggestions) to
> minimize the number of simple assignments needed for a "regular"
> situation like that?

You can formulate the task as a graph-theoretic problem by representing the set of assignments as a
digraph G(V,E), where:
- V = set(LHS) | set(RHS): the vertex set V is the union of all left and right hand side
expressions.
- E = set((v1,v2) for "v1 = v2" in assignments): there is an edge from v1 to v2 for every assignment
v1=v2.

Now, every edge v1->v2 where in-degree(v1)==0 corresponds to a safe assignment: v1 is not assigned
to any RHS, so it can be overwritten. After the assignment, both v1 and the edge (v1,v2) can be
removed, decrementing the in-degree of v2. This happens iteratively as long as there are nodes with
zero in-degree.

At this point, all remaining nodes have in-degree >=1 and they form one or more strongly connected
components. Since no RHS occurs more than once*, the out-degree of every vertex is less than or
equal to 1. Therefore, for every component Ci,
|Vi| >= sum(out-degree(v) for v in Vi)  == |Ei|.

Since for a strongly connected component |Vi| <= |Ei|, the previous relationship is actually
equality |Vi| == |Ei|. Thus each component is a simple cycle v[1]->v[2]->...v[n]->v[1]. You can
break the cycle by introducing an auxiliary variable x in an arbitrary edge, say v[n]->v[1]. Then
the following assignments can take place: x = v[1]; v[1] = v[2]; v[2] = v[3]; ...; v[n-1] = v[n];
v[n] = x

So overall, you need just one auxiliary variable for each strongly component of G.

HTH,
George


* More than one assignments with the same RHS [v=a, v=b] are useless since only the last has an
effect. In any case, the useless assignments can be filtered out in the beginning.