@graphty/algorithms / index / AcceleratedAlgorithms
Interface: AcceleratedAlgorithms ​
Defined in: indexed/accelerator.ts:358
The async dispatcher: one method per accelerable indexed.* function. Each delegates to the accelerator when it has the method and runs the CPU port otherwise, wrapped in Promise.resolve so both paths are async and graphty-element's async run() adapters treat them alike.
The list GROWS with the A2 ports -- each port PR adds its method (plan departure DEP-8A-E).
louvain and kCoreDecomposition pass their port's options through unchanged; Louvain's resolution is wider than the HitsOptionsLike the accelerator side declares, and narrowing that member belongs to the pull request that lands a GPU Louvain.
katzCentrality and hits hand the accelerator only what it reads -- { alpha, beta, maxIterations, tolerance, weighted } and { maxIterations, tolerance, weighted } -- with weighted resolved to the port's default (false), since an accelerator may default it the other way, and give its result the port's scale: an accelerator may end its iterate on any positive scale (webgpu-graph-algorithms divides Katz by its L2 norm and HITS by its sum), so Katz is min-max rescaled to [0, 1] as the port rescales its own, and each HITS vector is rescaled to unit length, or to a largest entry of 1 under normalized: false, as the port does. Katz runs the CPU port under normalized: false (the raw sums cannot be recovered from a rescaled vector), with alpha 0, and when every node has the same in-degree (or in-weight): there every score is equal, and the port leaves an equal vector unscaled. It also runs the CPU port unless alpha times a bound on the spectral radius is below 1, where the series is certain to converge: past that an f32 accelerator can overflow to Infinity. The iteration counts of the two paths differ.
labelPropagation passes its options through the same way, except that a call with randomSeed set runs the CPU port: the partition depends on the seed, and a GPU kernel has none to honour. An accelerator's result carries no iterations or converged; call labelPropagation directly for those. webgpu-graph-algorithms runs synchronous passes (the rules of labelPropagationSynchronous), so its partition can differ from the CPU port's, which visits nodes in a seeded random order.
breadthFirstSearch with a target or an arcOrder runs the CPU port: a GPU BFS expands whole levels and has no early stop and no neighbour order, so it would give a different result.
pageRank and personalizedPageRank run the CPU port when initialRanks or convergenceNorm: "max" is set: the accelerator members take neither. The accelerator is handed { dampingFactor, maxIterations, tolerance, weighted } with weighted resolved to the port's default (false), since an accelerator may default it the other way. Its stopping rule may differ from the port's (webgpu-graph-algorithms stops at an L1 change below tolerance * n, as networkx does), so the two paths can stop at different iterations. personalizedPageRank also runs the CPU port when the personalization is all zero (the port then answers plain PageRank, as the legacy function does for no personal nodes) or when a node is dangling: the port spreads dangling mass as legacy does, d * dangling / n scaled by the personalization, and the accelerator spreads d * dangling by the personalization, as networkx does. The two agree when no node is dangling.
eigenvectorCentrality goes to the accelerator only for the question its kernel answers the same way: an undirected snapshot with no parallel edges and no bipartite component, unweighted, from the uniform start. The kernel iterates on A where the port iterates on A + I, and walks every parallel arc where the port counts a neighbour once; on a bipartite component the iteration on A oscillates forever. A directed snapshot always runs the port, since a periodic strongly connected component oscillates the same way and is not cheap to rule out. The accelerator is called with { maxIterations, tolerance, weighted: false } and its unit-length vector is rescaled to [0, 1] exactly as the port rescales its own unless normalized: false. A result with converged: false raises ConvergenceError, as the port does. The iteration counts of the two paths differ.
allPairsShortestPath is the reverse case: the accelerator member reads none of the port's options and has no negative-cycle flag, so the dispatcher calls it, without options, only when it answers the port's question -- no options that change the result, at most the port's default 5,792 nodes, and non-negative finite snapshot weights -- and runs the CPU port otherwise. That is routing decided from the inputs, not a fallback: an error the accelerator raises still propagates. Same question is not same bits: both read the snapshot's f32 arc weights, but a GPU member sums them in f32 and returns an f32 dist, where the port sums in f64. The two agree exactly while every path sum is an integer below 2^24, and otherwise may differ by f32 rounding.
bellmanFord goes to the accelerator unless the call carries a weights override that is not a Float32Array: an accelerator narrows the override to f32, so an f64 one -- the exact weights a legacy facade passes -- would be answered for different weights. Its result gets the same pathTo / pathEdges decoration as sssp.
The three path centralities route the same way. betweennessCentrality and edgeBetweennessCentrality go to the accelerator unless the snapshot is a multigraph (the port counts a pair's parallel edges as one path, the WebGPU kernel as several), endpoints is set, or an alive edge mask is given. The accelerator is always handed the sources the port would run -- the caller's, the port's k draw, or every node -- so it never substitutes a draw or a sampling default of its own. closenessCentrality goes only for the plain score -- no normalized, cutoff or weights override, and harmonic only on an exact run to an accelerator that declares harmonicCloseness -- and hands the accelerator an explicit weighted, because the WebGPU member otherwise defaults it from the snapshot where the port defaults it off. A sampled closeness (sources or k) goes too, handed the sources the port would run -- the caller's or the port's k draw -- but only on an undirected snapshot: the port measures each node's distance TO the sources, which the accelerator's searches from the sources give only when distance is symmetric.
labelPropagationSynchronous is the deterministic label propagation on both paths: the accelerator's labelPropagation member (webgpu-graph-algorithms, since issue #694, follows the same rules) or the synchronous port. Both rank labels by the same scramble, keep a label that ties for the lead and move up on the first pass, so they give the same labels, except on a run that cycles: the port stops when a pass repeats the labels of two passes before and reports converged: false, the accelerator runs to maxIterations and reports no converged. Use it where a result should not depend on whether a device answered; use labelPropagation for the seeded, asynchronous (FLPA) partition.
minimumSpanningTree goes to the accelerator unless the call carries a per-arc weights override, which the accelerator does not take: it spans the snapshot's own edge weights. Both paths return the forest of the total edge order (weight, then edge index), so the edge SET is the same; the order of edges and the summation order of totalWeight may differ (webgpu-graph-algorithms' Boruvka lists the edges round by round).
triangleCount goes to the accelerator whenever it has the member, and the result always carries the clustering coefficient and the transitivity: an accelerator that returns only the seam's { perNode, total } gets them computed here from the counts and the distinct degrees.
depthFirstSearch, degrees, stronglyConnectedComponents, leiden, girvanNewman, maxFlow, minSTCut, stoerWagner, kargerMinCut, commonNeighborsPrediction, adamicAdarPrediction, primMST and maximumBipartiteMatching always run the CPU port: AlgorithmAccelerator declares no member for them, since no GPU kernel exists. They are here so graphty-element runs every algorithm through one object, and each gains an accelerator branch when a kernel lands. depthFirstSearch takes any AdjacencyView, as its port does, so a walk can run over a reverse or an edited view. A port's throw becomes a rejection.
Properties ​
accelerator ​
readonlyaccelerator:AlgorithmAccelerator|null
Defined in: indexed/accelerator.ts:359
Methods ​
adamicAdarPrediction() ​
adamicAdarPrediction(
s,options?):Promise<LinkPredictionResult>
Defined in: indexed/accelerator.ts:397
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<LinkPredictionResult>
allPairsShortestPath() ​
allPairsShortestPath(
s,options?):Promise<ApspCycleResultLike>
Defined in: indexed/accelerator.ts:383
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<ApspCycleResultLike>
bellmanFord() ​
bellmanFord(
s,source,options?):Promise<BellmanFordResult>
Defined in: indexed/accelerator.ts:368
Parameters ​
s ​
GraphSnapshot
source ​
NodeRef
options? ​
Returns ​
Promise<BellmanFordResult>
betweennessCentrality() ​
betweennessCentrality(
s,options?):Promise<ScoresResultLike>
Defined in: indexed/accelerator.ts:384
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<ScoresResultLike>
breadthFirstSearch() ​
breadthFirstSearch(
s,source,options?):Promise<BfsResultLike>
Defined in: indexed/accelerator.ts:369
Parameters ​
s ​
GraphSnapshot
source ​
NodeRef
options? ​
Returns ​
Promise<BfsResultLike>
closenessCentrality() ​
closenessCentrality(
s,options?):Promise<ClosenessResultLike>
Defined in: indexed/accelerator.ts:386
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<ClosenessResultLike>
commonNeighborsPrediction() ​
commonNeighborsPrediction(
s,options?):Promise<LinkPredictionResult>
Defined in: indexed/accelerator.ts:396
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<LinkPredictionResult>
connectedComponents() ​
connectedComponents(
s):Promise<LabelResultLike>
Defined in: indexed/accelerator.ts:370
Parameters ​
s ​
GraphSnapshot
Returns ​
Promise<LabelResultLike>
degrees() ​
degrees(
s):Promise<DegreesResult>
Defined in: indexed/accelerator.ts:388
Parameters ​
s ​
GraphSnapshot
Returns ​
Promise<DegreesResult>
depthFirstSearch() ​
depthFirstSearch(
g,start,options?):Promise<DfsResult>
Defined in: indexed/accelerator.ts:387
Parameters ​
g ​
AdjacencyView
start ​
NodeRef
options? ​
Returns ​
Promise<DfsResult>
edgeBetweennessCentrality() ​
edgeBetweennessCentrality(
s,options?):Promise<EdgeScoresResultLike>
Defined in: indexed/accelerator.ts:385
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<EdgeScoresResultLike>
eigenvectorCentrality() ​
eigenvectorCentrality(
s,options?):Promise<ScoresResultLike>
Defined in: indexed/accelerator.ts:366
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<ScoresResultLike>
girvanNewman() ​
girvanNewman(
s,options?):Promise<GirvanNewmanResult>
Defined in: indexed/accelerator.ts:391
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<GirvanNewmanResult>
hits() ​
hits(
s,options?):Promise<HitsResultLike>
Defined in: indexed/accelerator.ts:375
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<HitsResultLike>
kargerMinCut() ​
kargerMinCut(
s,options?):Promise<MinCutResult>
Defined in: indexed/accelerator.ts:395
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<MinCutResult>
katzCentrality() ​
katzCentrality(
s,options?):Promise<ScoresResultLike>
Defined in: indexed/accelerator.ts:374
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<ScoresResultLike>
kCoreDecomposition() ​
kCoreDecomposition(
s):Promise<CorenessResultLike>
Defined in: indexed/accelerator.ts:373
Parameters ​
s ​
GraphSnapshot
Returns ​
Promise<CorenessResultLike>
labelPropagation() ​
labelPropagation(
s,options?):Promise<LabelResultLike>
Defined in: indexed/accelerator.ts:377
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<LabelResultLike>
labelPropagationSynchronous() ​
labelPropagationSynchronous(
s,options?):Promise<LabelResultLike>
Defined in: indexed/accelerator.ts:378
Parameters ​
s ​
GraphSnapshot
options? ​
SynchronousLabelPropagationOptions
Returns ​
Promise<LabelResultLike>
leiden() ​
leiden(
s,options?):Promise<LeidenResult>
Defined in: indexed/accelerator.ts:390
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<LeidenResult>
louvain() ​
louvain(
s,options?):Promise<CommunityResultLike>
Defined in: indexed/accelerator.ts:376
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<CommunityResultLike>
maxFlow() ​
maxFlow(
s,source,sink,options?):Promise<MaxFlowResult>
Defined in: indexed/accelerator.ts:392
Parameters ​
s ​
GraphSnapshot
source ​
NodeRef
sink ​
NodeRef
options? ​
Returns ​
Promise<MaxFlowResult>
maximumBipartiteMatching() ​
maximumBipartiteMatching(
s,options?):Promise<BipartiteMatchingResult>
Defined in: indexed/accelerator.ts:399
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<BipartiteMatchingResult>
minimumSpanningTree() ​
minimumSpanningTree(
s,options?):Promise<MstResultLike>
Defined in: indexed/accelerator.ts:372
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<MstResultLike>
minSTCut() ​
minSTCut(
s,source,sink,options?):Promise<MinCutResult>
Defined in: indexed/accelerator.ts:393
Parameters ​
s ​
GraphSnapshot
source ​
NodeRef
sink ​
NodeRef
options? ​
Returns ​
Promise<MinCutResult>
pageRank() ​
pageRank(
s,options?):Promise<PageRankResultLike>
Defined in: indexed/accelerator.ts:360
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<PageRankResultLike>
personalizedPageRank() ​
personalizedPageRank(
s,personalization,options?):Promise<PageRankResultLike>
Defined in: indexed/accelerator.ts:361
Parameters ​
s ​
GraphSnapshot
personalization ​
F64 | F32
options? ​
Returns ​
Promise<PageRankResultLike>
primMST() ​
primMST(
s,options?):Promise<PrimResult>
Defined in: indexed/accelerator.ts:398
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<PrimResult>
sssp() ​
sssp(
s,source,options?):Promise<SsspResult>
Defined in: indexed/accelerator.ts:367
Parameters ​
s ​
GraphSnapshot
source ​
NodeRef
options? ​
Returns ​
Promise<SsspResult>
stoerWagner() ​
stoerWagner(
s,options?):Promise<MinCutResult>
Defined in: indexed/accelerator.ts:394
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<MinCutResult>
stronglyConnectedComponents() ​
stronglyConnectedComponents(
s,options?):Promise<LabelResult>
Defined in: indexed/accelerator.ts:389
Parameters ​
s ​
GraphSnapshot
options? ​
Returns ​
Promise<LabelResult>
triangleCount() ​
triangleCount(
s):Promise<TriangleCountResult>
Defined in: indexed/accelerator.ts:382
Parameters ​
s ​
GraphSnapshot
Returns ​
Promise<TriangleCountResult>
weaklyConnectedComponents() ​
weaklyConnectedComponents(
s):Promise<LabelResultLike>
Defined in: indexed/accelerator.ts:371
Parameters ​
s ​
GraphSnapshot
Returns ​
Promise<LabelResultLike>