colorClass: CardHashTableThreaded.Class = [GetColorDataKey, SetColorDataLink, GetColorDataLink];
sizeH: Histograms.Histogram ~ Histograms.Create1D[factor: RealFns.Power[2, 0.25], offset: 1, logarithmic: TRUE];
absExamsPerCompH: Histograms.Histogram ~ Histograms.Create1D[factor: RealFns.Power[2, 0.25], offset: 1, logarithmic: TRUE];
absExamsPerPass: Histograms.Histogram ~ Histograms.Create1D[factor: RealFns.Power[2, 0.25], offset: 1, logarithmic: TRUE];
DisplayStats:
PUBLIC
PROC ~ {
ok: BOOL ← FALSE;
Installit: PROC ~ {ok ← NOT CommandTool.Install["HistogramsViewing", NIL].failed};
FSExtras.DoInWDir[installDir, Installit];
IF NOT ok THEN RETURN;
IF v1=NIL OR v1.destroyed THEN v1 ← HistogramsViewing.Show[h: passesH, viewerInit: [name: "Comparisons doing x passes"], updatePeriod: 10];
IF v2=NIL OR v2.destroyed THEN v2 ← HistogramsViewing.Show[h: sizeH, viewerInit: [name: "Subtrees of size x"], format: "%g", updatePeriod: 10];
IF v3=NIL OR v3.destroyed THEN v3 ← HistogramsViewing.Show[h: relExamsPerCompH, viewerInit: [name: "Comparisons doing x work/size"], format: "%g", updatePeriod: 10];
IF v4=NIL OR v4.destroyed THEN v4 ← HistogramsViewing.Show[h: relExamsPerPassH, viewerInit: [name: "Passes doing x work/size"], format: "%g", updatePeriod: 10];
IF v5=NIL OR v5.destroyed THEN v5 ← HistogramsViewing.Show[h: absExamsPerCompH, viewerInit: [name: "Comparisons doing x work"], format: "%g", updatePeriod: 10];
IF v6=NIL OR v6.destroyed THEN v6 ← HistogramsViewing.Show[h: absExamsPerPass, viewerInit: [name: "Passes doing x work"], format: "%g", updatePeriod: 10];
RETURN};
CompareGraphs:
PUBLIC
PROC [descriptions: RealGraphDescriptions, a, b: CellType, trace: SymTab.Ref ←
NIL,
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;
totalSize: REAL ← 0.0;
totalExams, examsThisPass: CARD ← 0;
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);
IF trace#NIL AND trace.Fetch[VerboseVName[v]].found THEN Log[IF GetSuspect[nv] THEN "(%g)%g +| %08x * %08x (%g)\n" ELSE "(%g)%g += %08x * %08x (%g)\n", [rope[descriptions[GetGraph[v]]]], [rope[VerboseVName[v]]], [cardinal[edgeColor]], [cardinal[OldColor[nv]]], [rope[VerboseVName[nv]]] ];
};
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;
examsThisPass ← examsThisPass+1;
};
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];
examsThisPass ← examsThisPass+1;
};
ms: NAT = IF mirrors THEN 1 ELSE 0;
hts: CARDINAL ← MAX[Real.Round[sizeFactor * RealFns.SqRt[a.size + INT[b.size] + ms + ms]], MinHashSize];
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;
totalSize ← a.size + REAL[b.size] + ms + ms;
IF totalSize=0.0 THEN totalSize ← 1.0E-10;
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 ← NIL;
QCount: CARDINAL ← 0;
isAll: BOOL ← TRUE;
someMC, someSuspect: BOOL ← FALSE;
IF abort^ THEN RETURN [FALSE, FALSE, NIL];
Initialize[];
IF abort^ THEN RETURN [FALSE, FALSE, NIL];
totalExams ← examsThisPass;
sizeH.IncrementTransformed[xmin: 1, xmax: 4.0E9, x: totalSize];
absExamsPerPass.IncrementTransformed[xmin: 1, xmax: 4.0E9, x: examsThisPass];
relExamsPerPassH.IncrementTransformed[xmin: 0, xmax: 1000, x: examsThisPass/totalSize];
IF debug
THEN {
CSC.PushTimer[$log4Compare];
WriteAll["CompareCDs Initialized", descriptions, a, b, oldColorData, curColorData !UNWIND => CSC.PopTimer[$log4Compare]];
CSC.PopTimer[$log4Compare]};
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;
examsThisPass ← 0;
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;
totalExams ← totalExams + examsThisPass;
absExamsPerPass.IncrementTransformed[xmin: 1, xmax: 4.0E9, x: examsThisPass];
relExamsPerPassH.IncrementTransformed[xmin: 0, xmax: 1000, x: examsThisPass/totalSize];
QCount ← 0;
someSuspect ← FALSE;
[] ← curColorData.Pairs[ComputeUnique];
[] ← curColorData.Pairs[QueueFrontier];
IF debug
THEN {
CSC.PushTimer[$log4Compare];
{ENABLE UNWIND => CSC.PopTimer[$log4Compare];
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]};
CSC.PopTimer[$log4Compare]};
ENDLOOP;
passesH.IncrementTransformed[xmin: 0, xmax: 4.0E9, x: pass];
relExamsPerCompH.IncrementTransformed[xmin: 1, xmax: 4.0E9, x: totalExams/totalSize];
absExamsPerCompH.IncrementTransformed[xmin: 1, xmax: 4.0E9, x: totalExams];
equiv ← nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;
Finalize[];
END;