LichenCompare.Mesa
Last Edited by: Spreitzer, February 5, 1986 5:36:20 pm PST
DIRECTORY LichenDataStructure, LichenOps, IO, Real, Rope;
LichenCompare: CEDAR PROGRAM
IMPORTS LichenOps, IO, Real, Rope
EXPORTS LichenDataStructure, LichenOps =
BEGIN OPEN LichenDataStructure, LichenOps;
TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL;
graphIDToRope: PUBLIC ARRAY GraphID OF ROPE ← [A: "A", B: "B", Unspecified: "Unspecified"];
endOfQ: PUBLIC Vertex ← NEW [VertexRep];
MinHashSize: CARDINAL ← 511;
sizeFactor: REAL ← 0.25;
initialNetColor: Color ← 1;
CompareGraphs: PUBLIC PROC [a, b: CellType, nameSee: NameSee] RETURNS [equiv: BOOL] =
BEGIN
ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {
color ← v.oldColor;
FOR e: Edge ← v.firstEdge, e.sides[v.class].next WHILE e # NIL DO
nv: Vertex ← e.sides[OtherClass[v.class]].v;
IF e.sides[v.class].v # v THEN ERROR;
IF NOT nv.suspect THEN color ← color + (e.color+1) * (nv.oldColor+1);
ENDLOOP};
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] = {
FOR e: Edge ← v.firstEdge, e.sides[v.class].next WHILE e # NIL DO
IF e.sides[v.class].v # v THEN ERROR;
EnQ[e.sides[OtherClass[v.class]].v];
ENDLOOP};
Initialize: PROC = {
InitVertex: PROC [key, value: REF ANY] RETURNS [quit: BOOLEANFALSE] --HashTable.EachPairAction-- = {
v: Vertex;
WITH value SELECT FROM
x: Vertex => v ← x;
ENDCASE => ERROR;
v.graph ← curGraph;
IF v.unique OR v.QNext # notInQ THEN ERROR;
v.equiv ← NIL;
v.suspect ← FALSE;
SELECT v.class FROM
net => v.curColor ← initialNetColor;
cell => {
portIndex: PortIndex ← 0;
v.curColor ← v.type.color;
FOR e: Edge ← v.firstEdge, e.sides[cell].next WHILE e # NIL DO
IF e.sides[cell].v # v THEN ERROR;
e.color ← v.type.ports[portIndex].color;
portIndex ← portIndex + 1;
ENDLOOP;
IF portIndex # v.type.ports.length THEN ERROR;
};
ENDCASE => ERROR;
v.oldColor ← v.curColor;
EnQ[v]};
hts: CARDINALMAX[MinHashSize, Real.RoundC[sizeFactor * (a.parts.Size[] + b.parts.Size[] + 2)]];
curGraph: RealGraphID;
QFirst ← endOfQ; QCount ← 0;
oldColorTable ← curColorTable ← IntHashTable.Create[hts, colorClass];
curGraph ← A;
[] ← a.parts.Pairs[InitVertex]; [] ← InitVertex[a.mirror]; --AM1
curGraph ← B;
[] ← b.parts.Pairs[InitVertex]; [] ← InitVertex[b.mirror];
nonUniqueCount[A] ← a.parts.Size[] + 1;
nonUniqueCount[B] ← b.parts.Size[] + 1;
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
};
SetQToAllNonUniques: PROC = {
AddVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
v: Vertex;
stop ← FALSE;
WITH ra SELECT FROM
vtx: Vertex => v ← vtx;
a: Alias => {v ← NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};
ENDCASE => ERROR;
IF v.QNext # notInQ THEN ERROR;
EnQ[v]};
wasAll ← TRUE;
a.parts.EnumerateIncreasing[AddVertex]; [] ← AddVertex[a.mirror]; --AM1
b.parts.EnumerateIncreasing[AddVertex]; [] ← AddVertex[b.mirror];
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 RealGraphID 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 {
IF first[A].QNext # notInQ THEN ERROR;
IF first[B].QNext # notInQ THEN ERROR;
pairCount ← pairCount + 1;
EnQ[first[A]]; EnQ[first[B]]}};
ENDLOOP;
hashTable.firstNonEmpty ← NullIndex};
nonUniqueCount: TwoCount ← ALL[LAST[CARDINAL]];
curColorData, oldColorData: ColorTable ← NIL;
pass: CARDINAL ← 0;
QFirst: Vertex;
QCount: CARDINAL;
wasAll: BOOLTRUE;
Initialize[];
WriteAll["CompareCDs Initialized", a, b, curColorData];
WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 DO
mcCount: CARDINAL ← 0;
someMC: BOOLFALSE;
pass ← pass + 1;
WHILE QFirst # endOfQ DO
v: Vertex ← QFirst;
oldColor: Color ← v.oldColor;
newColor: Color ← v.curColor ← ComputeColor[v];
ncd: ColorData = GetColorData[curColorData, newColor];
IF QFirst = notInQ THEN ERROR;
QFirst ← v.QNext;
v.QNext ← notInQ;
IF wasAll AND NOT someMC THEN {
ocd: ColorData = NARROW[oldColorData.Fetch[oldColor]];
IF ocd.newColor = noColor THEN ocd.newColor ← newColor
ELSE IF ocd.multicolored THEN ERROR
ELSE IF ocd.newColor = newColor THEN NULL
ELSE ocd.multicolored ← someMC ← TRUE;
};
v.colorNext ← ncd.firstVertex;
ncd.firstVertex ← v;
ncd.count[v.graph] ← ncd.count[v.graph] + 1;
ENDLOOP;
QCount ← 0;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DO
uniques: ARRAY RealGraphID 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 RealGraphID 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]], a, b, 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;
equiv ← nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;
END;
HashRope: PROC [r: ROPE, hashTableSize: CARDINAL] RETURNS [c: Color] =
BEGIN
len: INT = r.Length[];
c ← 1;
FOR i: INT DECREASING IN [0 .. len) DO
char: CHAR ← r.Fetch[i];
long: LONG CARDINAL ← rot*c + (char-0C);
c ← long MOD hashTableSize;
ENDLOOP;
END;
rot: LONG CARDINAL ← 128 + 32 + 2;
CTEquivClass: PROC [ct: CellType] RETURNS [equivClass: EquivClass] = {
equivClass ← IF ct.equivClass = implicitClass THEN PickAName[ct.names] ELSE ct.equivClass};
PortEquivClass: PROC [ct: CellType, pi: PortIndex] RETURNS [equivClass: EquivClass] = {
equivClass ← IF ct.ports[pi].equivClass = implicitClass THEN PickAName[ct.ports[pi].names] ELSE ct.ports[pi].equivClass};
WriteQ: PROC [QFirst: Vertex] =
BEGIN
first: BOOLTRUE;
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[PickAName[QFirst.names]]];
ENDLOOP;
Log["}\n"];
END;
Test: PROC [da, db: Design, aName, bName: ROPE] =
BEGIN
aType: CellType ← NARROW[Lookup[da.cellTypesByName, aName]];
bType: CellType ← NARROW[Lookup[db.cellTypesByName, bName]];
equiv: BOOL;
EnsureParts[aType];
EnsureParts[bType];
Log["\nTesting %g %g\n", IO.rope[aName], IO.rope[bName]];
equiv ← CompareGraphs[aType, bType, FALSE];
Log["\nEquiv = %g.\n", IO.bool[equiv]];
FlushLog[];
END;
END.