CompareImpl.Mesa
Last Edited by: Spreitzer, July 1, 1984 6:27:22 pm PDT
CompareImpl: CEDAR PROGRAM =
BEGIN
Vertex: TYPE = REF VertexRep;
VertexRep:
TYPE =
RECORD [
neighbors: VertexS ← NIL,
QNext: Vertex ← notInQ,
colorNext, equiv: Vertex ← NIL,
color: ARRAY Pass OF Color ← [noColor, noColor],
graph: GraphID,
fudge: [0 .. 1] ← 0,
unique: BOOL ← FALSE
];
Pass: TYPE = [0 .. 1];
Color: TYPE = HashTableIndex;
noColor: Color = LAST[Color];
HashTableIndex: TYPE = CARDINAL;
NullIndex: HashTableIndex = LAST[HashTableIndex];
VertexS: TYPE = REF VertexSeq;
VertexSeq: TYPE = RECORD [vertices: SEQUENCE length: CARDINAL OF Vertex];
HashTable: TYPE = REF HashTableRep;
HashTableRep:
TYPE =
RECORD [
firstNonEmpty: HashTableIndex ← NullIndex,
entries: SEQUENCE length: HashTableIndex OF HashTableEntry];
GraphID: TYPE = {A, B};
HashTableEntry:
TYPE =
RECORD [
v: Vertex ← NIL,
nextNonEmpty: HashTableIndex ← NullIndex,
count: ARRAY GraphID OF CARDINAL ← [0, 0],
newColor: Color ← noColor,
suspect, multicolored: BOOL ← FALSE
];
newColor, multicolored, and suspect are indexed by old colors; the rest by new.
TwoCount: TYPE = ARRAY GraphID OF CARDINAL;
notInQ: Vertex ← NEW [VertexRep];
endOfQ: Vertex = NIL;
Compare:
PROC [hashTable: HashTable, nonUniqueCount: TwoCount] =
BEGIN
ComputeColor:
PROC [v: Vertex]
RETURNS [color: Color] = {
color ← (v.color[oldPass] + v.fudge) MOD hashTable.length;
v.fudge ← 0;
FOR i:
CARDINAL
IN [0 .. v.neighbors.length)
DO
n: Vertex ← v.neighbors[i];
nc: Color ← n.color[oldPass];
IF NOT hashTable[nc].suspect THEN color ← (color + (i+1) * (nc+1)) MOD hashTable.length;
ENDLOOP};
AddFrontier:
PROC [v: Vertex] = {
FOR n:
CARDINAL
IN [0 .. v.neighbors.length)
DO
w: Vertex ← v.neighbors[n];
IF (
NOT w.unique)
AND (w.QNext = notInQ)
THEN
{w.QNext ← QFirst; QFirst ← w; QCount ← QCount + 1};
ENDLOOP};
InitialColor:
PROC = {
QFirst ← endOfQ; QCount ← 0;
SetQToAllNonUniques[]};
SetQToAllNonUniques:
PROC = {
wasAll ← TRUE;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty
WHILE hti # NullIndex
DO
FOR v: Vertex ← hashTable[hti].v, v.colorNext
WHILE v #
NIL
DO
IF v.QNext # notInQ THEN ERROR;
IF
NOT v.unique
THEN
{v.QNext ← QFirst; QFirst ← v; QCount ← QCount + 1}
ENDLOOP;
ENDLOOP;
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR};
ChoosePairs:
PROC = {
wasAll ← TRUE;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty
WHILE hti # NullIndex
DO
first: ARRAY GraphID OF Vertex ← [NIL, NIL];
FOR v: Vertex ← hashTable[hti].v, v.colorNext
WHILE v #
NIL
DO
IF v.QNext # notInQ THEN ERROR;
IF first[v.graph] = NIL THEN first[v.graph] ← v;
IF
NOT v.unique
THEN
{v.QNext ← QFirst; QFirst ← v; QCount ← QCount + 1}
ENDLOOP;
IF first[A]#NIL AND first[B]#NIL THEN first[A].fudge ← first[B].fudge ← 1;
ENDLOOP;
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR};
QFirst: Vertex;
QCount: CARDINAL;
wasAll: BOOL ← TRUE;
pass, oldPass: Pass ← 0;
InitialColor[];
WHILE nonUniqueCount[
A]#0
AND nonUniqueCount[
B]#0
DO
mcCount: CARDINAL ← 0;
oldPass ← pass;
pass ← (pass+1) MOD 2;
WHILE QFirst # endOfQ
DO
v: Vertex ← QFirst;
oldColor: Color ← v.color[oldPass];
newColor: Color ← v.color[pass] ← ComputeColor[v];
IF QFirst = notInQ THEN ERROR;
QFirst ← v.QNext;
v.QNext ← notInQ;
IF wasAll
THEN {
IF hashTable[oldColor].newColor = noColor THEN hashTable[oldColor].newColor ← newColor
ELSE IF hashTable[oldColor].multicolored THEN mcCount ← mcCount + 1
ELSE IF hashTable[oldColor].newColor = newColor THEN NULL
ELSE {
otherNewColor: Color ← hashTable[oldColor].newColor;
hashTable[oldColor].multicolored ← TRUE;
mcCount ← mcCount + hashTable[otherNewColor].count[A] + hashTable[otherNewColor].count[B] + 1};
};
IF hashTable[newColor].count[
A] = 0
AND hashTable[newColor].count[
B] = 0
THEN {
hashTable[newColor].v ← NIL;
hashTable[newColor].nextNonEmpty ← hashTable.firstNonEmpty;
hashTable.firstNonEmpty ← newColor};
v.colorNext ← hashTable[newColor].v;
hashTable[newColor].v ← v;
hashTable[newColor].count[v.graph] ← hashTable[newColor].count[v.graph] + 1;
ENDLOOP;
QCount ← 0;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty
WHILE hti # NullIndex
DO
uniques: ARRAY GraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];
unique: BOOL ← uniques[A] AND uniques[B];
IF unique
THEN {
a: Vertex ← hashTable[hti].v;
b: Vertex ← a.colorNext;
IF b.colorNext # NIL THEN ERROR;
IF a.graph = b.graph THEN ERROR;
a.unique ← b.unique ← TRUE;
a.equiv ← b; b.equiv ← a;
nonUniqueCount[A] ← nonUniqueCount[A] - 1;
nonUniqueCount[A] ← nonUniqueCount[B] - 1;
};
IF uniques[
A]
OR uniques[
B]
THEN {
FOR w: Vertex ← hashTable[hti].v, w.colorNext
WHILE w #
NIL
DO
IF uniques[w.graph] THEN AddFrontier[w];
ENDLOOP};
hashTable[hti].suspect← hashTable[hti].count[A] # hashTable[hti].count[B];
hashTable[hti].count[A] ← 0;
hashTable[hti].count[B] ← 0;
hashTable[hti].newColor ← noColor;
hashTable[hti].multicolored ← FALSE;
ENDLOOP;
IF QCount > 0 THEN wasAll ← (nonUniqueCount[A] + nonUniqueCount[B]) = QCount
ELSE IF (mcCount > 0) OR (NOT wasAll) THEN SetQToAllNonUniques[]
ELSE ChoosePairs[];
ENDLOOP;
END;
END.