[Indigo]<Rosemary>Compare0.1>CompareCellDefs.Mesa!8

CompareCellDefs.Mesa

Last Edited by: Spreitzer, July 10, 1984 4:47:47 pm PDT

DIRECTORY ComparePrivate, IO, OrderedSymbolTableRef, Real;

CompareCellDefs: CEDAR PROGRAM

IMPORTS ComparePrivate, IO, OrderedSymbolTableRef, Real

EXPORTS ComparePrivate =

BEGIN OPEN ComparePrivate;

TwoCount: TYPE = ARRAY GraphID OF CARDINAL;

endOfQ: PUBLIC Vertex ← NEW [VertexRep[net][0]];

sizeFactor: REAL ← 0.25;

CompareCDs: PUBLIC PROC [vertices: SymbolTablePair] =

BEGIN

ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {

color ← v.oldColor;

WITH v SELECT FROM

cv: ComponentVertex => FOR i: CARDINAL IN [0 .. cv.length) DO

nv: Vertex ← cv.neighbors[i];

ec: Color ← cv.ports[i].color;

vc: Color ← nv.oldColor;

IF NOT nv.suspect THEN color ← (color + (ec+1) * (vc+1)) MOD hashTable.length;

ENDLOOP;

nv: NetVertex => FOR i: CARDINAL IN [0 .. nv.length) DO

cv: Vertex ← nv.neighbors[i].v;

ec: Color ← nv.neighbors[i].color;

vc: Color ← cv.oldColor;

IF NOT cv.suspect THEN color ← (color + (ec+1) * (vc+1)) MOD hashTable.length;

ENDLOOP;

ENDCASE => ERROR};

EnQ: PROC [v: Vertex] = {IF (NOT v.unique) AND (v.QNext = notInQ) THEN {v.QNext ← QFirst; QFirst ← v; QCount ← QCount + 1}};

AddFrontier: PROC [v: Vertex] = {

WITH v SELECT FROM

nv: NetVertex => FOR n: CARDINAL IN [0 .. nv.length) DO

EnQ[nv.neighbors[n].v];

ENDLOOP;

cv: ComponentVertex => FOR n: CARDINAL IN [0 .. cv.length) DO

EnQ[cv.neighbors[n]];

ENDLOOP;

ENDCASE => ERROR};

Initialize: PROC = {

InitVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {

v: Vertex ← NARROW[ra];

stop ← FALSE;

IF v.unique OR v.QNext # notInQ THEN ERROR;

EnQ[v]};

hts: CARDINAL ← MAX[MinHashSize, Real.RoundC[sizeFactor * (vertices[A].Size[] + vertices[B].Size[])]];

QFirst ← endOfQ; QCount ← 0;

hashTable ← NEW [HashTableRep[hts]];

hashTable.firstNonEmpty ← NullIndex;

FOR hti: HashTableIndex IN [0 .. hashTable.length) DO

hashTable[hti] ← [];

ENDLOOP;

vertices[A].EnumerateIncreasing[InitVertex];

vertices[B].EnumerateIncreasing[InitVertex];

nonUniqueCount[A] ← vertices[A].Size[];

nonUniqueCount[B] ← vertices[B].Size[];

IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;

};

SetQToAllNonUniques: PROC = {

AddVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {

v: Vertex ← NARROW[ra];

stop ← FALSE;

IF v.QNext # notInQ THEN ERROR;

EnQ[v]};

wasAll ← TRUE;

vertices[A].EnumerateIncreasing[AddVertex];

vertices[B].EnumerateIncreasing[AddVertex];

IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;

hashTable.firstNonEmpty ← NullIndex};

ChoosePairs: PROC [useSuspects: BOOL] RETURNS [pairCount: CARDINAL] = {

wasAll ← TRUE; pairCount ← 0;

FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DO

first: ARRAY GraphID OF Vertex ← [NIL, NIL];

IF hashTable[hti].suspect # useSuspects THEN LOOP;

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;

ENDLOOP;

IF first[A]#NIL AND first[B]#NIL THEN {

IF first[A].unique # first[B].unique THEN ERROR;

IF NOT first[A].unique THEN {

pairCount ← pairCount + 1;

EnQ[first[A]]; EnQ[first[B]]}};

ENDLOOP;

hashTable.firstNonEmpty ← NullIndex};

nonUniqueCount: TwoCount ← ALL[LAST[CARDINAL]];

hashTable: HashTable ← NIL;

pass: CARDINAL ← 0;

QFirst: Vertex;

QCount: CARDINAL;

wasAll: BOOL ← TRUE;

Initialize[];

WriteAll["CompareCDs Initialized", vertices, hashTable];

WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 DO

mcCount: CARDINAL ← 0;

someMC: BOOL ← FALSE;

pass ← pass + 1;

WHILE QFirst # endOfQ DO

v: Vertex ← QFirst;

oldColor: Color ← v.oldColor;

newColor: Color ← v.curColor ← ComputeColor[v];

IF QFirst = notInQ THEN ERROR;

QFirst ← v.QNext;

v.QNext ← notInQ;

IF wasAll AND NOT someMC THEN {

IF hashTable[oldColor].newColor = noColor THEN hashTable[oldColor].newColor ← newColor

ELSE IF hashTable[oldColor].multicolored THEN ERROR

ELSE IF hashTable[oldColor].newColor = newColor THEN NULL

ELSE hashTable[oldColor].multicolored ← someMC ← TRUE;

};

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;

IF a.unique OR b.unique THEN ERROR;

a.unique ← b.unique ← TRUE;

a.equiv ← b; b.equiv ← a;

nonUniqueCount[A] ← nonUniqueCount[A] - 1;

nonUniqueCount[B] ← nonUniqueCount[B] - 1;

};

ENDLOOP;

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;

IF NOT (a.unique AND b.unique) THEN ERROR;

AddFrontier[a]; AddFrontier[b];

};

hashTable[hti].suspect← hashTable[hti].count[A] # hashTable[hti].count[B];

FOR v: Vertex ← hashTable[hti].v, v.colorNext WHILE v # NIL DO

v.oldColor ← v.curColor;

v.suspect ← hashTable[hti].suspect;

ENDLOOP;

hashTable[hti].count[A] ← 0;

hashTable[hti].count[B] ← 0;

hashTable[hti].newColor ← noColor;

hashTable[hti].multicolored ← FALSE;

ENDLOOP;

WriteAll[IO.PutFR["Almost end of pass %g", IO.card[pass]], vertices, hashTable];

Log["QCount=%g, nonUniqueCount=[%g, %g], someMC=%g, wasAll=%g\n",

IO.card[QCount], IO.card[nonUniqueCount[A]],

IO.card[nonUniqueCount[B]], IO.bool[someMC], IO.bool[wasAll]];

WriteQ[QFirst];

IF QCount > 0 THEN {

wasAll ← (nonUniqueCount[A] + nonUniqueCount[B]) = QCount;

hashTable.firstNonEmpty ← NullIndex}

ELSE IF someMC OR (NOT wasAll) THEN SetQToAllNonUniques[]

ELSE {pairCount: CARDINAL ← ChoosePairs[useSuspects: FALSE];

IF pairCount = 0 THEN {QFirst ← endOfQ; QCount ← 0;

pairCount ← ChoosePairs[useSuspects: TRUE];

IF pairCount = 0 THEN EXIT}};

ENDLOOP;

END;

WriteQ: PROC [QFirst: Vertex] =

BEGIN

first: BOOL ← TRUE;

Log["Q = {"];

FOR QFirst ← QFirst, QFirst.QNext WHILE QFirst # endOfQ DO

IF QFirst = notInQ THEN ERROR;

IF first THEN first ← FALSE ELSE Log[", "];

Log["%g.%g", IO.rope[graphIDToRope[QFirst.graph]], IO.rope[QFirst.name]];

ENDLOOP;

Log["}\n"];

END;

END.