37773995795

Committed 08 Oct 2026 11:51AM UTC coverage: 92.684% (+0.03%) from 92.65%

Build # 37773995795

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1538 from graphty-org/fix/visual-review-incomplete-capture-flake

test(visual-review): pin that a held git call does not freeze the server

Coverage Stats

57092 of 63648 branches covered (89.7%)

Branch coverage included in aggregate %.

87329 of 92173 relevant lines covered (94.74%)

298887.48 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.46

/graphty-element/src/algorithms/StronglyConnectedComponentsAlgorithm.ts

import { INVALID_INDEX } from "@graphty/graph-format";

import type { ResultElementValues } from "../session/results";
import { caveat } from "../session/runs/caveatFacts";
import { Algorithm } from "./Algorithm";
import { type ScopeInputDeclaration, scopeNodeIds } from "./input/ScopedInput";
import {
    type AlgorithmOutput,
    type AlgorithmRunContext,
    communityFieldSpecs,
    DeclaredAlgorithm,
    declaredCaveats,
    forEachChunked,
} from "./results";
import { declarationArcOrder } from "./utils/graphUtils";

/**
 * Strongly connected components: the pieces a directed path can cross both ways.
 */
export class StronglyConnectedComponentsAlgorithm extends DeclaredAlgorithm {
    static namespace = "graphty";
    static type = "scc";
    /** Groups over the run's scope: the node list and the graph both come from the input. */
    static scopeInput: ScopeInputDeclaration = "subgraph";

    /**
     * Find the pieces of the graph that a directed path can cross both ways.
     *
     * The same community shape as the weak reading, run at the other strength: two nodes share a
     * group only when a directed path runs each way between them. The caveats say which strength
     * ran, because on a directed graph the two answers differ and the numbers do not say so.
     * @param context - What the element gave the run.
     * @returns The community result, or null when there are no nodes to group.
     */
    async compute(context: AlgorithmRunContext): Promise<AlgorithmOutput | null> {
        // The nodes of the run's input: its scope's, so a member with no edge in the scope stands alone.
        const nodeIds = scopeNodeIds(this.input("declared"));

        if (nodeIds.length === 0) {
            return null;
        }

        /* The declared orientation: strong connectivity is a directed notion. On an undirected graph
           every edge can be crossed both ways, so the strong pieces ARE the connected ones, and
           that is the question asked of it.

           Components are numbered in the order Tarjan's walk completes them, trying each node's
           neighbours in the order their edges were declared -- the numbering the element has
           always published, which is what a palette keyed on the group reads. No accelerator
           computes strong components, so this is the CPU port's decision. */
        const { snapshot, run } = this.accelerated("stronglyConnectedComponents", "directed");

        context.report({ phase: "Finding pieces", total: null });
        const { value, precision } = await run((dispatch, s) =>
            s.directed
                ? dispatch.stronglyConnectedComponents(s, { arcOrder: declarationArcOrder(s) })
                : dispatch.connectedComponents(s),
        );

        const nodes: ResultElementValues[] = [];
        await forEachChunked(context, "Grouping nodes", nodeIds, (nodeId) => {
            const index = snapshot.ids.indexOf(nodeId);
            nodes.push({ id: nodeId, values: { group: index === INVALID_INDEX ? 0 : value.labels[index] } });
        });

        return {
            shape: "community",
            fields: communityFieldSpecs(false),
            nodes,
            caveats: declaredCaveats({
                method: "strongly-connected-components",
                direction: snapshot.directed ? "directed" : "undirected",
                weight: null,
                precision,
                facts: [
                    caveat("components.strong"),
                    ...(snapshot.directed ? [] : [caveat("components.undirected-strong")]),
                ],
            }),
        };
    }
}

// Auto-register this algorithm when the module is imported
Algorithm.register(StronglyConnectedComponentsAlgorithm);

1	import { INVALID_INDEX } from "@graphty/graph-format";
2
3	import type { ResultElementValues } from "../session/results";
4	import { caveat } from "../session/runs/caveatFacts";
5	import { Algorithm } from "./Algorithm";
6	import { type ScopeInputDeclaration, scopeNodeIds } from "./input/ScopedInput";
7	import {
8	type AlgorithmOutput,
9	type AlgorithmRunContext,
10	communityFieldSpecs,
11	DeclaredAlgorithm,
12	declaredCaveats,
13	forEachChunked,
14	} from "./results";
15	import { declarationArcOrder } from "./utils/graphUtils";
16
17	/**
18	* Strongly connected components: the pieces a directed path can cross both ways.
19	*/
20	export class StronglyConnectedComponentsAlgorithm extends DeclaredAlgorithm {
21	static namespace = "graphty";	518 ✔
22	static type = "scc";	518 ✔
23	/** Groups over the run's scope: the node list and the graph both come from the input. */
24	static scopeInput: ScopeInputDeclaration = "subgraph";	518 ✔
25
26	/**
27	* Find the pieces of the graph that a directed path can cross both ways.
28	*
29	* The same community shape as the weak reading, run at the other strength: two nodes share a
30	* group only when a directed path runs each way between them. The caveats say which strength
31	* ran, because on a directed graph the two answers differ and the numbers do not say so.
32	* @param context - What the element gave the run.
33	* @returns The community result, or null when there are no nodes to group.
34	*/
35	async compute(context: AlgorithmRunContext): Promise<AlgorithmOutput \| null> {
36	// The nodes of the run's input: its scope's, so a member with no edge in the scope stands alone.
37	const nodeIds = scopeNodeIds(this.input("declared"));	25 ✔
38
39	if (nodeIds.length === 0) {	25 !
40	return null;	×
41	}
42
43	/* The declared orientation: strong connectivity is a directed notion. On an undirected graph
44	every edge can be crossed both ways, so the strong pieces ARE the connected ones, and
45	that is the question asked of it.
46
47	Components are numbered in the order Tarjan's walk completes them, trying each node's
48	neighbours in the order their edges were declared -- the numbering the element has
49	always published, which is what a palette keyed on the group reads. No accelerator
50	computes strong components, so this is the CPU port's decision. */
51	const { snapshot, run } = this.accelerated("stronglyConnectedComponents", "directed");	25 ✔
52
53	context.report({ phase: "Finding pieces", total: null });	25 ✔
54	const { value, precision } = await run((dispatch, s) =>	25 ✔
55	s.directed	25 ✔
56	? dispatch.stronglyConnectedComponents(s, { arcOrder: declarationArcOrder(s) })
57	: dispatch.connectedComponents(s),
58	);
59
60	const nodes: ResultElementValues[] = [];	25 ✔
61	await forEachChunked(context, "Grouping nodes", nodeIds, (nodeId) => {	25 ✔
62	const index = snapshot.ids.indexOf(nodeId);	140 ✔
63	nodes.push({ id: nodeId, values: { group: index === INVALID_INDEX ? 0 : value.labels[index] } });	140 !
64	});
65
66	return {	24 ✔
67	shape: "community",
68	fields: communityFieldSpecs(false),
69	nodes,
70	caveats: declaredCaveats({
71	method: "strongly-connected-components",
72	direction: snapshot.directed ? "directed" : "undirected",	24 ✔
73	weight: null,
74	precision,
75	facts: [
76	caveat("components.strong"),
77	...(snapshot.directed ? [] : [caveat("components.undirected-strong")]),	24 ✔
78	],
79	}),
80	};
81	}
82	}
83
84	// Auto-register this algorithm when the module is imported
85	Algorithm.register(StronglyConnectedComponentsAlgorithm);	518 ✔

graphty-org / graphty-monorepo / 37773995795

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous