/**
 * Graph Theory Functions
 *
 * Provides fundamental graph algorithms operating on adjacency matrices:
 * - adjacencyMatrix: create adjacency matrix from edge list
 * - shortestPath: Dijkstra's algorithm for shortest path
 * - minimumSpanningTree: Prim's algorithm for MST
 * - connectedComponents: BFS-based component detection
 * - stronglyConnectedComponents: Tarjan's algorithm for directed graphs
 * - topologicalSort: Kahn's algorithm for DAGs
 * - isConnected: check if graph is connected
 * - graphDistance: shortest path length between two nodes
 * - pageRank: PageRank centrality with optional random-restart fan-out (Slice 5.13)
 * - betweennessCentrality: Brandes betweenness centrality with optional restarts
 * - eigenvectorCentrality: power-iteration eigenvector centrality with optional restarts
 *
 * Input format: adjacency matrix as number[][] where adj[i][j] > 0
 * means an edge from i to j with that weight.
 *
 * Worker-dispatch strategy (Slice 5.13) — centrality random-restart fan-out:
 * - When `restarts >= CENTRALITY_WORKER_THRESHOLD` (4), the N independent
 *   restart computations are fanned out via `Promise.all`.  Each restart uses a
 *   different random-initialisation seed derived from the caller-supplied
 *   `restartSeed` via SplitMix64-style hashing:
 *     `seed_k = (baseSeed ^ (k * 0x9E3779B97F4A7C15)) >>> 0`
 * - Graph serialisation: the adjacency matrix is plain `number[][]` and is
 *   passed directly.  Option B (main-thread fan-out) is used because registering
 *   a new worker handler would require modifying packages/workerpool/src/worker.ts
 *   which is outside this slice's scope.
 *
 * @packageDocumentation
 */
/**
 * Create an adjacency matrix from an edge list.
 *
 * @param edges - Array of [from, to] or [from, to, weight] tuples
 * @param n - Number of nodes in the graph
 * @param directed - Whether the graph is directed (default false)
 * @returns n x n adjacency matrix
 *
 * @example
 * adjacencyMatrix([[0, 1], [1, 2]], 3)
 * // => [[0, 1, 0], [1, 0, 1], [0, 1, 0]] (undirected)
 */
export declare function adjacencyMatrix(edges: number[][], n: number, directed?: boolean): number[][];
/**
 * Find the shortest path between two nodes using Dijkstra's algorithm.
 *
 * Returns the sequence of node indices from start to end.
 * Returns an empty array if no path exists.
 *
 * Time complexity: O(V^2) with simple linear scan.
 *
 * @param adj - Adjacency matrix (weights must be non-negative)
 * @param start - Source node index
 * @param end - Destination node index
 * @returns Array of node indices forming the shortest path
 *
 * @example
 * const adj = [[0,1,0],[1,0,1],[0,1,0]];
 * shortestPath(adj, 0, 2) // => [0, 1, 2]
 */
export declare function shortestPath(adj: number[][], start: number, end: number): number[];
/**
 * Find the minimum spanning tree using Prim's algorithm.
 *
 * Returns edges of the MST as [from, to, weight] tuples.
 * The graph must be connected for a valid MST.
 *
 * Time complexity: O(V^2)
 *
 * @param adj - Adjacency matrix (undirected, symmetric)
 * @returns Array of MST edges as [from, to, weight]
 *
 * @example
 * const adj = [[0,2,0],[2,0,1],[0,1,0]];
 * minimumSpanningTree(adj) // => [[0, 1, 2], [1, 2, 1]]
 */
export declare function minimumSpanningTree(adj: number[][]): number[][];
/**
 * Find all connected components in an undirected graph.
 *
 * Returns an array of component arrays, where each component is an
 * array of node indices belonging to that component.
 *
 * @param adj - Adjacency matrix (undirected)
 * @returns Array of connected components
 *
 * @example
 * const adj = [[0,1,0],[1,0,0],[0,0,0]];
 * connectedComponents(adj) // => [[0, 1], [2]]
 */
export declare function connectedComponents(adj: number[][]): number[][];
/**
 * Find strongly connected components in a directed graph using Tarjan's algorithm.
 *
 * Returns an array of SCC arrays, each containing node indices.
 *
 * @param adj - Adjacency matrix (directed)
 * @returns Array of strongly connected components
 *
 * @example
 * const adj = [[0,1,0],[0,0,1],[1,0,0]];
 * stronglyConnectedComponents(adj) // => [[2, 1, 0]]
 */
export declare function stronglyConnectedComponents(adj: number[][]): number[][];
/**
 * Topological sort of a directed acyclic graph using Kahn's algorithm.
 *
 * Returns an array of node indices in topological order.
 * Throws if the graph contains a cycle.
 *
 * @param adj - Adjacency matrix (directed, acyclic)
 * @returns Topologically sorted node indices
 *
 * @example
 * const adj = [[0,1,0],[0,0,1],[0,0,0]];
 * topologicalSort(adj) // => [0, 1, 2]
 */
export declare function topologicalSort(adj: number[][]): number[];
/**
 * Check if an undirected graph is connected.
 *
 * A graph is connected if there is a path between every pair of vertices.
 *
 * @param adj - Adjacency matrix (undirected)
 * @returns true if the graph is connected
 *
 * @example
 * isConnected([[0,1],[1,0]]) // => true
 * isConnected([[0,0],[0,0]]) // => false
 */
export declare function isConnected(adj: number[][]): boolean;
/**
 * Compute the shortest path length (distance) between two nodes.
 *
 * Uses Dijkstra's algorithm internally.
 * Returns Infinity if no path exists.
 *
 * @param adj - Adjacency matrix
 * @param start - Source node index
 * @param end - Destination node index
 * @returns Shortest path distance (sum of edge weights)
 *
 * @example
 * const adj = [[0,3,0],[3,0,2],[0,2,0]];
 * graphDistance(adj, 0, 2) // => 5
 */
export declare function graphDistance(adj: number[][], start: number, end: number): number;
/**
 * Minimum restart count before fanning out via Promise.all rather than running
 * sequentially.  Below this threshold restarts run one after another on the
 * current microtask, avoiding Promise scheduling overhead for the common
 * single-restart case.
 */
export declare const CENTRALITY_WORKER_THRESHOLD = 4;
/**
 * Shared options for centrality functions that support random-restart
 * fan-out (Slice 5.13).
 */
export interface CentralityRestartOptions {
    /**
     * Number of independent restarts to run (default 1 — no fan-out).
     * When `restarts >= CENTRALITY_WORKER_THRESHOLD` (4) the restarts are
     * dispatched as a `Promise.all` fan-out.
     */
    restarts?: number;
    /**
     * Base seed for reproducible restart initialisation.  Each restart k
     * receives a derived seed:
     *   `seed_k = ((baseSeed ^ (k * 0x9E3779B97F4A7C15)) >>> 0)`
     * Default: 0 (non-reproducible — uses `Math.random()`).
     */
    restartSeed?: number;
    /**
     * How to aggregate multi-restart results.
     * - `'mean'` (default): return the element-wise average rank vector.
     * - `'all'`: return all N rank vectors plus their mean and std.
     */
    aggregation?: 'mean' | 'all';
}
/** Options for pageRank. */
export interface PageRankOptions {
    /**
     * Damping factor d (probability of following an edge rather than teleporting).
     * Brin & Page recommend 0.85.  Default: 0.85.
     */
    dampingFactor?: number;
    /**
     * Maximum number of power-iteration steps.  Default: 100.
     */
    maxIter?: number;
    /**
     * Convergence tolerance.  Iteration stops when the L1 norm of the rank
     * delta is below this value.  Default: 1e-6.
     */
    tol?: number;
}
/** Result when `restarts` is omitted or 1. */
export interface PageRankResult {
    /** Normalised rank vector (sums to 1). */
    ranks: Float64Array;
}
/** Result when `restarts > 1` and `aggregation === 'all'`. */
export interface PageRankRestartResult {
    /** Element-wise average of all restart rank vectors. */
    ranks: Float64Array;
    /** All N rank vectors, one per restart (only when `aggregation='all'`). */
    ranksPerRestart?: Float64Array[];
    /** Per-element mean and std across restarts (only when `aggregation='all'`). */
    restartStats?: {
        mean: Float64Array;
        std: Float64Array;
    };
}
/**
 * Compute PageRank centrality for each node in a directed graph.
 *
 * **Single-restart path** (`restarts` omitted or 1): runs one power-iteration
 * sequence from a uniform initialisation and returns `{ ranks }` synchronously
 * (wrapped in a resolved Promise for a uniform async API).
 *
 * **Multi-restart path** (`restarts >= CENTRALITY_WORKER_THRESHOLD` = 4):
 * fans out N independent restarts via `Promise.all`, each initialised from a
 * different seed derived by SplitMix64-style hashing of `restartSeed × k`.
 * Results are averaged element-wise (or returned individually when
 * `aggregation: 'all'`).
 *
 * **Option B note:** all restarts execute on the main thread because adding a
 * new `centralityRestartChunk` worker handler would require modifying
 * `packages/workerpool/src/worker.ts`, which is outside this slice's scope.
 * The Promise.all fan-out still keeps the event loop responsive for consumers
 * that `await` the result.
 *
 * @param adj  - Directed adjacency matrix
 * @param opts - PageRank + restart options
 *
 * @example
 * const adj = [[0,1,0],[0,0,1],[1,0,0]];
 * const { ranks } = await pageRank(adj);
 * // ranks ≈ [0.333, 0.333, 0.333] (symmetric ring)
 *
 * @example
 * // 8 restarts, averaged
 * const result = await pageRank(adj, { restarts: 8, restartSeed: 42 });
 */
export declare function pageRank(adj: number[][], opts?: PageRankOptions & CentralityRestartOptions): Promise<PageRankResult | PageRankRestartResult>;
/** Options for betweennessCentrality. */
export interface BetweennessOptions {
    /**
     * Whether the graph is directed.  Default: false (undirected).
     */
    directed?: boolean;
    /**
     * Normalise by `(n-1)(n-2)` (matches `networkx.betweenness_centrality`'s
     * default `endpoints=False` scaling — the same divisor for directed AND
     * undirected graphs, since the raw Brandes accumulation below already
     * naturally double-counts each undirected unordered pair {s,t} by running
     * a source BFS from both s and t).  Default: true.
     */
    normalise?: boolean;
    /**
     * American-spelling alias for `normalise` (matches `networkx.betweenness_centrality`'s
     * `normalized` kwarg). When both are given, `normalized` takes precedence.
     * Default: true — same default/behavior as `normalise`, so existing callers
     * are unaffected.
     */
    normalized?: boolean;
}
/** Result returned by betweennessCentrality. */
export interface BetweennessResult {
    /** Betweenness centrality score for each node (length = n). */
    centrality: Float64Array;
}
/** Result when `restarts > 1` and `aggregation === 'all'`. */
export interface BetweennessRestartResult {
    centrality: Float64Array;
    centralityPerRestart?: Float64Array[];
    restartStats?: {
        mean: Float64Array;
        std: Float64Array;
    };
}
/**
 * Compute betweenness centrality for each node.
 *
 * Uses Brandes' BFS-based algorithm (exact for a single restart).  When
 * `restarts > 1` each restart samples n source nodes (with replacement) using
 * a distinct seed; the per-restart scores are averaged.
 *
 * Worker-dispatch strategy: Option B — all restarts run on the main thread
 * via `Promise.all`.
 *
 * @param adj  - Adjacency matrix
 * @param opts - Betweenness + restart options
 *
 * @example
 * const adj = [[0,1,1],[1,0,1],[1,1,0]];
 * const { centrality } = await betweennessCentrality(adj);
 */
export declare function betweennessCentrality(adj: number[][], opts?: BetweennessOptions & CentralityRestartOptions): Promise<BetweennessResult | BetweennessRestartResult>;
/** Options for eigenvectorCentrality. */
export interface EigenvectorOptions {
    /**
     * Maximum number of power-iteration steps.  Default: 100.
     */
    maxIter?: number;
    /**
     * Convergence tolerance (L∞ norm of delta).  Default: 1e-6.
     */
    tol?: number;
}
/** Result from eigenvectorCentrality. */
export interface EigenvectorResult {
    /** Eigenvector centrality scores (length = n). */
    centrality: Float64Array;
}
/** Result when `restarts > 1` and `aggregation === 'all'`. */
export interface EigenvectorRestartResult {
    centrality: Float64Array;
    centralityPerRestart?: Float64Array[];
    restartStats?: {
        mean: Float64Array;
        std: Float64Array;
    };
}
/**
 * Compute eigenvector centrality using power iteration.
 *
 * Each node's score is proportional to the sum of its neighbours' scores,
 * converging to the principal eigenvector of the adjacency matrix.
 *
 * When `restarts > 1`, each restart is initialised from a distinct random
 * vector seeded reproducibly.  The per-restart eigenvectors are sign-aligned
 * and then averaged to produce a stable estimate.
 *
 * Worker-dispatch strategy: Option B — all restarts run on the main thread
 * via `Promise.all`.
 *
 * @param adj  - Adjacency matrix (undirected, non-negative weights)
 * @param opts - Eigenvector + restart options
 *
 * @example
 * const adj = [[0,1,1],[1,0,1],[1,1,0]];
 * const { centrality } = await eigenvectorCentrality(adj);
 * // all ≈ [0.577, 0.577, 0.577] (symmetric k3)
 */
export declare function eigenvectorCentrality(adj: number[][], opts?: EigenvectorOptions & CentralityRestartOptions): Promise<EigenvectorResult | EigenvectorRestartResult>;
//# sourceMappingURL=graph.d.ts.map