layoutData = { const maxLevels = controls.maxLevels; const layoutMode = controls.layout; // Helper function to convert numbers to subscript characters function toSubscript(num) { const subscripts = '₀₁₂₃₄₅₆₇₈₉'; return String(num).split('').map(d => subscripts[parseInt(d)]).join(''); } // Helper function to convert numbers to superscript characters function toSuperscript(num) { const superscripts = '⁰¹²³⁴⁵⁶⁷⁸⁹'; return String(num).split('').map(d => superscripts[parseInt(d)]).join(''); } // Simplify GAP's StructureDescription to standard mathematical notation function simplifyGroupName(desc) { let result = desc; const p = 2; // Normalize GAP's " x " to "@" and " : " to "#" for internal processing result = result.replace(/ x /g, '@').replace(/ : /g, '#'); const elementaryPattern2 = /^(C2\s*[@x]\s*)+C2$/; if (elementaryPattern2.test(result)) { const count = (result.match(/C2/g) || []).length; const order = Math.pow(2, count); return "E" + order; } const elementaryPatternP = new RegExp("^(C" + p + "\\s*[@x]\\s*)+C" + p + "$"); if (elementaryPatternP.test(result)) { const count = (result.match(new RegExp("C" + p, 'g')) || []).length; const order = Math.pow(p, count); return "E" + order; } if (/^C2\s*[@x]\s*C2$/.test(result)) { return 'E4'; } result = result.replace(/QD(\d+)/g, 'SD$1'); const heisenbergPattern = /^$C(\d+)\s*[@x]\s*C\1$\s*[:#]\s*C\1$/; const heisMatch = result.match(heisenbergPattern); if (heisMatch) { const prime = heisMatch[1]; return "He" + prime; } return result; } function formatLabel(desc) { let simplified = simplifyGroupName(desc); // Parse the group into components // Split by common operations: @, #, ., ~, *, x // We need to handle this carefully to preserve the operations // First, let's identify all the components and operations const parts = []; const ops = []; let current = ''; let i = 0; while (i < simplified.length) { const char = simplified[i]; if (char === '@' || char === '#' || char === '.' || char === '~' || char === '*' || char === 'x') { if (current.trim()) { parts.push(current.trim()); } // Check for operation suffix (like @1, #2) let op = char; if (i + 1 < simplified.length && /\d/.test(simplified[i + 1])) { let suffix = ''; i++; while (i < simplified.length && /\d/.test(simplified[i])) { suffix += simplified[i]; i++; } op += suffix; i--; // Back up one since the loop will increment } ops.push(op); current = ''; } else if (char === ' ') { // Skip spaces } else { current += char; } i++; } if (current.trim()) { parts.push(current.trim()); } // Check if all operations are direct products (@, x, or no suffix) const allDirect = ops.every(op => op === '@' || op === 'x' || /^@\d+$/.test(op)); if (allDirect && parts.length > 0) { // Parse each part to identify elementary and cyclic groups let elementaryOrder = 1; const primeCyclics = []; // Track prime cyclic groups separately const otherParts = []; let hasElementary = false; parts.forEach(part => { // Match elementary group: E followed by number const elemMatch = part.match(/^E(\d+)$/); if (elemMatch) { elementaryOrder *= parseInt(elemMatch[1]); hasElementary = true; return; } // Match cyclic group: C followed by number const cyclicMatch = part.match(/^C(\d+)$/); if (cyclicMatch) { const order = parseInt(cyclicMatch[1]); // Check if it's a prime (for potential consolidation into elementary) const isPrime = order > 1 && (() => { for (let j = 2; j <= Math.sqrt(order); j++) { if (order % j === 0) return false; } return true; })(); if (isPrime) { primeCyclics.push({ order, label: part }); } else { // Non-prime cyclic, keep as is otherParts.push({ type: 'cyclic', order, label: part }); } return; } // Other group types - extract order if possible const orderMatch = part.match(/(\d+)/); const order = orderMatch ? parseInt(orderMatch[1]) : 0; otherParts.push({ type: 'other', order, label: part }); }); // Decide how to handle prime cyclic groups // Only consolidate into E if: // 1. There's already an E group, OR // 2. There are multiple prime cyclic groups const shouldConsolidate = hasElementary || primeCyclics.length > 1; if (shouldConsolidate) { // Multiply all prime cyclics into elementary order primeCyclics.forEach(pc => { elementaryOrder *= pc.order; }); if (elementaryOrder > 1) { otherParts.push({ type: 'elementary', order: elementaryOrder, label: 'E' + elementaryOrder }); } } else { // Keep prime cyclics as cyclic groups primeCyclics.forEach(pc => { otherParts.push({ type: 'cyclic', order: pc.order, label: pc.label }); }); // If there was a standalone E group with no prime cyclics to merge, add it back if (hasElementary && elementaryOrder > 1) { otherParts.push({ type: 'elementary', order: elementaryOrder, label: 'E' + elementaryOrder }); } } // Sort by order (highest first) otherParts.sort((a, b) => b.order - a.order); // Rebuild the label if (otherParts.length > 0) { simplified = otherParts.map(p => p.label).join('@'); } } // Apply standard formatting - convert internal symbols to display symbols return simplified .replace(/@/g, '×') // Direct product .replace(/#/g, '⋊') // Semidirect product .replace(/\./g, '↑') // Non-split central extension .replace(/~/g, '↑') // Non-split non-central (same display symbol) .replace(/\*/g, '○') // Central product .replace(/(\d+)/g, (match) => toSubscript(match)) .replace(/\s+/g, ''); } function formatFormula(formula, sourceLabel, linkType) { // Use the link type to determine the operation symbol let operation = '×'; // default for direct if (linkType === 'semidirect' || linkType === 'semidirect product' || linkType === 'split non-central') { operation = '⋊'; } else if (linkType === 'non-split-central' || linkType === 'non-split central' || linkType === 'central extension') { operation = '↑'; } else if (linkType === 'non-split-non-central' || linkType === 'non-split non-central' || linkType === 'non-central non-split') { operation = '↑'; } // Check for operation suffix in formula (like _1, _2, etc.) let operationSuffix = ''; const suffixMatch = formula.match(/_(\d+)/); if (suffixMatch) { operationSuffix = toSubscript(suffixMatch[1]); } // Build: sourceLabel + operation + C₂ return sourceLabel + operation + operationSuffix + 'C' + toSubscript(2); } const typeMap = { "direct product": "direct", "split central": "direct", "semidirect product": "semidirect", "split non-central": "semidirect", "non-split central": "non-split-central", "central extension": "non-split-central", "non-split non-central": "non-split-non-central", "non-central non-split": "non-split-non-central" }; // ============================================ // DETERMINE LEVELS FROM DISTINCT ORDERS // ============================================ // Get all distinct orders and sort them const allOrders = [...new Set(data.nodes.map(n => n.gapIndex[0]))].sort((a, b) => a - b); // Create a map from order to level (1-indexed) // Level 1 = smallest order, Level 2 = next smallest, etc. const orderToLevel = new Map(); allOrders.forEach((order, index) => { orderToLevel.set(order, index + 1); // 1-indexed levels }); // Filter nodes to only include those within maxLevels const nodes = data.nodes .filter(node => orderToLevel.get(node.gapIndex[0]) <= maxLevels) .map(node => ({ ...node, label: formatLabel(node.desc), level: orderToLevel.get(node.gapIndex[0]), order: node.gapIndex[0], class: node.isAbelian ? 'abelian' : 'non-abelian' })); const nodeIds = new Set(nodes.map(n => n.id)); const nodeMap = new Map(nodes.map(n => [n.id, n])); // Filter and transform links const links = data.links .filter(link => nodeIds.has(link.source) && nodeIds.has(link.target)) .map(link => { const sourceNode = nodeMap.get(link.source); const mappedType = typeMap[link.type] || link.type; return { ...link, label: formatFormula(link.formula, sourceNode ? sourceNode.label : '', link.type), type: mappedType }; }); // Configuration const config = { levelWidth: 200, minNodeSpacing: 36, paddingLeft: 50, paddingRight: 120, paddingY: 70, boundingPadding: 20, zoomExtent: [0.1, 4], transitionDuration: 100, // Radial config radialMinOuterRadius: 150, radialLevelSpacing: 60, radialMinLevelSpacing: 80 // Minimum distance between any two levels }; // ============================================ // LINEAR LAYOUT ALGORITHM // ============================================ function computeLinearLayout(nodes, links, config) { const { minNodeSpacing, paddingLeft, paddingRight, paddingY } = config; const levels = d3.group(nodes, d => d.level); const sortedLevelKeys = Array.from(levels.keys()).sort((a, b) => a - b); const maxLevel = Math.max(...sortedLevelKeys); const minLevel = Math.min(...sortedLevelKeys); for (const [level, levelNodes] of levels) { levelNodes.forEach((node, i) => { node.index = i; }); } // Calculate level heights (number of nodes * spacing) const levelHeights = new Map(); for (const [level, levelNodes] of levels) { const height = (levelNodes.length - 1) * minNodeSpacing; levelHeights.set(level, height); } // Calculate dynamic level widths based on the height of adjacent levels // Space between levels = 1/3 the max height of the two adjacent levels const levelPositions = new Map(); let currentX = paddingLeft; for (let i = 0; i < sortedLevelKeys.length; i++) { const level = sortedLevelKeys[i]; levelPositions.set(level, currentX); if (i < sortedLevelKeys.length - 1) { const nextLevel = sortedLevelKeys[i + 1]; const currentHeight = levelHeights.get(level); const nextHeight = levelHeights.get(nextLevel); const maxHeight = Math.max(currentHeight, nextHeight); // Level spacing = 1/3 the max height of adjacent levels, with a minimum const minLevelWidth = 100; // Minimum spacing between levels const levelSpacing = Math.max(minLevelWidth, maxHeight / 3); currentX += levelSpacing; } } function getLinksBetweenLevels(lowerLevel, upperLevel) { return links.filter(link => { const sourceNode = nodes.find(n => n.id === link.source); const targetNode = nodes.find(n => n.id === link.target); return sourceNode && targetNode && sourceNode.level === lowerLevel && targetNode.level === upperLevel; }); } function optimizeLevel(levelToOptimize, fixedLevel, isUpperFixed) { const levelNodes = levels.get(levelToOptimize); const fixedNodes = levels.get(fixedLevel); // Guard against undefined levels if (!levelNodes || !fixedNodes) return; const levelLinks = getLinksBetweenLevels( isUpperFixed ? levelToOptimize : fixedLevel, isUpperFixed ? fixedLevel : levelToOptimize ); levelNodes.forEach(node => { const connectedLinks = levelLinks.filter(link => isUpperFixed ? link.source === node.id : link.target === node.id ); if (connectedLinks.length > 0) { const sum = connectedLinks.reduce((acc, link) => { const connectedId = isUpperFixed ? link.target : link.source; const connectedNode = fixedNodes.find(n => n.id === connectedId); return acc + (connectedNode ? connectedNode.index : 0); }, 0); node.barycenter = sum / connectedLinks.length; } else { node.barycenter = node.index; } }); levelNodes.sort((a, b) => a.barycenter - b.barycenter); levelNodes.forEach((node, i) => { node.index = i; }); } // Iterate over actual level keys instead of assuming consecutive integers for (let i = sortedLevelKeys.length - 1; i > 0; i--) { optimizeLevel(sortedLevelKeys[i - 1], sortedLevelKeys[i], true); } for (let i = 0; i < sortedLevelKeys.length - 1; i++) { optimizeLevel(sortedLevelKeys[i + 1], sortedLevelKeys[i], false); } for (let pass = 0; pass < 3; pass++) { for (let i = sortedLevelKeys.length - 1; i > 0; i--) { optimizeLevel(sortedLevelKeys[i - 1], sortedLevelKeys[i], true); } for (let i = 0; i < sortedLevelKeys.length - 1; i++) { optimizeLevel(sortedLevelKeys[i + 1], sortedLevelKeys[i], false); } } // Position nodes horizontally using the dynamic level positions nodes.forEach(node => { node.x = levelPositions.get(node.level); }); const highestLevelNodes = levels.get(maxLevel); highestLevelNodes.sort((a, b) => a.index - b.index); const totalHeight = (highestLevelNodes.length - 1) * minNodeSpacing; highestLevelNodes.forEach((node, i) => { node.y = paddingY + i * minNodeSpacing; }); // Iterate backwards through actual levels for (let i = sortedLevelKeys.length - 2; i >= 0; i--) { const level = sortedLevelKeys[i]; const currentLevelNodes = levels.get(level); if (!currentLevelNodes) continue; currentLevelNodes.sort((a, b) => a.index - b.index); currentLevelNodes.forEach(node => { const connectedLinks = links.filter(link => link.source === node.id); const connectedNodes = connectedLinks.map(link => nodes.find(n => n.id === link.target) ).filter(Boolean); if (connectedNodes.length > 0) { node.y = d3.mean(connectedNodes, n => n.y); } else { node.y = paddingY + node.index * minNodeSpacing; } }); currentLevelNodes.sort((a, b) => a.index - b.index); for (let j = 1; j < currentLevelNodes.length; j++) { const prev = currentLevelNodes[j - 1]; const curr = currentLevelNodes[j]; if (curr.y - prev.y < minNodeSpacing) { curr.y = prev.y + minNodeSpacing; } } const levelMinY = d3.min(currentLevelNodes, n => n.y); const levelMaxY = d3.max(currentLevelNodes, n => n.y); const levelCenter = (levelMinY + levelMaxY) / 2; const targetCenter = paddingY + totalHeight / 2; const adjustment = (targetCenter - levelCenter) * 0.3; currentLevelNodes.forEach(node => { node.y += adjustment; }); } // Calculate final dimensions based on dynamic positions const lastLevel = sortedLevelKeys[sortedLevelKeys.length - 1]; const calculatedWidth = levelPositions.get(lastLevel) + paddingRight; const calculatedHeight = paddingY * 2 + d3.max(nodes, n => n.y); return { nodes, links, width: calculatedWidth, height: calculatedHeight, maxLevel, minLevel, paddingLeft, layoutType: 'linear' }; } // ============================================ // RADIAL LAYOUT ALGORITHM // ============================================ function computeRadialLayout(nodes, links, config) { const { radialLevelSpacing, radialMinOuterRadius, radialMinLevelSpacing } = config; const levels = d3.group(nodes, d => d.level); const sortedLevelKeys = Array.from(levels.keys()).sort((a, b) => a - b); const maxLevel = Math.max(...sortedLevelKeys); const minLevel = Math.min(...sortedLevelKeys); const numLevels = sortedLevelKeys.length; for (const [level, levelNodes] of levels) { levelNodes.forEach((node, i) => { node.index = i; }); } function getLinksBetweenLevels(lowerLevel, upperLevel) { return links.filter(link => { const sourceNode = nodes.find(n => n.id === link.source); const targetNode = nodes.find(n => n.id === link.target); return sourceNode && targetNode && sourceNode.level === lowerLevel && targetNode.level === upperLevel; }); } function circularMean(angles) { if (angles.length === 0) return 0; let sumSin = 0, sumCos = 0; for (const a of angles) { sumSin += Math.sin(a); sumCos += Math.cos(a); } return Math.atan2(sumSin / angles.length, sumCos / angles.length); } function normalizeAngle(angle) { while (angle > Math.PI) angle -= 2 * Math.PI; while (angle < -Math.PI) angle += 2 * Math.PI; return angle; } const pillHeight = 24; function minAngularGap(radius) { if (radius === 0) return 0; return (pillHeight * 2) / radius; } const highestLevelNodes = levels.get(maxLevel); highestLevelNodes.forEach((node, i) => { node.index = i; }); const n = highestLevelNodes.length; highestLevelNodes.sort((a, b) => a.index - b.index); highestLevelNodes.forEach((node, i) => { if (n === 1) { node.angle = 0; } else { node.angle = (2 * Math.PI * i) / n; } }); const levelRadii = new Map(); // Calculate the outer radius based on the highest level's node count const highestCount = highestLevelNodes.length; const highestCircumference = highestCount * pillHeight * 2; const outerRadius = Math.max(radialMinOuterRadius, highestCircumference / (2 * Math.PI)); levelRadii.set(maxLevel, outerRadius); // Calculate the inner radius for the lowest level const lowestLevelNodes = levels.get(minLevel); const lowestCount = lowestLevelNodes.length; let innerRadius; if (lowestCount === 1) { innerRadius = 0; } else { const lowestCircumference = lowestCount * pillHeight * 2; innerRadius = lowestCircumference / (2 * Math.PI); } // Ensure minimum total span based on minimum level spacing const minTotalSpan = (numLevels - 1) * radialMinLevelSpacing; const currentSpan = outerRadius - innerRadius; // If the current span is too small, expand the outer radius let adjustedOuterRadius = outerRadius; if (currentSpan < minTotalSpan) { adjustedOuterRadius = innerRadius + minTotalSpan; levelRadii.set(maxLevel, adjustedOuterRadius); } levelRadii.set(minLevel, innerRadius); // Calculate intermediate level radii if (numLevels > 2) { // First, calculate density-based radii (what each level needs based on node count) const densityRadii = new Map(); for (let i = 1; i < sortedLevelKeys.length - 1; i++) { const level = sortedLevelKeys[i]; const levelNodes = levels.get(level); if (!levelNodes) continue; const nodeCount = levelNodes.length; const requiredCircumference = nodeCount * pillHeight * 2; densityRadii.set(level, requiredCircumference / (2 * Math.PI)); } // Calculate evenly spaced radii const finalOuterRadius = levelRadii.get(maxLevel); const levelSpacing = (finalOuterRadius - innerRadius) / (numLevels - 1); // Assign radii with minimum spacing enforcement for (let i = 1; i < sortedLevelKeys.length - 1; i++) { const level = sortedLevelKeys[i]; const levelIndex = i; // Use index in sorted array const evenlySpacedRadius = innerRadius + levelIndex * levelSpacing; const densityRadius = densityRadii.get(level) || evenlySpacedRadius; // Blend evenly spaced with density-based let blendedRadius = (evenlySpacedRadius + densityRadius) / 2; // Enforce minimum spacing from the previous level const prevLevel = sortedLevelKeys[i - 1]; const prevRadius = levelRadii.get(prevLevel); if (blendedRadius - prevRadius < radialMinLevelSpacing) { blendedRadius = prevRadius + radialMinLevelSpacing; } levelRadii.set(level, blendedRadius); } // Second pass: if any level got pushed too close to the outer radius, // we may need to expand the outer radius further const secondToLastLevel = sortedLevelKeys[sortedLevelKeys.length - 2]; const secondToLastRadius = levelRadii.get(secondToLastLevel); const finalOuterRadius2 = levelRadii.get(maxLevel); if (finalOuterRadius2 - secondToLastRadius < radialMinLevelSpacing) { levelRadii.set(maxLevel, secondToLastRadius + radialMinLevelSpacing); } } // Process levels from second-highest down to lowest for (let i = sortedLevelKeys.length - 2; i >= 0; i--) { const level = sortedLevelKeys[i]; const levelNodes = levels.get(level); if (!levelNodes) continue; const outerLevel = sortedLevelKeys[i + 1]; const outerNodes = levels.get(outerLevel); if (!outerNodes) continue; const levelLinks = getLinksBetweenLevels(level, outerLevel); const radius = levelRadii.get(level); if (levelNodes.length === 1 && radius === 0) { levelNodes[0].angle = 0; continue; } levelNodes.forEach(node => { const connectedLinks = levelLinks.filter(link => link.source === node.id); if (connectedLinks.length > 0) { const connectedAngles = connectedLinks.map(link => { const connectedNode = outerNodes.find(n => n.id === link.target); return connectedNode ? connectedNode.angle : 0; }); node.targetAngle = circularMean(connectedAngles); } else { node.targetAngle = (2 * Math.PI * node.index) / levelNodes.length; } }); levelNodes.sort((a, b) => { const normA = normalizeAngle(a.targetAngle); const normB = normalizeAngle(b.targetAngle); return normA - normB; }); levelNodes.forEach((node, idx) => { node.index = idx; node.angle = node.targetAngle; }); const minGap = minAngularGap(radius); const maxIterations = 50; for (let iter = 0; iter < maxIterations; iter++) { let hasOverlap = false; for (let j = 0; j < levelNodes.length; j++) { const curr = levelNodes[j]; const next = levelNodes[(j + 1) % levelNodes.length]; let gap = next.angle - curr.angle; if (j === levelNodes.length - 1) { gap = (next.angle + 2 * Math.PI) - curr.angle; } gap = normalizeAngle(gap); if (gap < 0) gap += 2 * Math.PI; if (gap < minGap) { hasOverlap = true; const adjustment = (minGap - gap) / 2; curr.angle = normalizeAngle(curr.angle - adjustment); next.angle = normalizeAngle(next.angle + adjustment); } } levelNodes.forEach(node => { const diff = normalizeAngle(node.targetAngle - node.angle); node.angle = normalizeAngle(node.angle + diff * 0.1); }); if (!hasOverlap) break; } let hasOverlap = false; for (let j = 0; j < levelNodes.length; j++) { const curr = levelNodes[j]; const next = levelNodes[(j + 1) % levelNodes.length]; let gap = next.angle - curr.angle; if (j === levelNodes.length - 1) { gap = (next.angle + 2 * Math.PI) - curr.angle; } gap = normalizeAngle(gap); if (gap < 0) gap += 2 * Math.PI; if (gap < minGap * 0.9) { hasOverlap = true; break; } } if (hasOverlap) { const nodeCount = levelNodes.length; let bestNode = levelNodes[0]; let bestDiff = Math.abs(normalizeAngle(levelNodes[0].targetAngle - levelNodes[0].angle)); levelNodes.forEach(node => { const diff = Math.abs(normalizeAngle(node.targetAngle - node.angle)); if (diff < bestDiff) { bestDiff = diff; bestNode = node; } }); const startAngle = bestNode.targetAngle; const anchorIndex = levelNodes.indexOf(bestNode); levelNodes.forEach((node, idx) => { const offset = idx - anchorIndex; node.angle = normalizeAngle(startAngle + (2 * Math.PI * offset) / nodeCount); }); } } nodes.forEach(node => { const radius = levelRadii.get(node.level); node.radius = radius; if (radius === 0) { node.x = 0; node.y = 0; node.angle = 0; } else { node.x = radius * Math.cos(node.angle); node.y = radius * Math.sin(node.angle); } }); const finalOuterRadius = levelRadii.get(maxLevel); const maxRadius = finalOuterRadius + 60; const size = maxRadius * 2 + 100; return { nodes, links, width: size, height: size, maxLevel, minLevel, centerX: size / 2, centerY: size / 2, levelRadii, layoutType: 'radial' }; } const result = layoutMode === 'radial' ? computeRadialLayout([...nodes], links, config) : computeLinearLayout([...nodes], links, config); return { ...result, config, toSubscript, orderToLevel }; }