Something went wrong. Try again.
How do I have so many partners??
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208import { forceSimulation, forceLink, forceManyBody, forceCenter, forceCollide, type SimulationNodeDatum, type SimulationLinkDatum,} from 'd3-force';import type { PolyculeData, Person, Relationship } from './types.js';
export interface SimNode extends SimulationNodeDatum, Person { x: number; y: number; connectionCount: number;}
export interface SimLink extends SimulationLinkDatum<SimNode> { source: SimNode; target: SimNode; relationship: Relationship;}
const WIDTH = 960;const HEIGHT = 720;export const NODE_RADIUS = 28;
/** Count edge crossings in the settled layout (lower = better) */function countCrossings(links: SimLink[]): number { let count = 0; for (let i = 0; i < links.length - 1; i++) { for (let j = i + 1; j < links.length; j++) { const a = links[i].source, b = links[i].target; const c = links[j].source, d = links[j].target; // Edges sharing a node cannot cross if (a.id === c.id || a.id === d.id || b.id === c.id || b.id === d.id) continue; if (segmentsIntersect(a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y)) count++; } } return count;}
function segmentsIntersect( ax: number, ay: number, bx: number, by: number, cx: number, cy: number, dx: number, dy: number,): boolean { const d1x = bx - ax, d1y = by - ay; const d2x = dx - cx, d2y = dy - cy; const denom = d1x * d2y - d1y * d2x; if (Math.abs(denom) < 1e-10) return false; // parallel / collinear const t = ((cx - ax) * d2y - (cy - ay) * d2x) / denom; const u = ((cx - ax) * d1y - (cy - ay) * d1x) / denom; return t > 0 && t < 1 && u > 0 && u < 1;}
/** * BFS order starting from `forcedStart` (if given) or the highest-degree node. * Places directly connected nodes consecutively on the initial circle so * the force simulation starts with fewer crossings to resolve. */function bfsOrder(people: Person[], relationships: Relationship[], forcedStart?: string): Person[] { if (people.length === 0) return people; const adj = new Map<string, string[]>(); people.forEach(p => adj.set(p.id, [])); relationships.forEach(r => { adj.get(r.from)?.push(r.to); adj.get(r.to)?.push(r.from); });
const startId = forcedStart ?? [...adj.entries()].sort((a, b) => b[1].length - a[1].length)[0]?.[0] ?? people[0].id; const visited = new Set<string>(); const queue = [startId]; const order: string[] = [];
while (queue.length > 0) { const id = queue.shift()!; if (visited.has(id)) continue; visited.add(id); order.push(id); // Enqueue neighbours highest-degree first so hubs stay clustered queue.push( ...(adj.get(id) ?? []) .filter(n => !visited.has(n)) .sort((a, b) => (adj.get(b)?.length ?? 0) - (adj.get(a)?.length ?? 0)), ); }
const rank = new Map(order.map((id, i) => [id, i])); return [...people].sort((a, b) => (rank.get(a.id) ?? 0) - (rank.get(b.id) ?? 0));}
function runOnce( orderedPeople: Person[], data: PolyculeData, connCount: Map<string, number>, startAngle: number, chargeStrength: number, linkDistance: number, mainNodeId?: string,): { nodes: SimNode[]; links: SimLink[] } { const count = orderedPeople.length; // Non-main nodes distributed on circle; main node starts at center const nonMain = orderedPeople.filter(p => p.id !== mainNodeId); const nodes: SimNode[] = orderedPeople.map((p, i) => { if (p.id === mainNodeId) { return { ...p, x: WIDTH / 2, y: HEIGHT / 2, connectionCount: connCount.get(p.id) ?? 0, }; } const circleIdx = nonMain.findIndex(n => n.id === p.id); const angle = startAngle + (circleIdx / Math.max(nonMain.length, 1)) * 2 * Math.PI; return { ...p, x: WIDTH / 2 + Math.cos(angle) * 220, y: HEIGHT / 2 + Math.sin(angle) * 220, connectionCount: connCount.get(p.id) ?? 0, }; });
const nodeById = new Map<string, SimNode>(nodes.map(n => [n.id, n])); const links: SimLink[] = data.relationships.map(r => ({ source: nodeById.get(r.from)!, target: nodeById.get(r.to)!, relationship: r, }));
// Pin main node at center for the entire simulation so others orbit around it const mainNode = mainNodeId ? nodeById.get(mainNodeId) : undefined; if (mainNode) { mainNode.fx = WIDTH / 2; mainNode.fy = HEIGHT / 2; }
const sim = forceSimulation<SimNode>(nodes) .force( 'link', forceLink<SimNode, SimLink>(links) .id(d => d.id) .distance(linkDistance) .strength(0.35), ) .force('charge', forceManyBody<SimNode>().strength(chargeStrength)) .force('center', forceCenter(WIDTH / 2, HEIGHT / 2).strength(0.06)) .force('collision', forceCollide<SimNode>(NODE_RADIUS + 40)) .alphaDecay(0.015) .stop();
const iterations = Math.ceil(Math.log(sim.alphaMin()) / Math.log(1 - sim.alphaDecay())); for (let i = 0; i < iterations; ++i) sim.tick();
// Release pin — positions are baked in, no longer need fx/fy if (mainNode) { mainNode.fx = undefined; mainNode.fy = undefined; }
return { nodes, links };}
export function simulate(data: PolyculeData): { nodes: SimNode[]; links: SimLink[] } { const count = data.people.length; if (count === 0) return { nodes: [], links: [] };
// Pre-compute connection counts for node scaling const connCount = new Map<string, number>(); data.people.forEach(p => connCount.set(p.id, 0)); data.relationships.forEach(r => { connCount.set(r.from, (connCount.get(r.from) ?? 0) + 1); connCount.set(r.to, (connCount.get(r.to) ?? 0) + 1); });
// Scale forces with graph size so denser graphs spread out properly const chargeStrength = -Math.max(800, count * 140); const linkDistance = Math.max(180, 140 + count * 10);
const mainNodeId = data.settings.mainNode;
// Three initial orderings × four circle rotations = up to 12 candidates. // Pick the settled layout with the fewest edge crossings. // When mainNode is set, always start BFS from it so its neighbours radiate outward. const orderings = [ data.people, bfsOrder(data.people, data.relationships, mainNodeId), [...data.people].sort((a, b) => (connCount.get(b.id) ?? 0) - (connCount.get(a.id) ?? 0)), ]; const ROTATIONS = 4;
let best: { nodes: SimNode[]; links: SimLink[]; crossings: number } | null = null;
outer: for (const ordering of orderings) { for (let r = 0; r < ROTATIONS; r++) { const startAngle = (r / ROTATIONS) * 2 * Math.PI; const result = runOnce(ordering, data, connCount, startAngle, chargeStrength, linkDistance, mainNodeId); const crossings = countCrossings(result.links); if (!best || crossings < best.crossings) { best = { ...result, crossings }; if (crossings === 0) break outer; // perfect layout — stop early } } }
return { nodes: best!.nodes, links: best!.links };}