7 Literal Selection in Switching Lattice Design
169
HMPA1 (input {G, P }, output {A, R, L, Q})
set to 0 all the elements of A, R, L, Q;
define an empty queue Z;
push 1 → Z; /* start with vertex 1 in the queue */
a ← 1;
/* a is an area number */
while Z non empty
pop Z → h;
A(h) ← a;
R(h) ← h;
access L h through P (h);
select a literal x from L h at random;
L(h) ← x;
traverse G building a BFS tree with root h;
let s be the vertex currently encountered;
if (A(s) = 0)
access L s through P (s);
if (x ∈ L s )
A(s) ← a;
R(s) ← h;
L(s) ← x;
else if (Q(s) = 0)
push s → Z;
Q(s) ← 1;
until no more vertices s with (A(s) = 0) AND (Q(s) = 0) are encountered;
a ← a + 1;
The second heuristic called HMPA2 scans the vertices v h of G assigning a final
literal to each vertex encountered. In this process Rule 1 is applied again at each
step. Since the subsets of literals of two out of four vertices adjacent to h have
already been reduced to a sole literal, both steps of the rule are likely to induce a
new reduction of L h before a literal is assigned to h. At the end of the scan, a graph
traversal is needed to build the areas, e.g., via BSF. A queue Z and the vectors
A, R, L, Q, P can be used as in HMPA1, but this traversal is simpler because a
literal has already been assigned to each vertex.
HMPA2 (input {G, P }, output {A, R, L, Q})
set to 0 all the elements of A, R, L, Q;
define an empty queue Z;
for h = 1 to NM
access L h through P (h);
apply Rule 1 to L h ;
select a literal x from L h at random;
L(h) ← x;
push 1 → Z;
a ← 1;
while Z non empty
pop Z → h;
A(h) ← a;
R(h) ← h;
traverse the graph G building a BFS tree with root h
let s be the vertex currently encountered
if (L(s) = L(h))