| |
| |
| (function (scope) { |
| 'use strict'; |
| const quantile = (sorted, p) => { |
| if (!sorted.length) return 0; |
| const pos = (sorted.length - 1) * p, i = Math.floor(pos), a = pos - i; |
| return sorted[i] + (sorted[Math.min(i + 1, sorted.length - 1)] - sorted[i]) * a; |
| }; |
| const median = a => quantile(a, .5); |
| const mean = a => a.length ? a.reduce((x, y) => x + y, 0) / a.length : 0; |
| const frequencies = a => { |
| const f = new Map(); |
| for (const n of a) f.set(n, (f.get(n) || 0) + 1); |
| return [...f].sort((a, b) => a[0] - b[0]).map(([degree, count]) => ({degree, count})); |
| }; |
| function createAccumulator() { |
| const ids = new Map(), names = [], parent = [], rank = [], out = [], inc = [], outRaw = [], inRaw = [], |
| neighbors = [], outgoingNeighbors = [], outgoingRels = [], incidentRels = [], |
| relIds = new Map(), relNames = [], relFreq = [], relEdges = [], unique = new Set(); |
| let rows = 0, simpleEdges = 0, bad = 0, selfLoops = 0; |
| function node(label) { |
| let id = ids.get(label); |
| if (id !== undefined) return id; |
| id = names.length; ids.set(label,id); names.push(label); parent.push(id); rank.push(1); |
| out.push(0); inc.push(0); outRaw.push(0); inRaw.push(0); |
| neighbors.push(new Set()); outgoingNeighbors.push(new Set()); outgoingRels.push(new Set()); incidentRels.push(new Set()); |
| return id; |
| } |
| function relation(label) { |
| let id = relIds.get(label); |
| if (id !== undefined) return id; |
| id = relNames.length; relIds.set(label,id); relNames.push(label); relFreq.push(0); relEdges.push([]); |
| return id; |
| } |
| function root(x) { let y=x; while(parent[y]!==y)y=parent[y];while(parent[x]!==x){const k=parent[x];parent[x]=y;x=k;}return y; } |
| function unite(a,b) {a=root(a);b=root(b);if(a===b)return;if(rank[a]<rank[b])[a,b]=[b,a];parent[b]=a;rank[a]+=rank[b];} |
| function add(h,r,t){ |
| h=String(h??'').trim();r=String(r??'').trim();t=String(t??'').trim(); |
| if(!h||!r||!t){bad++;return;} |
| const a=node(h), b=node(t), relationId=relation(r); rows++; |
| outRaw[a]++;inRaw[b]++;relFreq[relationId]++; |
| const key=`${a}:${relationId}:${b}`; |
| if(unique.has(key))return; |
| unique.add(key);out[a]++;inc[b]++; |
| outgoingNeighbors[a].add(b);outgoingRels[a].add(relationId); |
| incidentRels[a].add(relationId);incidentRels[b].add(relationId); |
| relEdges[relationId].push([a,b]); |
| if(a===b)selfLoops++; |
| if(!neighbors[a].has(b)){neighbors[a].add(b);if(a!==b) neighbors[b].add(a);simpleEdges++;unite(a,b);} |
| } |
| function addNode(n){n=String(n??'').trim();if(n)node(n);} |
| function output(options={}){ |
| const n=names.length, m=relNames.length; |
| const outValues=[...out].sort((a,b)=>a-b), inValues=[...inc].sort((a,b)=>a-b), |
| onValues=outgoingNeighbors.map(s=>s.size).sort((a,b)=>a-b), |
| orValues=outgoingRels.map(s=>s.size).sort((a,b)=>a-b); |
| const sums=new Map();for(let i=0;i<n;i++){const p=root(i);sums.set(p,(sums.get(p)||0)+1);} |
| const wcc=[...sums.values()].sort((a,b)=>a-b), largest=wcc[wcc.length-1]||0; |
| const s={ |
| triplet_rows:rows, unique_triples:unique.size, duplicate_triplet_rows:rows-unique.size, |
| entities:n,relations:m,self_loop_triples:selfLoops,zero_out_degree_nodes:out.filter(v=>v===0).length, |
| out_degree_mean:mean(outValues),out_degree_median:median(outValues),out_degree_p90:quantile(outValues,.9), |
| out_degree_p95:quantile(outValues,.95),out_degree_p99:quantile(outValues,.99),out_degree_max:outValues[n-1]||0, |
| in_degree_mean:mean(inValues),in_degree_median:median(inValues),in_degree_p90:quantile(inValues,.9), |
| in_degree_p95:quantile(inValues,.95),in_degree_p99:quantile(inValues,.99),in_degree_max:inValues[n-1]||0, |
| unique_out_neighbors_mean:mean(onValues),unique_out_neighbors_median:median(onValues), |
| unique_out_neighbors_p90:quantile(onValues,.9), unique_out_neighbors_p95:quantile(onValues,.95), |
| unique_out_neighbors_p99:quantile(onValues,.99),unique_out_neighbors_max:onValues[n-1]||0, |
| distinct_out_relations_mean:mean(orValues),distinct_out_relations_median:median(orValues), |
| distinct_out_relations_p90:quantile(orValues,.9),distinct_out_relations_p95:quantile(orValues,.95), |
| distinct_out_relations_p99:quantile(orValues,.99),distinct_out_relations_max:orValues[n-1]||0, |
| nodes_out_degree_gt_10_fraction: n?out.filter(v=>v>10).length/n:0, |
| nodes_out_degree_gt_50_fraction:n?out.filter(v=>v>50).length/n:0, |
| nodes_out_degree_gt_100_fraction:n?out.filter(v=>v>100).length/n:0, |
| wcc_count:wcc.length,largest_wcc_nodes:largest,largest_wcc_fraction:n?largest/n:0, |
| median_wcc_nodes:median(wcc),singleton_wcc_count:wcc.filter(v=>v===1).length, |
| isolated_nodes:out.reduce((sum,v,i)=>sum+(v===0 && inc[i]===0?1:0),0), |
| out_degree_mean_legacy:mean(outRaw.filter((v,i)=>v>0||inRaw[i]>0)), |
| in_degree_mean_legacy:mean(inRaw.filter((v,i)=>outRaw[i]>0||v>0)), |
| graph_density:n>1?2*simpleEdges/(n*(n-1)):0 |
| }; |
| const nodes=names.map((name,i)=>({name,out_degree:out[i],in_degree:inc[i],out_degree_rows:outRaw[i],in_degree_rows:inRaw[i],unique_out_neighbors:outgoingNeighbors[i].size,distinct_out_relations:outgoingRels[i].size,distinct_incident_relations:incidentRels[i].size,total_degree_rows:outRaw[i]+inRaw[i]})); |
| const maxTop=options.maxTop||25; |
| const topNodes=[...nodes].sort((a,b)=>b.total_degree_rows-a.total_degree_rows || a.name.localeCompare(b.name)).slice(0,maxTop); |
| const diverseNodes=[...nodes].sort((a,b)=>b.distinct_incident_relations-a.distinct_incident_relations || a.name.localeCompare(b.name)).slice(0,maxTop); |
| const relations=relNames.map((name,i)=>({name,count:relFreq[i],unique_triples:relEdges[i].length})).sort((a,b)=>b.count-a.count||a.name.localeCompare(b.name)); |
| const optional={}; |
| if(options.clustering){ |
| |
| |
| |
| |
| const degree=neighbors.map((adj,i)=>adj.size-(adj.has(i)?1:0)); |
| const forward=Array.from({length:n},()=>new Set()); |
| for(let u=0;u<n;u++)for(const v of neighbors[u]){ |
| if(u===v)continue; |
| if(degree[u]<degree[v]||(degree[u]===degree[v]&&u<v))forward[u].add(v); |
| } |
| let estimate=0; |
| const budget=30000000; |
| for(let u=0;u<n&&estimate<=budget;u++)for(const v of forward[u]){ |
| estimate+=Math.min(forward[u].size,forward[v].size); |
| if(estimate>budget)break; |
| } |
| if(estimate>budget){ |
| optional.clustering=`Skipped. Estimated triangle-intersection work exceeds ${budget.toLocaleString('en-US')} checks. This optional calculation was skipped to avoid excessive browser resource use.`; |
| } else { |
| const triangles=new Float64Array(n); |
| for(let u=0;u<n;u++)for(const v of forward[u]){ |
| const small=forward[u].size<=forward[v].size?forward[u]:forward[v]; |
| const large=small===forward[u]?forward[v]:forward[u]; |
| for(const w of small)if(large.has(w)){triangles[u]++;triangles[v]++;triangles[w]++;} |
| } |
| let sum=0; |
| for(let u=0;u<n;u++)if(degree[u]>1)sum+=2*triangles[u]/(degree[u]*(degree[u]-1)); |
| s.clustering_coefficient=n?sum/n:0; |
| } |
| } |
| if(options.eigenvector){ |
| |
| const connected=[];for(let i=0;i<n;i++)if(outRaw[i]||inRaw[i])connected.push(i); |
| if(connected.length>10000||simpleEdges>80000)optional.eigenvector='Skipped. Eigenvector centrality is capped at 10,000 connected nodes / 80,000 undirected edges.'; |
| else if(connected.length){ |
| const nn=connected.length;let x=new Float64Array(n),last=new Float64Array(n); |
| for(const i of connected)x[i]=1/Math.sqrt(nn); |
| let converged=false; |
| for(let iter=0;iter<1000;iter++){ |
| let norm=0;for(const i of connected){let v=x[i];for(const j of neighbors[i])v+=x[j];last[i]=v;norm+=v*v;} |
| norm=Math.sqrt(norm)||1;let err=0;for(const i of connected){last[i]/=norm;err+=Math.abs(last[i]-x[i]);} |
| [x,last]=[last,x];if(err<nn*1e-6){converged=true;break;} |
| } |
| if(!converged)optional.eigenvector='Did not converge within 1,000 iterations (as in NetworkX, this result is not reported).'; |
| else optional.eigenvector_top=connected.map(i=>({name:names[i],value:x[i]})).sort((a,b)=>b.value-a.value).slice(0,20); |
| } |
| } |
| if(options.legacy){ |
| if(unique.size>20000||n>10000) optional.legacy='Skipped. Legacy per-relation cycle pruning and reachability are capped at 20,000 unique triples and 10,000 nodes.'; |
| else { |
| const lengths=[], kh=[]; |
| for(let r=0;r<m;r++){ |
| const edges=relEdges[r], vx=new Set();for(const [a,b] of edges){vx.add(a);vx.add(b);} |
| |
| const f=new Map(), rev=new Map();for(const v of vx){f.set(v,[]);rev.set(v,[]);} |
| for(const [a,b] of edges){f.get(a).push(b);rev.get(b).push(a);} |
| const seen=new Set(),order=[]; |
| for(const src of vx){if(seen.has(src))continue;seen.add(src);const stack=[[src,0]]; |
| while(stack.length){const top=stack[stack.length-1], ns=f.get(top[0]);if(top[1]<ns.length){const v=ns[top[1]++];if(!seen.has(v)){seen.add(v);stack.push([v,0]);}} |
| else{order.push(top[0]);stack.pop();}} |
| } |
| const scc=new Map();let sid=0; |
| for(let i=order.length-1;i>=0;i--){const src=order[i];if(scc.has(src))continue;const stack=[src];scc.set(src,sid); |
| while(stack.length){for(const t of rev.get(stack.pop()))if(!scc.has(t)){scc.set(t,sid);stack.push(t);}}sid++; |
| } |
| const graph=new Map(),indeg=new Map(),height=new Map();for(const v of vx){graph.set(v,[]);indeg.set(v,0);height.set(v,0);} |
| for(const [a,b] of edges)if(scc.get(a)!==scc.get(b)){graph.get(a).push(b);indeg.set(b,indeg.get(b)+1);} |
| const q=[...vx].filter(v=>indeg.get(v)===0);let best=0; |
| for(let k=0;k<q.length;k++){const u=q[k];for(const v of graph.get(u)){height.set(v,Math.max(height.get(v),height.get(u)+1));best=Math.max(best,height.get(v));indeg.set(v,indeg.get(v)-1);if(indeg.get(v)===0)q.push(v);}} |
| lengths.push(best); |
| if(vx.size>600){kh.push(null);continue;} |
| let count=0,oneWay=0;const reach=new Map(); |
| for(const src of vx){const visited=new Set([src]),queue=[src];for(let k=0;k<queue.length;k++)for(const t of f.get(queue[k]))if(!visited.has(t)){visited.add(t);queue.push(t);}visited.delete(src);reach.set(src,visited);} |
| for(const [a,reachA] of reach)for(const b of reachA){count++;if(!reach.get(b).has(a))oneWay++;} |
| kh.push(count?oneWay/count:0); |
| } |
| s.legacy_max_non_cyclic_path=lengths.length?Math.max(...lengths):0; |
| if(kh.every(v=>v!==null))s.legacy_krackhardt_mean=mean(kh); |
| else optional.legacy_krackhardt='Partial only: some relation graphs exceeded 600 vertices; no mean reported.'; |
| optional.legacy_path_per_relation=relNames.map((name,i)=>({relation:name,maximum: lengths[i],krackhardt:kh[i]})); |
| } |
| } |
| return {summary:s,optional,topNodes,diverseNodes,relations,nodes, |
| components:wcc.slice().reverse().slice(0,20), |
| distributions:{out_degree:frequencies(out),in_degree:frequencies(inc),distinct_out_relations:frequencies(orValues),unique_out_neighbors:frequencies(onValues)}, |
| parse:{bad_rows:bad},sourceNote:'Measures from complete parsed input, not a sample.', |
| }; |
| } |
| return {add,addNode,output,get rows(){return rows;},get nodes(){return names.length;}}; |
| } |
| const api={createAccumulator,quantile}; |
| if(typeof module==='object'&&module.exports)module.exports=api; |
| if(scope)scope.KGCore=api; |
| })(typeof self!=='undefined'?self:null); |
|
|
