nandi.uk
This repository has no description
5.7 kB
181 lines
1/**
2 * Shared island utilities: canonical ID, component types, BFS, DB access.
3 */
4
5import { resolve } from 'node:path';
6import { createHash } from 'node:crypto';
7import { Database } from 'bun:sqlite';
8
9const CARRY_DIR = process.env.CARRY_DIR ?? '/home/nandi/.local/share/carry-vault';
10const DB_PATH = process.env.ISLAND_DETECT_DB ?? resolve(CARRY_DIR, '.island-detect.db');
11
12export interface Component {
13 nodes: Set<string>;
14 dids: Set<string>;
15 lexmin: string;
16 centroid: string;
17 islandId: string;
18}
19
20export interface EdgeRow {
21 source: string;
22 target: string;
23 relation: string | null;
24 did: string;
25 atUri: string | null;
26}
27
28// --- Canonical island ID: first 12 hex chars of SHA-256(centroid) ---
29
30export function islandId(centroid: string): string {
31 return createHash('sha256').update(centroid).digest('hex').slice(0, 12);
32}
33
34// --- Centroid: vertex with highest closeness centrality (smallest avg distance) ---
35
36export function computeCentroid(adj: Map<string, Set<string>>, nodes: Set<string>): string {
37 if (nodes.size <= 1) return [...nodes][0] ?? '';
38
39 let bestNode = '';
40 let bestAvg = Infinity;
41
42 for (const start of nodes) {
43 // BFS from start
44 const dist = new Map<string, number>();
45 dist.set(start, 0);
46 const queue = [start];
47 while (queue.length > 0) {
48 const current = queue.shift()!;
49 for (const neighbor of adj.get(current) ?? []) {
50 if (!dist.has(neighbor) && nodes.has(neighbor)) {
51 dist.set(neighbor, dist.get(current)! + 1);
52 queue.push(neighbor);
53 }
54 }
55 }
56
57 // Average distance to all reachable nodes
58 let totalDist = 0;
59 let reachable = 0;
60 for (const [node, d] of dist) {
61 if (nodes.has(node)) {
62 totalDist += d;
63 reachable++;
64 }
65 }
66
67 const avg = reachable > 0 ? totalDist / reachable : Infinity;
68 if (avg < bestAvg) {
69 bestAvg = avg;
70 bestNode = start;
71 }
72 }
73
74 return bestNode;
75}
76
77// --- SQLite ---
78
79export function openDb(): Database {
80 return new Database(DB_PATH, { readonly: true });
81}
82
83// --- Connected components (BFS) ---
84
85export function findComponents(db: Database): Component[] {
86 const adj = new Map<string, Set<string>>();
87 const edgeDids = new Map<string, Set<string>>();
88
89 const rows = db.query('SELECT source, target, did FROM edges').all() as Array<{ source: string; target: string; did: string }>;
90 for (const row of rows) {
91 const s = row.source;
92 const t = row.target;
93 if (!adj.has(s)) adj.set(s, new Set());
94 if (!adj.has(t)) adj.set(t, new Set());
95 adj.get(s)!.add(t);
96 adj.get(t)!.add(s);
97 if (!edgeDids.has(s)) edgeDids.set(s, new Set());
98 if (!edgeDids.has(t)) edgeDids.set(t, new Set());
99 edgeDids.get(s)!.add(row.did);
100 edgeDids.get(t)!.add(row.did);
101 }
102
103 const visited = new Set<string>();
104 const components: Component[] = [];
105
106 for (const node of adj.keys()) {
107 if (visited.has(node)) continue;
108 const compNodes = new Set<string>();
109 const compDids = new Set<string>();
110 const queue = [node];
111 while (queue.length > 0) {
112 const current = queue.pop()!;
113 if (visited.has(current)) continue;
114 visited.add(current);
115 compNodes.add(current);
116 for (const did of edgeDids.get(current) ?? []) compDids.add(did);
117 for (const neighbor of adj.get(current) ?? []) {
118 if (!visited.has(neighbor)) queue.push(neighbor);
119 }
120 }
121 const lexmin = [...compNodes].sort()[0];
122 const centroid = computeCentroid(adj, compNodes);
123 components.push({ nodes: compNodes, dids: compDids, lexmin, centroid, islandId: islandId(centroid) });
124 }
125
126 return components.sort((a, b) => b.nodes.size - a.nodes.size);
127}
128
129/** Find a component by its island ID (centroid hash). */
130export function findComponentById(db: Database, targetId: string): Component | undefined {
131 return findComponents(db).find((c) => c.islandId === targetId);
132}
133
134/** Fetch edges for a component from the DB. */
135export function fetchComponentEdges(db: Database, component: Component): EdgeRow[] {
136 const nodePlaceholders = [...component.nodes].map(() => '?').join(',');
137 const nodeValues = [...component.nodes];
138
139 // at_uri column may not exist yet — try with it, fall back without
140 let edges: EdgeRow[];
141 try {
142 edges = db.query(
143 `SELECT source, target, relation, did, at_uri as atUri FROM edges WHERE source IN (${nodePlaceholders}) OR target IN (${nodePlaceholders})`,
144 ).all(...nodeValues, ...nodeValues) as EdgeRow[];
145 } catch {
146 edges = db.query(
147 `SELECT source, target, relation, did, NULL as atUri FROM edges WHERE source IN (${nodePlaceholders}) OR target IN (${nodePlaceholders})`,
148 ).all(...nodeValues, ...nodeValues) as EdgeRow[];
149 }
150
151 // Deduplicate (same source+target from multiple DIDs)
152 const seen = new Set<string>();
153 const unique: EdgeRow[] = [];
154 for (const e of edges) {
155 const key = `${e.source}::${e.target}`;
156 if (!seen.has(key)) {
157 seen.add(key);
158 unique.push(e);
159 }
160 }
161 return unique;
162}
163
164/** Resolve handles for a set of DIDs. */
165export function resolveDidHandles(db: Database, dids: Set<string>): Map<string, string | null> {
166 const handles = new Map<string, string | null>();
167 if (dids.size === 0) return handles;
168 const placeholders = [...dids].map(() => '?').join(',');
169 const rows = db.query(`SELECT did, handle FROM dids WHERE did IN (${placeholders})`).all(...dids) as Array<{ did: string; handle: string | null }>;
170 for (const r of rows) handles.set(r.did, r.handle);
171 return handles;
172}
173
174/** Extract domain from a URL for display. */
175export function domainFromUrl(url: string): string {
176 try {
177 return new URL(url).hostname.replace(/^www\./, '');
178 } catch {
179 return url;
180 }
181}