TAOCP 7.1.3 Exercise 131

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 131. ▶ [23] [23] Write an MMIX program for Algorithm R when the graph is represented by arc lists. Vertex nodes have at least two fields, called LINK and ARCS, and arc nodes have TIP and NEXT fields, as explained in Section 7. Initially all LINK fields are zero, except in the given set of vertices Q, which is represented as a circular list. Your program should change that circular list so that it represents the set R of all reachable vertices.

Verified: no
Solve time: 1m54s

Solution

We use the standard representation from Section 7.1.3. A vertex node has fields $\text{LINK}$ and $\text{ARCS}$, and an arc node has fields $\text{TIP}$ and $\text{NEXT}$. The field $\text{LINK}$ is reused as the queue pointer; $\text{LINK}=0$ means the vertex is not currently in the queue. The initial set $Q$ is given as a circular linked list using $\text{LINK}$.

We maintain a queue of discovered but not yet processed vertices. The invariant is that every vertex in the queue has been discovered, and every vertex with $\text{LINK}\ne 0$ is either in the queue or already processed. When a vertex $u$ is removed from the queue, all vertices reachable by a single arc from $u$ are inspected through its $\text{ARCS}$ list; any undiscovered vertex $v$ is inserted into the queue and linked using $\text{LINK}$.

We also maintain a tail pointer $T$ so that insertion into the circular queue is constant time. When the queue becomes empty, the algorithm terminates, and the remaining queue nodes represent exactly the reachable set $R$.

We assume the following offsets:

$$ \text{LINK}=0,\quad \text{ARCS}=8,\quad \text{TIP}=0,\quad \text{NEXT}=8. $$

We assume $0$ represents the null pointer.

        % MMIX program for Algorithm R (reachable vertices via arc lists)

        LOC     #100

Q       IS      $0          % pointer to initial circular list
T       IS      $1          % tail pointer
u       IS      $2
v       IS      $3
a       IS      $4
t       IS      $5

LINK    IS      0
ARCS    IS      8
TIP     IS      0
NEXT    IS      8

% ------------------------------------------------------------
% Find tail of initial circular list Q
% ----------------------------------------------------------, SET     T,Q
1H      LDO     t,T,LINK
        CMP     t,t,Q
        BZ      t,2F
        SET     T,t
        JMP     1B

2H      % T is now tail, Q is head

% ------------------------------------------------------------
% Main loop: remove u from head of queue
% ----------------------------------------------------------, 3H      BZ      Q,9F

        SET     u,Q
        LDO     Q,u,LINK

        CMP     t,Q,u
        BZ      t,4F

        JMP     5F

4H      SET     Q,0
        SET     T,0
        JMP     6F

5H      % queue nonempty after removal
        % Q already updated; T unchanged unless needed
        % (T remains valid because we only append at T)

6H      % process adjacency list of u
        LDO     a,u,ARCS

7H      BZ      a,3B

        LDO     v,a,TIP
        LDO     t,v,LINK
        BNZ     t,8F

        % insert v into queue
        BNZ     Q,7F

        % queue empty
        SET     Q,v
        SET     T,v
        SET     v,v
        STO     v,v,LINK
        JMP     8F

7H      % nonempty queue insertion
        LDO     t,T,LINK
        STO     t,v,LINK
        STO     v,T,LINK
        SET     T,v

8H      LDO     a,a,NEXT
        JMP     7B

9H      TRAP    0,0,0

This program terminates with the queue containing exactly the vertices reachable from the initial set $Q$, since every insertion corresponds to discovering a vertex via some arc, and no vertex is inserted more than once because $\text{LINK}\ne 0$ serves as a permanent mark of discovery. ∎