How do I have so many partners??
1import {
2 forceSimulation,
3 forceLink,
4 forceManyBody,
5 forceCenter,
6 forceCollide,
7 type SimulationNodeDatum,
8 type SimulationLinkDatum,
9} from 'd3-force';
10import type { PolyculeData, Person, Relationship } from './types.js';
11
12export interface SimNode extends SimulationNodeDatum, Person {
13 x: number;
14 y: number;
15 connectionCount: number;
16}
17
18export interface SimLink extends SimulationLinkDatum<SimNode> {
19 source: SimNode;
20 target: SimNode;
21 relationship: Relationship;
22}
23
24const WIDTH = 960;
25const HEIGHT = 720;
26export const NODE_RADIUS = 28;
27
28/** Count edge crossings in the settled layout (lower = better) */
29function countCrossings(links: SimLink[]): number {
30 let count = 0;
31 for (let i = 0; i < links.length - 1; i++) {
32 for (let j = i + 1; j < links.length; j++) {
33 const a = links[i].source, b = links[i].target;
34 const c = links[j].source, d = links[j].target;
35 // Edges sharing a node cannot cross
36 if (a.id === c.id || a.id === d.id || b.id === c.id || b.id === d.id) continue;
37 if (segmentsIntersect(a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y)) count++;
38 }
39 }
40 return count;
41}
42
43function segmentsIntersect(
44 ax: number, ay: number, bx: number, by: number,
45 cx: number, cy: number, dx: number, dy: number,
46): boolean {
47 const d1x = bx - ax, d1y = by - ay;
48 const d2x = dx - cx, d2y = dy - cy;
49 const denom = d1x * d2y - d1y * d2x;
50 if (Math.abs(denom) < 1e-10) return false; // parallel / collinear
51 const t = ((cx - ax) * d2y - (cy - ay) * d2x) / denom;
52 const u = ((cx - ax) * d1y - (cy - ay) * d1x) / denom;
53 return t > 0 && t < 1 && u > 0 && u < 1;
54}
55
56/**
57 * BFS order starting from `forcedStart` (if given) or the highest-degree node.
58 * Places directly connected nodes consecutively on the initial circle so
59 * the force simulation starts with fewer crossings to resolve.
60 */
61function bfsOrder(people: Person[], relationships: Relationship[], forcedStart?: string): Person[] {
62 if (people.length === 0) return people;
63 const adj = new Map<string, string[]>();
64 people.forEach(p => adj.set(p.id, []));
65 relationships.forEach(r => {
66 adj.get(r.from)?.push(r.to);
67 adj.get(r.to)?.push(r.from);
68 });
69
70 const startId = forcedStart ?? [...adj.entries()].sort((a, b) => b[1].length - a[1].length)[0]?.[0] ?? people[0].id;
71 const visited = new Set<string>();
72 const queue = [startId];
73 const order: string[] = [];
74
75 while (queue.length > 0) {
76 const id = queue.shift()!;
77 if (visited.has(id)) continue;
78 visited.add(id);
79 order.push(id);
80 // Enqueue neighbours highest-degree first so hubs stay clustered
81 queue.push(
82 ...(adj.get(id) ?? [])
83 .filter(n => !visited.has(n))
84 .sort((a, b) => (adj.get(b)?.length ?? 0) - (adj.get(a)?.length ?? 0)),
85 );
86 }
87
88 const rank = new Map(order.map((id, i) => [id, i]));
89 return [...people].sort((a, b) => (rank.get(a.id) ?? 0) - (rank.get(b.id) ?? 0));
90}
91
92function runOnce(
93 orderedPeople: Person[],
94 data: PolyculeData,
95 connCount: Map<string, number>,
96 startAngle: number,
97 chargeStrength: number,
98 linkDistance: number,
99 mainNodeId?: string,
100): { nodes: SimNode[]; links: SimLink[] } {
101 const count = orderedPeople.length;
102 // Non-main nodes distributed on circle; main node starts at center
103 const nonMain = orderedPeople.filter(p => p.id !== mainNodeId);
104 const nodes: SimNode[] = orderedPeople.map((p, i) => {
105 if (p.id === mainNodeId) {
106 return {
107 ...p,
108 x: WIDTH / 2,
109 y: HEIGHT / 2,
110 connectionCount: connCount.get(p.id) ?? 0,
111 };
112 }
113 const circleIdx = nonMain.findIndex(n => n.id === p.id);
114 const angle = startAngle + (circleIdx / Math.max(nonMain.length, 1)) * 2 * Math.PI;
115 return {
116 ...p,
117 x: WIDTH / 2 + Math.cos(angle) * 220,
118 y: HEIGHT / 2 + Math.sin(angle) * 220,
119 connectionCount: connCount.get(p.id) ?? 0,
120 };
121 });
122
123 const nodeById = new Map<string, SimNode>(nodes.map(n => [n.id, n]));
124 const links: SimLink[] = data.relationships.map(r => ({
125 source: nodeById.get(r.from)!,
126 target: nodeById.get(r.to)!,
127 relationship: r,
128 }));
129
130 // Pin main node at center for the entire simulation so others orbit around it
131 const mainNode = mainNodeId ? nodeById.get(mainNodeId) : undefined;
132 if (mainNode) {
133 mainNode.fx = WIDTH / 2;
134 mainNode.fy = HEIGHT / 2;
135 }
136
137 const sim = forceSimulation<SimNode>(nodes)
138 .force(
139 'link',
140 forceLink<SimNode, SimLink>(links)
141 .id(d => d.id)
142 .distance(linkDistance)
143 .strength(0.35),
144 )
145 .force('charge', forceManyBody<SimNode>().strength(chargeStrength))
146 .force('center', forceCenter(WIDTH / 2, HEIGHT / 2).strength(0.06))
147 .force('collision', forceCollide<SimNode>(NODE_RADIUS + 40))
148 .alphaDecay(0.015)
149 .stop();
150
151 const iterations = Math.ceil(Math.log(sim.alphaMin()) / Math.log(1 - sim.alphaDecay()));
152 for (let i = 0; i < iterations; ++i) sim.tick();
153
154 // Release pin — positions are baked in, no longer need fx/fy
155 if (mainNode) {
156 mainNode.fx = undefined;
157 mainNode.fy = undefined;
158 }
159
160 return { nodes, links };
161}
162
163export function simulate(data: PolyculeData): { nodes: SimNode[]; links: SimLink[] } {
164 const count = data.people.length;
165 if (count === 0) return { nodes: [], links: [] };
166
167 // Pre-compute connection counts for node scaling
168 const connCount = new Map<string, number>();
169 data.people.forEach(p => connCount.set(p.id, 0));
170 data.relationships.forEach(r => {
171 connCount.set(r.from, (connCount.get(r.from) ?? 0) + 1);
172 connCount.set(r.to, (connCount.get(r.to) ?? 0) + 1);
173 });
174
175 // Scale forces with graph size so denser graphs spread out properly
176 const chargeStrength = -Math.max(800, count * 140);
177 const linkDistance = Math.max(180, 140 + count * 10);
178
179 const mainNodeId = data.settings.mainNode;
180
181 // Three initial orderings × four circle rotations = up to 12 candidates.
182 // Pick the settled layout with the fewest edge crossings.
183 // When mainNode is set, always start BFS from it so its neighbours radiate outward.
184 const orderings = [
185 data.people,
186 bfsOrder(data.people, data.relationships, mainNodeId),
187 [...data.people].sort((a, b) => (connCount.get(b.id) ?? 0) - (connCount.get(a.id) ?? 0)),
188 ];
189 const ROTATIONS = 4;
190
191 let best: { nodes: SimNode[]; links: SimLink[]; crossings: number } | null = null;
192
193 outer:
194 for (const ordering of orderings) {
195 for (let r = 0; r < ROTATIONS; r++) {
196 const startAngle = (r / ROTATIONS) * 2 * Math.PI;
197 const result = runOnce(ordering, data, connCount, startAngle, chargeStrength, linkDistance, mainNodeId);
198 const crossings = countCrossings(result.links);
199 if (!best || crossings < best.crossings) {
200 best = { ...result, crossings };
201 if (crossings === 0) break outer; // perfect layout — stop early
202 }
203 }
204 }
205
206 return { nodes: best!.nodes, links: best!.links };
207}