StructurallyCompare.Mesa
Bertrand Serlet June 4, 1986 4:16:39 pm PDT
Last tweaked by Mike Spreitzer on March 24, 1987 2:56:58 pm PST
DIRECTORY Basics, CardHashTableThreaded, IO, Random, Real, RealFns, Rope, RopeHash, StructuralComparisonDataStructure, StructuralComparisonOps, SymTab;
StructurallyCompare: CEDAR PROGRAM
IMPORTS Basics, CardHashTableThreaded, IO, Random, Real, RealFns, StructuralComparisonDataStructure, StructuralComparisonOps, SymTab
EXPORTS StructuralComparisonOps =
BEGIN OPEN StructuralComparisonDataStructure, StructuralComparisonOps;
TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL;
MinHashSize: CARDINAL ← 11;
sizeFactor: REAL ← 0.25;
colorClass: CardHashTableThreaded.Class = [GetColorDataKey, SetColorDataLink, GetColorDataLink];
debug: BOOL ← TRUE;
Break: SIGNAL = CODE;
MidSquare: PROC [x: CARD] RETURNS [y: CARD] ~ {y ← MidSquareI[x]};
MidSquareI: PROC [x: CARD] RETURNS [CARD] ~ INLINE {
lowProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.LowHalf[x], Basics.LowHalf[x]]]];
midProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.LowHalf[x], Basics.HighHalf[x]]]];
highProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.HighHalf[x], Basics.HighHalf[x]]]];
m: Basics.LongNumber = [lc[AddC[lowProd.hi, midProd.lo, midProd.lo]]];
lo: Basics.LongNumber = [pair[lo: lowProd.lo, hi: m.lo]];
hi: CARD = highProd.lc + AddC[m.hi, midProd.hi, midProd.hi];
RETURN [hi + lo.lc]};
CompareGraphs: PUBLIC PROC [descriptions: RealGraphDescriptions, a, b: CellType, GenerateHints: PROC [Consume: PROC [vA, vB: Vertex]], pick, mirrors, mayQuitEarly: BOOL, abort: REF BOOL] RETURNS [equiv, didQuitEarly: BOOL, partition: ColorTable] =
BEGIN
rs: Random.RandomStream = Random.Create[seed: 0];
passColor: Color ← noColor;
breakVs: SymTab.Ref ← NIL;
ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {
AddEdge: PROC [edgeColor: Color, nv: Vertex] = {
IF NOT GetSuspect[nv] THEN color ← color + (edgeColor+1) * (OldColor[nv]+1);
};
color ← OldColor[v] + passColor;
EnumerateEdges[v, AddEdge, mirrors];
color ← FilterColor[MidSquareI[color]];
IF debug AND breakVs#NIL AND breakVs.Fetch[VName[v]].found THEN Break;
};
EnQNeighbor: PROC [edgeColor: Color, neighbor: Vertex] = {EnQ[neighbor]};
EnQ: PROC [v: Vertex] = {
IF (NOT mirrors) AND IsMirror[v] THEN ERROR;
IF (NOT GetUnique[v]) AND (GetQNext[v] = notInQ) THEN {SetQNext[v, QFirst]; QFirst ← v; QCount ← QCount + 1}};
AddFrontier: PROC [v: Vertex] = {EnumerateEdges[v, EnQNeighbor, mirrors]};
Initialize: PROC = {
ClearVertex: PROC [v: Vertex] = {
IF VDead[v] THEN ERROR;
SetQNext[v, notInQ];
SetEquiv[v, NIL];
SetOldColor[v, noColor]; SetCurColor[v, noColor];
SetUnique[v, FALSE];
SetSuspect[v, FALSE];
};
NoteAssoc: PROC [vA, vB: Vertex] = {
color: Color = FilterColor[rs.NextInt[]];
SetOldColor[vA, color]; SetCurColor[vA, color];
SetOldColor[vB, color]; SetCurColor[vB, color];
};
InitVertex: PROC [v: Vertex] = {
SetGraph[v, curGraph];
IF CurColor[v] = noColor THEN {
color: Color = InitialColor[v];
SetOldColor[v, color]; SetCurColor[v, color];
};
AddToColor[GetColorData[curColorData, CurColor[v]], v];
};
ms: NAT = IF mirrors THEN 1 ELSE 0;
hts: CARDINAL ← MAX[MinHashSize, Real.RoundC[sizeFactor * RealFns.SqRt[a.size + b.size + ms + ms]]];
curGraph: RealGraphID;
QFirst ← endOfQ; QCount ← 0;
partition ← CardHashTableThreaded.Create[hts, colorClass];
curColorData ← CardHashTableThreaded.Create[hts, colorClass];
EnumerateParts[a, ClearVertex, mirrors];
IF abort^ THEN RETURN;
EnumerateParts[b, ClearVertex, mirrors];
IF abort^ THEN RETURN;
GenerateHints[NoteAssoc];
IF abort^ THEN RETURN;
curGraph ← A; EnumerateParts[a, InitVertex, mirrors];
IF abort^ THEN RETURN;
curGraph ← B; EnumerateParts[b, InitVertex, mirrors];
IF abort^ THEN RETURN;
nonUniqueCount[A] ← a.size + ms;
nonUniqueCount[B] ← b.size + ms;
someSuspect ← FALSE;
[] ← curColorData.Pairs[ComputeUnique];
SetQToAllNonUniques[];
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
};
Finalize: PROC = {
FinalVertex: PROC [v: Vertex] = {
AddToColor[GetColorData[partition, CurColor[v]], v];
};
EnumerateParts[a, FinalVertex, mirrors];
EnumerateParts[b, FinalVertex, mirrors];
};
SetQToAllNonUniques: PROC = {
AddVertex: PROC [v: Vertex] = {IF GetQNext[v] # notInQ THEN ERROR; EnQ[v]};
EnumerateParts[a, AddVertex, mirrors];
EnumerateParts[b, AddVertex, mirrors];
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
};
ChoosePairs: PROC [useSuspects, onlyOne: BOOL] RETURNS [pairCount: CARDINAL] = {
ConsiderColor: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL ← FALSE] --CardHashTableThreaded.EachPairAction-- = {
ccd: ColorData = NARROW[value];
first: ARRAY RealGraphID OF Vertex ← [NIL, NIL];
IF ccd.suspect # useSuspects THEN RETURN;
FOR v: Vertex ← ccd.firstVertex, GetColorNext[v] WHILE v # NIL DO
IF GetQNext[v] # notInQ THEN ERROR;
IF first[GetGraph[v]] = NIL THEN {
first[GetGraph[v]] ← v;
IF first[OtherGraph[GetGraph[v]]] # NIL THEN EXIT};
ENDLOOP;
IF first[A]#NIL AND first[B]#NIL THEN {
IF GetUnique[first[A]] # GetUnique[first[B]] THEN ERROR;
IF NOT GetUnique[first[A]] THEN {
pairCount ← pairCount + 1;
EnQ[first[A]]; EnQ[first[B]];
quit ← onlyOne};
};
};
pairCount ← 0;
[] ← curColorData.Pairs[ConsiderColor];
};
ComputeUnique: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL ← FALSE] --CardHashTableThreaded.EachPairAction-- = {
ccd: ColorData = NARROW[value];
uniques: ARRAY RealGraphID OF BOOL = [ccd.count[A]=1, ccd.count[B]=1];
unique: BOOL ← uniques[A] AND uniques[B];
IF unique THEN {
a: Vertex ← ccd.firstVertex;
b: Vertex ← GetColorNext[a];
IF GetColorNext[b] # NIL THEN ERROR;
IF GetGraph[a] = GetGraph[b] THEN ERROR;
IF GetUnique[a] OR GetUnique[b] THEN ERROR;
SetUnique[a, TRUE];
SetUnique[b, TRUE];
SetEquiv[a, b]; SetEquiv[b, a];
nonUniqueCount[A] ← nonUniqueCount[A] - 1;
nonUniqueCount[B] ← nonUniqueCount[B] - 1;
};
someSuspect ← (ccd.suspect ← ccd.count[A] # ccd.count[B]) OR someSuspect;
FOR v: Vertex ← ccd.firstVertex, GetColorNext[v] WHILE v # NIL DO
SetOldColor[v, CurColor[v]];
SetSuspect[v, ccd.suspect];
ENDLOOP;
};
QueueFrontier: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL ← FALSE] --CardHashTableThreaded.EachPairAction-- = {
ccd: ColorData = NARROW[value];
uniques: ARRAY RealGraphID OF BOOL = [ccd.count[A]=1, ccd.count[B]=1];
unique: BOOL ← uniques[A] AND uniques[B];
IF unique THEN {
v1: Vertex ← ccd.firstVertex;
v2: Vertex ← GetColorNext[v1];
IF GetColorNext[v2] # NIL THEN ERROR;
IF GetGraph[v1] = GetGraph[v2] THEN ERROR;
IF NOT (GetUnique[v1] AND GetUnique[v2]) THEN ERROR;
AddFrontier[v1]; AddFrontier[v2];
};
};
nonUniqueCount: TwoCount ← ALL[LAST[CARDINAL]];
curColorData, oldColorData: ColorTable ← NIL;
pass: CARDINAL ← 0;
QFirst: Vertex;
QCount: CARDINAL;
isAll: BOOL ← TRUE;
someMC, someSuspect: BOOL ← FALSE;
IF abort^ THEN RETURN [FALSE, FALSE, NIL];
Initialize[];
IF abort^ THEN RETURN [FALSE, FALSE, NIL];
IF debug THEN WriteAll["CompareCDs Initialized", descriptions, a, b, oldColorData, curColorData];
didQuitEarly ← mayQuitEarly AND someSuspect;
WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 AND NOT didQuitEarly DO
mcCount: CARDINAL ← 0;
keepOld: BOOL ← isAll;
IF abort^ THEN RETURN [FALSE, FALSE, NIL];
pass ← pass + 1;
passColor ← LOOPHOLE[rs.NextInt[], Color];
IF QCount > 0 THEN NULL
ELSE IF NOT (isAll AND NOT someMC) THEN SetQToAllNonUniques[]
ELSE {pairCount: CARDINAL ← 0;
IF pick THEN pairCount ← ChoosePairs[FALSE, TRUE];
IF pairCount = 0 THEN {
IF QFirst # endOfQ OR QCount # 0 THEN ERROR;
pairCount ← ChoosePairs[TRUE, FALSE];
IF pairCount = 0 THEN EXIT}};
isAll ← (nonUniqueCount[A] + nonUniqueCount[B]) = QCount;
oldColorData ← IF keepOld THEN curColorData ELSE CardHashTableThreaded.Create[curColorData.GetSize[], colorClass];
curColorData ← CardHashTableThreaded.Create[curColorData.GetSize[], colorClass];
someMC ← FALSE;
WHILE QFirst # endOfQ DO
v: Vertex = QFirst;
oldColor: Color = OldColor[v];
newColor: Color = ComputeColor[v];
ncd: ColorData = GetColorData[curColorData, newColor];
IF abort^ THEN RETURN [FALSE, FALSE, NIL];
IF QFirst = notInQ THEN ERROR;
SetCurColor[v, newColor];
QFirst ← GetQNext[v];
SetQNext[v, notInQ];
IF isAll AND NOT someMC THEN {
ocd: ColorData = GetColorData[oldColorData, oldColor, keepOld];
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;
};
AddToColor[ncd, v];
ENDLOOP;
QCount ← 0;
someSuspect ← FALSE;
[] ← curColorData.Pairs[ComputeUnique];
[] ← curColorData.Pairs[QueueFrontier];
IF debug THEN {
Log["\nAt end of pass %g:\n", [cardinal[pass]]];
WriteColorTable[curColorData, descriptions];
Log["QCount=%g, nonUniqueCount=[%g, %g]", IO.card[QCount], IO.card[nonUniqueCount[A]], IO.card[nonUniqueCount[B]]];
Log[", someMC=%g, isAll=%g, someSuspect=%g\n", IO.bool[someMC], IO.bool[isAll], IO.bool[someSuspect]];
WriteQ[QFirst, descriptions];
};
ENDLOOP;
equiv ← nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;
Finalize[];
END;
GetColorData: PROC [colorTable: ColorTable, color: Color, mayNotCreate: BOOL ← FALSE] RETURNS [cd: ColorData] = {
cd ← NARROW[colorTable.Fetch[color].value];
IF cd # NIL OR mayNotCreate THEN RETURN;
cd ← NEW [ColorDataPrivate ← [color: color]];
IF NOT colorTable.Insert[color, cd] THEN ERROR;
};
AddToColor: PROC [cd: ColorData, v: Vertex] = INLINE {
SetColorNext[v, cd.firstVertex];
cd.firstVertex ← v;
cd.count[GetGraph[v]] ← cd.count[GetGraph[v]] + 1;
};
WriteQ: PROC [QFirst: Vertex, descriptions: RealGraphDescriptions] =
BEGIN
first: BOOL ← TRUE;
Log["Q = {"];
FOR QFirst ← QFirst, GetQNext[QFirst] WHILE QFirst # endOfQ DO
IF QFirst = notInQ THEN ERROR;
IF first THEN first ← FALSE ELSE Log[", "];
Log["(%g)%g", [rope[descriptions[GetGraph[QFirst]]]], IO.rope[VerboseVName[QFirst]]];
ENDLOOP;
Log["}\n"];
END;
GetColorDataKey: PROC [value: REF ANY] RETURNS [key: CARD] = {
cd: ColorData = NARROW[value];
key ← cd.color;
};
SetColorDataLink: PROC [from, to: REF ANY] = {
fromCD: ColorData = NARROW[from];
toCD: ColorData = NARROW[to];
fromCD.nextColor ← toCD;
};
GetColorDataLink: PROC [from: REF ANY] RETURNS [to: REF ANY] = {
fromCD: ColorData = NARROW[from];
to ← fromCD.nextColor;
};
AddC: PROC [c1, c2, c3: CARDINAL] RETURNS [CARD] = INLINE {
RETURN [c1.LONG + c2.LONG + c3.LONG];
};
END.