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: BOOLEAN _ FALSE] --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: CARDINAL _ MAX[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: BOOL _ TRUE;Initialize[];WriteAll["CompareCDs Initialized", a, b, curColorData];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];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: 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[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.    T  LichenCompare.MesaLast Edited by: Spreitzer, February 5, 1986 5:36:20 pm PSTЭ╩'  Ц"cedar" styleШ IcodeЩJЩ:KШ KЪ╧k	Ь!ЭЬШ9KШ Ъ╨bxЬЭЬЭШKЪЭЬЭЬШ!KЪЭЬ!Ш(KШ KЪЭЬЭЬ Ш*KШ KЪ	Ь
ЭЬЭЬЭЬЭЬШ/KШ KЪЬЭЬЭЬ	ЭЬЭЬЭЬЭЬ#Ш[KШ KЪЬЭЬ
ЭЬШ(KШ KЪЬЭЬШKЪЬЭЬШKШKШ Ъ
╧nЬЭЬЭЬ$ЭЬ	ЭЬШUKЪЭШЪЯЬЭЬЭЬШ9KЪЬШЪЭЬ.ЭЬЭЬЭШAKШ,KЪЭЬЭЬЭЬШ%KЪЭЬЭЬЭЬ/ШEKЪЭЬШ	ЧЧKЪЯЬЭЬЭЬЭЬЭЬЭЬ6Ш|ЪЯЬЭЬШ!ЪЭЬ.ЭЬЭЬЭШAKЪЭЬЭЬЭЬШ%KШ$KЪЭЬШ	ЧЧЪЯ
ЬЭЬШЪЯ
ЬЭЬЭЬЭЬЭЬЭЬЭЬ╧cЬШgKЪЬ
Ш
ЪЭЬЭЬЭШKЪЬШKЪЭЬЭЬШЧKШKЪЭЬ
ЭЬЭЬЭЬШ+KЪЬ
ЭЬШKЪЬЭЬШЪЭЬ	ЭШKШ$Ш	KШKШЪЭЬ+ЭЬЭЬЭШ>KЪЭЬЭЬЭЬШ"KШ(KШKЪЭЬШЧKЪЭЬ!ЭЬЭЬШ.KШЧKЪЭЬЭЬШЧKШKШЧKЪЬЭЬЭЬOШbKШKШKШEKЪЬЭЬШKЪЬ;аШ@KЪЬЭЬШKЪЬ:Ш:KЪЬЭЬШ'KЪЬЭЬШ'KЪ
ЭЬЭЬЭЬЭЬЭЬШ?KЪЬШЧЪЯЬЭЬШЪЯ	ЬЭЬЭЬЭЬЭЬЭЬШ6KЪЬ
Ш
KЪЬЭЬШЪЭЬЭЬЭШKШKЪ	ЬЭЬЭЬЭЬЭЬШSKЪЭЬЭЬШЧKЪЭЬЭЬЭЬШKЪЬШЧKЪЬ	ЭЬШKЪЬBаШGKЪЬAШAKЪ
ЭЬЭЬЭЬЭЬЭЬШ?KЪЬ%Ш%ЧЪ
ЯЬЭЬЭЬЭЬЭЬШGKЪЬ	ЭЬШЪЭЬLЭЬЭШgKЪ	ЬЭЬЭЬЭЬЭЬШ0KЪЭЬ&ЭЬЭЬШ2ЪЭЬ+ЭЬЭЬЭШ>KЪЭЬЭЬЭЬШKЪЭЬЭЬЭЬШ0KЪЭЬШЧЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ'KЪ
ЭЬЭЬЭЬ	ЭЬЭЬШ0ЪЭЬЭЬЭЬ	ЭЬШKЪЭЬЭЬЭЬЭЬШ&KЪЭЬЭЬЭЬЭЬШ&KЪЬШKЪЬ
ЭЬЭЬШЧЧKЪЭЬШЧKЪЬ%Ш%ЧKЪЬЭЬЭЬЭЬШ/KЪЬ)ЭЬШ-KЪЬЭЬШKШKЪЬЭЬШKЪЬЭЬЭЬШKШKЪЬ7Ш7Ъ	ЭЬЭЬЭЬЭЬЭШ4KЪЬ	ЭЬШKЪЬЭЬЭЬШKЪЬШЪЭЬЭШKШKШKЪЬ/Ш/KЪЬ6Ш6KЪЭЬЭЬЭЬШKШKЪЬШЪЭЬЭЬЭЬЭЬШKЪЬЭЬШ6KЪЭЬЭЬШ6KЪЭЬЭЬЭЬЭШ#KЪЭЬЭЬЭЬЭШ)KЪЭЬЭЬШ&KШЧKЪЬШKЪЬШKЪЬ,Ш,KЪЭЬШЧKШЪЭЬLЭЬЭШgKЪЬ	ЭЬЭЬЭЬЭЬЭЬШ\KЪ	ЬЭЬЭЬЭЬ	ЭЬШ)ЪЭЬЭЬШKЪЬШKШKЪЭЬЭЬЭЬЭЬШ KЪЭЬЭЬЭЬШ KЪЭЬ
ЭЬ
ЭЬЭЬШ#KЪЬЭЬШKШKЪЬЭЬЭЬШ*KЪЬЭЬЭЬШ*KШЧKЪЭЬШЧЪЭЬLЭЬЭШgKЪЬ	ЭЬЭЬЭЬЭЬЭЬШ\KЪ	ЬЭЬЭЬЭЬ	ЭЬШ)ЪЭЬЭЬШKЪЬШKШKЪЭЬЭЬЭЬЭЬШ KЪЭЬЭЬЭЬШ KЪ
ЭЬЭЬЭЬЭЬЭЬШ*KЪЬШKШЧKЪЬ-ЭЬЭЬШJЪЭЬ+ЭЬЭЬЭШ>KШKЪЬ#Ш#KЪЭЬШЧKЪЬЭЬШKЪЬЭЬШKЪЬ"Ш"KЪЬЭЬШ$KЪЭЬШЧKЪЬ	ЭЬ ЭЬШLЪЬAШAKЪЭЬЭЬЭЬШ,KЪЭЬЭЬЭЬЭЬШ>ЧKШЪЭЬЭЬШKЪЬЭЬЭЬШ:KШ$ЧKЪ
ЭЬЭЬЭЬЭЬ	ЭЬШ9ЪЭЬЭЬЭЬШ<ЪЭЬЭЬШ3KЪЬ%ЭЬШ+KЪЭЬЭЬЭЬШЧЧKЪЭЬШЧKЪЬЭЬЭЬЭЬШ4KЪЭЬШЧKШ Ъ
ЯЬЭЬЭЬЭЬЭЬШFKЪЭШKЪЬЭЬШKШЪ	ЭЬЭЬЭ
ЬЭЬЭШ&KЪЬЭЬШKЪЬЭЬЭЬШ(KЪЬ	ЭЬШKЪЭЬШЧKЪЭЬШKЪЬЭЬЭЬШ"ЧKШ ЪЯЬЭЬЭЬШFKЪЬЭЬЭЬЭЬШ[ЧKШ ЪЯЬЭЬЭЬШWKЪЬЭЬ)ЭЬЭЬШyЧKШ ЪЯЬЭЬШKЪЭШKЪЬЭЬЭЬШKШЪЭЬЭЬЭШ:KЪЭЬЭЬЭЬШKЪЭЬЭЬ	ЭЬЭЬШ+KЪЬЭЬ$ЭЬ ШUKЪЭЬШЧKШKЪЭЬШЧKШ ЪЯЬЭЬ ЭЬШ1KЪЭШKЪЬЭЬ$Ш<KЪЬЭЬ$Ш<KЪЬЭЬШKЪЬШKЪЬШKЪЬЭЬЭЬШ9KЪЬ$ЭЬШ+KЪЬЭЬШ'KШKЪЭЬШЧKШ KЪЭЬШЧЧ ЕЧ    ╚  +C  