DIRECTORY Rope, IO, AlgebraClasses; QEClusterStructure: CEDAR DEFINITIONS ~ BEGIN ROPE: TYPE ~ Rope.ROPE; Cluster: TYPE = AlgebraClasses.Object; ClusterData: TYPE = REF ClusterDataRec; ClusterDataRec: TYPE ~ RECORD [ baseCluster: Cluster, repCell: CellIndex, -- representative cell samplePoint: Object, constituentCells: Sequences.Sequence -- of Cell's, sorted into increasing order intraclusterAdjacencies: Sequences.Sequence, -- of Adjacencies, sorted into increasing (lexicographical) order. We need this to be able to find subclusters maximal with respect to the property of being contained in the boundary of some other cluster. Lemma: If one cell of cluster A is contained in the boundary of a cell of cluster B, then every cell of cluster A which is adjacent to a cell of cluster B is contained in the boundary of cluster B. basisSignature: QESignatureStructure.Signature, -- (see below) inputSignature: QESignatureStructure.Signature, -- (see below) satisfiesLocalization: BOOL _ FALSE, -- satisfies localization formula; default FALSE reflects default assumption of no localization inSolutionSet: BOOL, -- meaningless unless both this cluster and "solution set" in i-space ]; We can be keeping track of signatures of several different polynomial sequences simultaneously for a cluster, e.g. r-variate input polynomials, and basis polynomials in r and lower dimensions. Comparing names of signature Structures should enable us to keep them straight. When we construct initial clusters in i-space, signature polynomials will be be complete factors, i.e. all irreducible factors, of i-variate input polynomials. We get the signs of factors which are not i-variate basis polys (which we get from cells) by making this cells signature polys union of baseCluster signature polys and i-variate basis. ]; ClusterStructureData: TYPE = REF ClusterStructureDataRec; ClusterStructureDataRec: TYPE = RECORD [ cad: Cad ]; ClusterFromCell: AlgebraClasses.UnaryImbedOp; ExtractClusters: PROC [cad: Cad, numComponents: CARDINAL] RETURNS [clusters: SEQ.Sequence]; InitialClustersOverCluster: PROC; END. šQEClusterStructure.mesa Last Edited by: Arnon, November 19, 1987 8:31:50 am PST Structure Constructor: Clusters with respect to argument Structures. Type Abbreviations Element Representation So given clusters A and B, we first find all cells of A adjacent to a cell of B, then we use intraclusterAdjacencies to find maximal clusters among these. Rule: signature polynomials are elements of i-variate basis for some i. However nothing assumed about the order in which they occur in the PolynomialSequenceFile. Rule: a cluster's set or signature polynomials is as large as possible, i.e. is the largest collection of basis polynomials that is invariant on the constituent cells of this cluster. Thus for example, when we are not doing any pasting of clusters as we extend our cad, i.e. clusters just have one constituent cell, i.e. "original" cad algorithm, then signature polys in dimension i should be collection of all i and lower dimensional basis polynomials. Note: to get a cluster's rep cell sample point, you have to look in the stack file containing the rep cell. Assert: there will always exist a stack file containing any cluster's rep cell. Structure Instance Data Element Constructor Clusters components assumed to be of cad, and not some induced cad thereof. Components: Menus.MenuProc = { User specifies polynomials with respect to which to cluster by (*,*,@,*,*,@) tuples (@ is new FormulaOperators.Op). edgePredicate: GraphOps.EdgePredicate ~ { cell1: QET.Cell _ NARROW[v.rep]; cell2: QET.Cell _ NARROW[w.rep]; RETURN[cell1.basisSignature.structure.class.equal[cell1.basisSignature, cell2.basisSignature] ]; }; inducedCad: QET.Cad _ QEIO.GetInducedCad[cad, dimension]; numComponents: CARDINAL _ GraphOps.DetermineComponents[cad.abstractGraph, Undirected, edgePredicate]; clusters: QET.SignedRegionSeq _ Cads.ExtractClusters[inducedCad, numComponents]; QEIO.WriteSignedRegionSeq[clusters, out]; }; MaximalSignedRegions: PROC [dimension: CARDINAL, cad: Cad, primary: BOOL]; Depth-First Search connected components computation in the dimension-space cad graph, filling in the (IF primary THEN primaryRegion ELSE secondaryRegion) fields of cells. ExtractSignedRegions: PROC [dimension: CARDINAL, cad: Cad, primary: BOOL] RETURNS [SEQ.Sequence]; Extract from the dimension-space cad graph, the (IF primary THEN primaryRegion ELSE secondaryRegion) cell-field-defined regions. Element Operations firstArg _ baseCluster from LowerDimCluster environment variable. Set LowerDimCell environment variable to representative cell of baseCluster. Call ExtendCellToStack. Retrieve the stack it writes from CurrentDimStack environment variable. Build initial clusters over baseCluster, write them out as a single ClusterFile. Rep cell of each initial cluster is appropriate element of stack over rep cell of baseCluster. Cluster signature polynomials are union of baseCluster signature polynomials and this dimensional basis (cf. ClusterFile format). Κ˜Jšœ™J™7J˜JšœD™DJ™šΟk ˜ Icodešœ˜Kšœ˜Kšœ˜—Ihead2šΟnœœ ˜%Jšœ˜headšž™Kšœœœ˜—šž™Jšœ œ˜&J˜Jšœ œœ˜'šœœ˜šœ˜Jšœ˜JšœΟc˜*Jšœ˜Jšœ&Ÿ*˜Pšœ.ŸB˜pJšŸŒ˜ŒJšŸΖ˜ΖJšœ›™›—Jšœ1Ÿ˜?Jšœ1Ÿ˜?JšœœœŸ+Ÿ/˜„JšœœŸE˜ZK˜J˜JšŸ‘˜‘JšŸΩ˜ΩJšŸŒœ™£J™ΗšœΌ™ΌJ™—J˜———šœ™Kšœœœ˜9šœœœ˜(Jšœ˜K˜——šœ™Jšžœ˜-—šž™š žœœœœ œ ˜[KšœB™BK˜—šž œ™JšŸt™tšœ)™)Jšœœœ™ Jšœœœ™ JšœZ™`J™—Jšœ œœ™9Jšœœ žœ/™eJšœ œžœ™PJšœ%™)J™J™—šžœœ œœ™JKšœeœ œœ#™«K™—š žœœ œœœœ ™aKšœ0œ œœ-™€K™——šœ™šžœœ˜!Kšœ•žœύ™£K˜J˜——J˜Jšœ˜—…—@ή