/** * Add noise paths to make ground truth detection harder. * * Creates random paths that act as decoys, making it more challenging * to identify the true high-MI paths. * * @template N - Node type * @template E - Edge type * @param graph - Graph with planted paths * @param groundTruth - Ground truth paths to avoid * @param numNoisePaths - Number of decoy paths to add * @param numberNoisePaths * @param seed - Random seed * @returns Graph with added noise paths */ export declare const addNoisePaths: (graph: Graph, groundTruth: Path[], numberNoisePaths: number, seed?: number) => Graph; /** * Aggregate representativeness results across multiple seed pairs. * * @param results - Array of individual representativeness results * @returns Averaged metrics */ export declare const aggregateRepresentativenessResults: (results: StructuralRepresentativenessResult[]) => StructuralRepresentativenessResult; /** Algebraic connectivity (λ₂): second smallest Laplacian eigenvalue (Fiedler value) */ export declare type AlgebraicConnectivity = { kind: "algebraic_connectivity"; value: number; } | { kind: "unconstrained"; }; export declare const allEqual: (xs: readonly T[], eq: (a: T, b: T) => boolean) => boolean; /** * Type guard for graphs allowing self-loops * @param spec */ export declare const allowsSelfLoops: (spec: GraphSpec_2) => spec is GraphSpec_2 & { selfLoops: { kind: "allowed"; }; }; /** * Altered communities state for tracking changed communities between iterations. * @remarks * Used by altered communities heuristic to reduce redundant computation. * Only nodes in altered communities (and their neighbors) need to be revisited. */ export declare interface AlteredCommunitiesState { /** * Set of community IDs that had nodes move in or out during the last iteration. * @remarks * - Initialized with all community IDs before first iteration (visit all nodes) * - Cleared at the start of each iteration * - Populated during node moves (add both source and target community IDs) * - Used to filter which nodes need to be checked for movement */ alteredCommunities: Set; } /** * Analyze a graph spec for mathematically impossible combinations. * @param spec */ export declare const analyzeGraphSpecConstraints: (spec: GraphSpec_2) => GraphSpecImpossibility[]; export declare type AnalyzerEdge = { id: string; endpoints: readonly AnalyzerVertexId[]; directed: boolean; weight?: number; sign?: -1 | 1; probability?: number; label?: string; attrs?: Record; }; export declare type AnalyzerGraph = { vertices: AnalyzerVertex[]; edges: AnalyzerEdge[]; }; export declare type AnalyzerGraphPredicate = (g: AnalyzerGraph) => boolean; export declare type AnalyzerVertex = { id: AnalyzerVertexId; label?: string; attrs?: Record; }; /** * Analyzer Types and Helpers * * Shared types, compute policy, and helper functions for graph analysis. */ export declare type AnalyzerVertexId = string; /** * Wayback Machine utilities for archiving and retrieving URLs. * * Provides functions to submit URLs to the Internet Archive's Wayback Machine, * check for existing archives, and retrieve historical snapshots. */ export declare interface ArchivedUrl { original: string; archived: string; } /** Arc-transitive property (both vertex AND edge transitive - symmetric graphs) */ export declare type ArcTransitive = { kind: "arc_transitive"; } | { kind: "not_arc_transitive"; } | { kind: "unconstrained"; }; /** * No asteroidal triple of vertices */ declare type ATFree = { kind: "at_free"; } | { kind: "has_asteroidal_triple"; } | { kind: "unconstrained"; }; /** * Create a predicate that checks if an axis equals a specific value. * Example: axisEquals("directionality", { kind: "undirected" }) * @param key * @param expected * @param policy */ export declare const axisEquals: (key: K, expected: InferredGraphSpec[K], policy?: Partial) => AnalyzerGraphPredicate; /** * Create a predicate that checks if an axis has a specific kind. * Example: axisKindIs("cycles", "acyclic") * @param key * @param kind * @param policy */ export declare const axisKindIs: (key: K, kind: KK, policy?: Partial) => AnalyzerGraphPredicate; /** * All available benchmark datasets. */ export declare const BENCHMARK_DATASETS: BenchmarkDatasetMeta[]; /** * Metadata for a benchmark dataset. */ export declare interface BenchmarkDatasetMeta { /** Human-readable name */ name: string; /** Short identifier for tables/logs */ id: string; /** Brief description */ description: string; /** Whether edges are directed */ directed: boolean; /** Expected node count (for validation) */ expectedNodes: number; /** Expected edge count (for validation) */ expectedEdges: number; /** Expected content size in bytes (for validation, helps detect remote changes) */ expectedContentSize: number; /** File path relative to data/benchmarks/ */ relativePath: string; /** Delimiter for parsing (regex or string) */ delimiter: string | RegExp; /** Source/citation for the dataset */ source: string; /** * Remote URL for downloading the dataset. * Used for browser environments or when local files aren't available. * Should point to a raw text file in edge list format. */ remoteUrl?: string; /** * Representative node pairs for testing. * These are actual node IDs from the graph that can be used in path ranking tests. * Tests should use these rather than assuming generic IDs like "0", "1", etc. */ testPairs?: TestNodePair[]; } /** * Benjamini-Hochberg FDR correction. * * Controls false discovery rate (FDR) rather than FWER. Less conservative * than Bonferroni, making it more powerful for large numbers of tests. * * Procedure: * 1. Sort p-values in ascending order * 2. Find largest k such that p_k ≤ (k/m) * FDR * 3. Reject all hypotheses 1, 2, ..., k * * @param pValues - Array of p-values from multiple tests * @param fdr - Target false discovery rate (default: 0.05) * @returns Adjusted p-values and which tests are significant * * @example * ```typescript * const pValues = [0.001, 0.02, 0.045, 0.08, 0.12]; * const result = benjaminiHochberg(pValues, 0.05); * console.log(result.adjustedPValues); // [0.005, 0.05, 0.075, 0.1, 0.12] * console.log(result.significant); // [true, true, false, false, false] * ``` */ export declare const benjaminiHochberg: (pValues: number[], fdr?: number) => { adjustedPValues: number[]; significant: boolean[]; }; /** * Options for between-graph enumeration. */ export declare interface BetweenGraphOptions { /** Maximum path length to enumerate (default: 6) */ maxPathLength?: number; /** Maximum number of paths to enumerate (default: 10000) */ maxPaths?: number; /** Whether to treat graph as directed (default: false) */ directed?: boolean; } /** * Result of between-graph enumeration. */ export declare interface BetweenGraphResult { /** All nodes on any path between seeds */ nodes: Set; /** All edges on any path between seeds */ edges: Set; /** All discovered paths (as node ID arrays) */ paths: string[][]; /** Node degrees within the between-graph */ degrees: Map; /** Statistics about the enumeration */ stats: { /** Total paths found */ pathCount: number; /** Maximum path length found */ maxPathLength: number; /** Minimum path length found */ minPathLength: number; /** Mean path length */ meanPathLength: number; }; } /** * Breadth-First Search traversal. * @param graph * @param startId */ export declare const bfs: (graph: ReadableGraph, startId: string) => Result_2, InvalidInputError_2>; /** * Statistics collected during BFS expansion. */ export declare interface BfsExpansionStats { /** Total nodes expanded (popped from frontiers) */ nodesExpanded: number; /** Total edges traversed */ edgesTraversed: number; /** Iterations (single node expansions) performed */ iterations: number; /** Breakdown of nodes by degree ranges */ degreeDistribution: Map; /** Fraction of total expansion complete when first hub is expanded (0-1). -1 if no hubs. */ firstHubEncounterFraction: number; /** Mean fraction of expansion complete across all hub encounters */ meanHubEncounterFraction: number; } /** * Options for bibliographic coupling detection. */ export declare interface BibliographicCouplingOptions { /** Minimum shared references */ minShared: number; } /** * Bibliographic coupling pair (papers citing same references). * Two papers sharing references in their bibliographies. */ export declare interface BibliographicCouplingPair { /** First coupled paper */ paper1: N; /** Second coupled paper */ paper2: N; /** Number of shared references */ sharedReferences: number; } /** * Biconnected component. * Maximal subgraph with no articulation points (remains connected after removing any single node). */ export declare interface BiconnectedComponent { /** Component identifier */ id: ComponentId; /** Nodes in this biconnected component */ nodes: Set; /** Number of nodes */ size: number; /** Articulation points connecting this component to others */ articulationPoints: Set; /** True if component consists of a single bridge edge */ isBridge: boolean; } /** * Find biconnected components using Tarjan's algorithm. * * A biconnected component is a maximal subgraph where removing any single node * still leaves the graph connected. Articulation points (cut vertices) are nodes * whose removal increases the number of connected components. * * Use Case: Identify critical papers (articulation points) that connect research communities * in citation networks. Removing these papers would fragment the network. * * Algorithm Steps: * 1. DFS traversal with discovery time tracking * 2. Calculate low-link values (earliest ancestor reachable via back edges) * 3. Detect articulation points: low[child] ≥ disc[v] * 4. Extract components by popping edge stack on backtrack * 5. Handle disconnected graphs (DFS from each unvisited node) * @template N - Node type * @template E - Edge type * @param graph - Undirected graph to analyze * @returns Result containing biconnected components and articulation points, or error * @example * ```typescript * const graph = new Graph(false); // undirected * // ... add nodes and edges ... * * const result = biconnectedComponents(graph); * if (result.ok) { * console.log(`Found ${result.value.articulationPoints.size} articulation points`); * console.log(`Found ${result.value.components.length} biconnected components`); * * result.value.components.forEach(component => { * console.log(`Component ${component.id}: ${component.size} nodes`); * if (component.isBridge) { * console.log(' -> Bridge component'); * } * }); * } * ``` */ export declare const biconnectedComponents: (graph: Graph) => BiconnectedResult; /** * Result type for Biconnected Component Decomposition. */ export declare type BiconnectedResult = Result<{ components: BiconnectedComponent[]; articulationPoints: Set; metadata: { algorithm: "biconnected"; runtime: number; }; }, DecompositionError>; /** * Generic bidirectional breadth-first search with degree-based node prioritization. * * **NOTE: This is an earlier design with parameterised termination.** * For the parameter-free version that aligns with the thesis theoretical framework, * see DegreePrioritisedExpansion (N≥1 seeds, frontier exhaustion only). * * **Design Relationship**: * - BidirectionalBFS: Earlier design, N=2 only, has termination parameters (targetPaths, maxIterations) * - DegreePrioritisedExpansion: Refined design, N≥1 with identical code path, parameter-free * * This implementation is suitable for production use cases where: * - Predictable resource consumption is required * - Finding *a* path quickly is more important than exhaustive sampling * - Service-level objectives constrain iteration count * * Searches for paths between two seed nodes by expanding frontiers from both directions. * Uses priority queue to process low-degree nodes first, naturally prioritizing specific * connections over generic ones. * * **Algorithm**: Degree-based best-first search * - Maintains two frontiers (from seedA and seedB) * - Processes nodes in order of degree (low degree = high priority) * - Detects when frontiers meet to find paths * - Continues for minimum iterations after finding target paths (for diversity) * * **Time Complexity**: O(E log V) where E = edges explored, V = vertices * **Space Complexity**: O(V) for visited sets and frontiers * * @template T - Type of node data returned by expander * @example * ```typescript * const bfs = new BidirectionalBFS( * expander, * 'nodeA', * 'nodeB', * { targetPaths: 5, maxIterations: 10, minIterations: 2 } * ); * * const result = await bfs.search(); * console.log(`Found ${result.paths.length} paths in ${result.iterations} iterations`); * ``` * * @see DegreePrioritisedExpansion - Parameter-free version for N≥1 seeds */ export declare class BidirectionalBFS { private readonly expander; private readonly seedA; private readonly seedB; private readonly options; private foundPaths; private stateA; private stateB; constructor(expander: GraphExpander, seedA: string, seedB: string, options: BidirectionalBFSOptions); /** * Execute the bidirectional BFS search. * * @returns Search results including found paths and visited nodes */ search(): Promise; /* Excluded from this release type: expandFrontier */ /* Excluded from this release type: checkForConnections */ /* Excluded from this release type: reconstructPath */ /* Excluded from this release type: pathExists */ /* Excluded from this release type: addPathNodesToFrontiers */ } /** * Configuration options for bidirectional BFS. */ export declare interface BidirectionalBFSOptions { /** Target number of paths to find */ targetPaths: number; /** Maximum BFS iterations before stopping */ maxIterations: number; /** Minimum iterations to continue after finding target paths (for path diversity) */ minIterations?: number; } /** * Result from bidirectional BFS search. */ export declare interface BidirectionalBFSResult { /** Array of paths (each path is array of node IDs from seedA to seedB) */ paths: string[][]; /** Nodes visited from seedA */ visitedA: Set; /** Nodes visited from seedB */ visitedB: Set; /** Number of iterations performed */ iterations: number; } /** Binary tree property */ export declare type BinaryTree = { kind: "binary_tree"; } | { kind: "full_binary"; } | { kind: "complete_binary"; } | { kind: "not_binary_tree"; } | { kind: "unconstrained"; }; /** * Bonferroni correction for multiple comparisons. * * Controls family-wise error rate (FWER) by dividing alpha by the * number of tests. Very conservative but simple. * * @param pValues - Array of p-values from multiple tests * @param alpha - Original significance level (default: 0.05) * @returns Corrected alpha threshold and which tests are significant * * @example * ```typescript * const pValues = [0.001, 0.02, 0.045, 0.08, 0.12]; * const result = bonferroniCorrection(pValues, 0.05); * console.log(result.correctedAlpha); // 0.01 (0.05 / 5 tests) * console.log(result.significant); // [true, false, false, false, false] * ``` */ export declare const bonferroniCorrection: (pValues: number[], alpha?: number) => { correctedAlpha: number; significant: boolean[]; }; /** * Bootstrap confidence interval for a metric. * * Uses resampling with replacement to estimate the sampling distribution * of a statistic and calculate confidence intervals. * * @param samples - Observed metric values * @param confidence - Confidence level (default: 0.95 for 95% CI) * @param nBootstrap - Number of bootstrap samples (default: 10000) * @param seed - Random seed for reproducibility (optional) * @returns Lower and upper bounds of CI and mean estimate * * @example * ```typescript * const scores = [0.82, 0.85, 0.78, 0.90, 0.87, 0.83, 0.86, 0.89, 0.84, 0.88]; * const ci = bootstrapCI(scores, 0.95, 10000, 42); * console.log(ci.lower); // e.g., 0.82 * console.log(ci.upper); // e.g., 0.88 * console.log(ci.mean); // e.g., 0.85 * ``` */ export declare const bootstrapCI: (samples: number[], confidence?: number, nBootstrap?: number, seed?: number) => { lower: number; upper: number; mean: number; }; /** * Bootstrap test for significant difference between methods. * * Tests whether the difference between two methods is statistically * significant by bootstrapping the distribution of differences. * * @param method1Samples - Samples from method 1 * @param method2Samples - Samples from method 2 * @param nBootstrap - Number of bootstrap samples (default: 10000) * @param alpha - Significance level (default: 0.05) * @param seed - Random seed for reproducibility (optional) * @returns p-value, mean difference, and confidence interval for difference * * @example * ```typescript * const miScores = [0.85, 0.82, 0.88, 0.90, 0.87]; * const baselineScores = [0.65, 0.70, 0.68, 0.72, 0.69]; * const result = bootstrapDifferenceTest(miScores, baselineScores, 10000, 0.05, 42); * console.log(result.pValue); // e.g., 0.002 (significant) * console.log(result.meanDifference); // e.g., 0.17 * console.log(result.ci.lower); // e.g., 0.12 * console.log(result.ci.upper); // e.g., 0.22 * ``` */ export declare const bootstrapDifferenceTest: (method1Samples: number[], method2Samples: number[], nBootstrap?: number, alpha?: number, seed?: number) => { pValue: number; meanDifference: number; ci: { lower: number; upper: number; }; significant: boolean; }; /** Branchwidth property */ export declare type Branchwidth = { kind: "branchwidth"; width: number; } | { kind: "unconstrained"; }; export declare const buildAdjUndirectedBinary: (g: AnalyzerGraph) => Record; /** * Contains no induced bull graph */ declare type BullFree = { kind: "bull_free"; } | { kind: "has_bull"; } | { kind: "unconstrained"; }; /** * Contains no induced cycle on 5 vertices */ declare type C5Free = { kind: "c5_free"; } | { kind: "has_c5"; } | { kind: "unconstrained"; }; /** Cage graph: (girth, degree) combination with minimal vertices */ export declare type Cage = { kind: "cage"; girth: number; degree: number; } | { kind: "not_cage"; } | { kind: "unconstrained"; }; /** * Calculate average conductance across multiple clusters. * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param clusters - Array of node sets representing clusters * @returns Average conductance score * @example * ```typescript * const clusters = [ * new Set(['A', 'B', 'C']), * new Set(['D', 'E', 'F']), * new Set(['G', 'H', 'I']) * ]; * const avgConductance = calculateAverageConductance(graph, clusters); * ``` */ export declare const calculateAverageConductance: (graph: Graph, clusters: Set[]) => number; /** * Calculate average density across multiple clusters. * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param clusters - Array of node sets representing clusters * @returns Average density score * @example * ```typescript * const clusters = [ * new Set(['A', 'B', 'C']), * new Set(['D', 'E', 'F']) * ]; * const avgDensity = calculateAverageDensity(graph, clusters); * ``` */ export declare const calculateAverageDensity: (graph: Graph, clusters: Set[]) => number; /** * Calculate aggregated quality metrics for a clustering result. * * Computes modularity, average conductance, average density, coverage ratio, * and cluster count for a complete clustering. * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param communities - Array of communities * @returns Aggregated ClusterMetrics * @example * ```typescript * const graph = new Graph(false); * const communities: Community[] = [...]; * const metrics = calculateClusterMetrics(graph, communities); * * console.log(`Modularity: ${metrics.modularity.toFixed(3)}`); * console.log(`Avg Conductance: ${metrics.avgConductance.toFixed(3)}`); * console.log(`Avg Density: ${metrics.avgDensity.toFixed(3)}`); * console.log(`Coverage: ${(metrics.coverageRatio * 100).toFixed(1)}%`); * console.log(`Clusters: ${metrics.numClusters}`); * ``` */ export declare const calculateClusterMetrics: (graph: Graph, communities: Community[]) => ClusterMetrics; /** * Calculate modularity contribution for a single community. * * Used for incremental modularity updates during optimization. * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param community - Community to evaluate * @param totalEdges - Total number of edges in graph * @returns Modularity contribution of this community * @example * ```typescript * const m = graph.getEdgeCount(); * const contribution = calculateCommunityModularity(graph, community, m); * ``` */ export declare const calculateCommunityModularity: (graph: Graph, community: Community, totalEdges: number) => number; /** * Calculate conductance for a cluster/community. * * Conductance formula: * φ(S) = |cut(S)| / min(vol(S), vol(V\S)) * * Where: * - cut(S) = number of edges crossing the boundary of S * - vol(S) = sum of degrees of nodes in S * - V\S = complement of S (nodes not in S) * * Range: [0.0, 1.0] * - Lower values indicate better cluster quality (fewer boundary edges) * - φ < 0.1 typically indicates strong cluster cohesion * - φ > 0.5 indicates weak cluster structure * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param clusterNodes - Set of nodes in the cluster * @returns Conductance score in range [0.0, 1.0] * @example * ```typescript * const graph = new Graph(false); * // ... build graph ... * const cluster = new Set(['A', 'B', 'C']); * const conductance = calculateConductance(graph, cluster); * console.log(`Conductance: ${conductance.toFixed(3)}`); // e.g., "Conductance: 0.125" * ``` */ export declare const calculateConductance: (graph: Graph, clusterNodes: Set) => number; /** * Calculate coverage ratio: fraction of edges within clusters vs. total edges. * * coverage = (edges within clusters) / (total edges in graph) * * Range: [0.0, 1.0] * - Higher coverage means most edges are within communities * - Lower coverage means many inter-community edges * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param clusters - Array of node sets representing clusters * @returns Coverage ratio * @example * ```typescript * const coverage = calculateCoverageRatio(graph, clusters); * console.log(`${(coverage * 100).toFixed(1)}% of edges are within clusters`); * ``` */ export declare const calculateCoverageRatio: (graph: Graph, clusters: Set[]) => number; /** * Calculate density for a cluster/community. * * Density formula: * density = actual_edges / possible_edges * * For undirected graphs: * - possible_edges = n * (n - 1) / 2 * * For directed graphs: * - possible_edges = n * (n - 1) * * Where n is the number of nodes in the cluster. * * Range: [0.0, 1.0] * - 1.0 = complete graph (all possible edges present) * - 0.0 = no internal edges * - Higher density indicates tighter community structure * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param clusterNodes - Set of nodes in the cluster * @returns Density score in range [0.0, 1.0] * @example * ```typescript * const graph = new Graph(false); * // ... build graph ... * const cluster = new Set(['A', 'B', 'C']); * const density = calculateDensity(graph, cluster); * console.log(`Density: ${density.toFixed(3)}`); // e.g., "Density: 0.667" * ``` */ export declare const calculateDensity: (graph: Graph, clusterNodes: Set) => number; /** * Calculate modularity (Q) for a graph partitioned into communities. * * Newman-Girvan formula: * Q = 1/(2m) * Σ[A_ij - (k_i * k_j)/(2m)] * δ(c_i, c_j) * * Where: * - m = total number of edges * - A_ij = 1 if edge exists between i and j, 0 otherwise * - k_i = degree of node i * - k_j = degree of node j * - δ(c_i, c_j) = 1 if nodes i and j are in the same community, 0 otherwise * * Range: [-0.5, 1.0] * - Higher values indicate stronger community structure * - Q > 0.3 typically indicates significant community structure * - Q < 0 indicates worse than random partitioning * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param communities - Community assignments * @returns Modularity score in range [-0.5, 1.0] * @example * ```typescript * const graph = new Graph(false); * // ... build graph ... * const communities: Community[] = [...]; * const Q = calculateModularity(graph, communities); * console.log(`Modularity: ${Q.toFixed(3)}`); // e.g., "Modularity: 0.427" * ``` */ export declare const calculateModularity: (graph: Graph, communities: Community[]) => number; /** * Calculate modularity delta for moving a node between communities. * * Used by Louvain and Leiden algorithms for greedy optimization. * * ΔQ = [Σin + k_i_in] / (2m) - [(Σtot + k_i)² / (2m)²] - [Σin / (2m) - (Σtot / (2m))² - (k_i / (2m))²] * @param k_i - Degree of node being moved * @param k_index * @param k_i_in - Sum of edge weights from node to nodes in target community * @param k_index_in * @param sigma_tot - Sum of degrees of nodes in target community * @param sigma_in - Sum of edge weights between nodes in target community * @param m - Total number of edges in graph * @returns Change in modularity (positive means improvement) * @example * ```typescript * const deltaQ = calculateModularityDelta(5, 3, 20, 15, 100); * if (deltaQ > 0) { * // Moving node improves modularity * } * ``` */ export declare const calculateModularityDelta: (k_index: number, k_index_in: number, sigma_tot: number, sigma_in: number, m: number) => number; /** * Calculate weighted average conductance (weighted by cluster size). * * Larger clusters have more influence on the average. * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param clusters - Array of node sets representing clusters * @returns Weighted average conductance score * @example * ```typescript * const clusters = [ * new Set(['A', 'B', 'C']), // size 3 * new Set(['D', 'E']), // size 2 * new Set(['F', 'G', 'H', 'I']) // size 4 * ]; * const weightedAvg = calculateWeightedAverageConductance(graph, clusters); * ``` */ export declare const calculateWeightedAverageConductance: (graph: Graph, clusters: Set[]) => number; /** Cartesian product G □ H */ export declare type CartesianProduct = { kind: "cartesian_product"; leftFactors: number; rightFactors: number; } | { kind: "not_cartesian_product"; } | { kind: "unconstrained"; }; /** * Check if a URL has been archived and get the latest snapshot. * * Uses the Wayback Availability API to find the closest available snapshot. * * @param url * @param options * @example * ```ts * const result = await checkArchived("https://example.com"); * if (result) { * console.log("Already archived:", result.archived); * } * ``` */ export declare const checkArchived: (url: string, options?: WaybackOptions) => Promise; /** Chordal graph property (no induced cycles > 3) */ export declare type Chordal = { kind: "chordal"; } | { kind: "non_chordal"; } | { kind: "unconstrained"; }; /** Chromatic number property (minimum colors needed) */ export declare type ChromaticNumber = { kind: "chromatic_number"; chi: number; } | { kind: "unconstrained"; }; /** * intersection Graph Class Type Definitions * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.825Z */ /** * Intersection graph of arcs on a circle */ declare type CircularArc = { kind: "circular_arc"; } | { kind: "not_circular_arc"; } | { kind: "unconstrained"; }; /** Length of longest cycle */ export declare type Circumference = { kind: "circumference"; value: number; } | { kind: "unconstrained"; }; /** * Type definitions for the normalized graph JSON format. * * This format is used as the canonical interchange format for graphbox. */ /** * Structured citation for academic references. */ export declare interface Citation { /** List of author names */ authors: string[]; /** Title of the work */ title: string; /** Publication year */ year: number; /** Journal name (for articles) */ journal?: string; /** Volume number */ volume?: number; /** Issue number */ issue?: number; /** Page range (e.g., "452-473") */ pages?: string; /** Publisher name (for books) */ publisher?: string; /** Publication location (for books) */ location?: string; /** DOI identifier */ doi?: string; /** Type of publication */ type?: "article" | "book" | "conference" | "thesis" | "other"; } /** * Configuration for citation path planting. */ export declare interface CitationPathConfig extends PlantedPathConfig { /** Type of citation path to plant */ pathType: CitationPathType; } /** * Citation path types based on real scholarly communication patterns. */ export declare type CitationPathType = "direct-citation-chain" | "co-citation-bridge" | "bibliographic-coupling" | "author-mediated" | "venue-mediated"; /** * CiteSeer citation network. * * A citation network of computer science papers. * Nodes are papers, edges are citations. */ export declare const CITESEER: BenchmarkDatasetMeta; /** Claw-free property (no K1,3 induced subgraph) */ export declare type ClawFree = { kind: "claw_free"; } | { kind: "has_claw"; } | { kind: "unconstrained"; }; /** * Cliff's delta (non-parametric effect size). * * Measures dominance between two groups without assuming normal distribution. * Based on probability that a randomly selected value from group1 exceeds * a randomly selected value from group2. * * Interpretation: * - |δ| < 0.147: Negligible * - 0.147 ≤ |δ| < 0.33: Small * - 0.33 ≤ |δ| < 0.474: Medium * - |δ| ≥ 0.474: Large * * @param group1 - Samples from group 1 * @param group2 - Samples from group 2 * @returns Effect size and interpretation * * @example * ```typescript * const treatment = [8, 9, 7, 8, 10]; * const control = [5, 6, 5, 6, 7]; * const result = cliffsDelta(treatment, control); * console.log(result.effectSize); // e.g., 0.92 (large effect) * console.log(result.interpretation); // 'large' * console.log(result.probability); // e.g., 0.96 (96% chance treatment > control) * ``` */ export declare const cliffsDelta: (group1: number[], group2: number[]) => { effectSize: number; interpretation: "negligible" | "small" | "medium" | "large"; probability: number; magnitude: number; }; /** * Cliquewidth at most k */ declare type Cliquewidth = { kind: "cliquewidth_bounded"; } | { kind: "cliquewidth_unbounded"; } | { kind: "unconstrained"; }; /** * Cluster identifier for label propagation */ export declare type ClusterId = number; /** * Error type for clustering/partitioning/decomposition algorithms. */ export declare type ClusteringError = { type: "EmptyGraph"; message: string; } | { type: "InvalidInput"; message: string; } | { type: "InsufficientNodes"; message: string; required: number; actual: number; } | { type: "ConvergenceFailure"; message: string; iterations: number; } | { type: "InvalidParameter"; message: string; parameter: string; value: unknown; }; /** * Aggregated quality metrics for clustering results. * Used by Louvain, Leiden, Label Propagation algorithms. */ export declare interface ClusterMetrics { /** Global modularity score (Newman-Girvan), range: [-0.5, 1.0] */ modularity: number; /** Average conductance across communities, range: [0.0, 1.0] */ avgConductance: number; /** Average internal density across communities, range: [0.0, 1.0] */ avgDensity: number; /** Total number of clusters/communities */ numClusters: number; /** Silhouette score if applicable, range: [-1.0, 1.0] */ silhouetteCoefficient?: number; /** Fraction of edges within clusters vs. total edges, range: [0.0, 1.0] */ coverageRatio: number; } /** * Options for co-citation detection. */ export declare interface CoCitationOptions { /** Minimum co-citation count */ minCount: number; } /** * Co-citation pair (papers cited together). * Two papers frequently cited by the same citing papers. */ export declare interface CoCitationPair { /** First co-cited paper */ paper1: N; /** Second co-cited paper */ paper2: N; /** Number of papers citing both */ count: number; } /** Cograph property (P4-free, can be constructed via union/complement) */ export declare type Cograph = { kind: "cograph"; } | { kind: "non_cograph"; } | { kind: "unconstrained"; }; /** * Cohen's d effect size. * * Standardized mean difference measures the magnitude of difference * between two groups in units of standard deviation. * * Interpretation (Cohen's conventions): * - |d| < 0.2: Small effect * - 0.2 ≤ |d| < 0.5: Medium effect * - 0.5 ≤ |d| < 0.8: Large effect * - |d| ≥ 0.8: Very large effect * * @param group1 - Samples from group 1 * @param group2 - Samples from group 2 * @returns Effect size and interpretation category * * @example * ```typescript * const treatment = [8, 9, 7, 8, 10]; * const control = [5, 6, 5, 6, 7]; * const result = cohensD(treatment, control); * console.log(result.effectSize); // e.g., 1.8 (very large effect) * console.log(result.interpretation); // 'very-large' * ``` */ export declare const cohensD: (group1: number[], group2: number[]) => { effectSize: number; interpretation: "negligible" | "small" | "medium" | "large" | "very-large"; magnitude: number; }; /** * Community structure detected by Louvain algorithm. * Represents a densely connected subgraph with high modularity. */ export declare interface Community { /** Community identifier (0-indexed) */ id: CommunityId; /** Set of nodes belonging to this community */ nodes: Set; /** Number of edges within the community */ internalEdges: number; /** Number of edges crossing community boundary */ externalEdges: number; /** Contribution to global modularity score */ modularity: number; /** Internal edge density (actual_edges / possible_edges) */ density: number; /** Number of nodes in community */ size: number; } /** * Community edge weight cache for Louvain optimization. * @remarks * Hash table caching edge weights between pairs of communities. * Reduces redundant calculations during modularity evaluations. * * **Cache Key Format**: `"${fromCommunityId}-${toCommunityId}"` * **Cache Value**: Total weight of edges from community `fromCommunityId` to `toCommunityId` * * **Lifecycle**: * - Initialized as empty Map at the start of each local moving phase * - Invalidated when a node moves (delete entries involving affected communities) * * **Note**: Cache population logic was removed in final optimization phase due to * complexity and lack of measured performance benefit for citation networks. */ export declare type CommunityHashTable = Map; /** * Community/Cluster identifier */ export declare type CommunityId = number; /** Modular/community structure property */ export declare type CommunityStructure = { kind: "modular"; numCommunities?: number; intraCommunityDensity?: number; interCommunityDensity?: number; } | { kind: "non_modular"; } | { kind: "unconstrained"; }; /** Comparability graph property (represents partial order) */ export declare type Comparability = { kind: "comparability"; } | { kind: "incomparability"; } | { kind: "unconstrained"; }; /** * Compute comprehensive degree distribution comparison metrics. * * @param sampledDegrees - Degree values from sampled subgraph * @param groundTruthDegrees - Degree values from ground truth graph * @returns Complete comparison metrics */ export declare const compareDegreeDistributions: (sampledDegrees: number[], groundTruthDegrees: number[]) => DegreeDistributionMetrics; /** Complete bipartite property K_{m,n} */ export declare type CompleteBipartite = { kind: "complete_bipartite"; m: number; n: number; } | { kind: "not_complete_bipartite"; } | { kind: "unconstrained"; }; /** Graph completeness property */ export declare type Completeness = { kind: "complete"; } | { kind: "incomplete"; }; /** * Connected component of nodes. * Represents a maximal set of mutually reachable nodes. * @template N - Node type * id - Component identifier (0-indexed) * nodes - Nodes in this component * size - Number of nodes in component * @invariant size === nodes.length * @example * ```typescript * const result = connectedComponents(graph); * if (result.ok) { * console.log(`Found ${result.value.length} components`); * result.value.forEach(comp => { * console.log(`Component ${comp.id}: ${comp.size} nodes`); * }); * } * ``` */ export declare interface Component { /** Component identifier (0-indexed) */ id: number; /** Nodes in this component */ nodes: N[]; /** Number of nodes in component */ size: number; } /** * Biconnected component identifier */ export declare type ComponentId = number; /** * Compression ratio for Infomap * initial_length / final_length, > 1.0 indicates compression */ export declare type CompressionRatio = number; /** * Convenience function to compute all ground truth types for a set of paths * * @param graph - Graph containing the paths * @param paths - Paths to rank * @param customImportance - Optional custom importance for domain-specific * @returns Object with rankings for each ground truth type */ export declare const computeAllGroundTruths: (graph: Graph, paths: Path[], customImportance?: (nodeId: string) => number) => Record[]>; /** * Compute ATFree property from graph structure. * No asteroidal triple of vertices * @param g * @param _policy */ declare const computeATFree: (g: AnalyzerGraph, _policy: ComputePolicy) => ATFree; /** * Auto-detect k-regular property (find k if graph is regular). * @param g */ declare const computeAutoRegular: (g: AnalyzerGraph) => { kind: "k_regular"; k: number; } | { kind: "not_k_regular"; } | { kind: "unconstrained"; }; /** * Compute BullFree property from graph structure. * Contains no induced bull graph * @param g * @param _policy */ declare const computeBullFree: (g: AnalyzerGraph, _policy: ComputePolicy) => BullFree; /** * Compute C5Free property from graph structure. * Contains no induced cycle on 5 vertices * @param g * @param _policy */ declare const computeC5Free: (g: AnalyzerGraph, _policy: ComputePolicy) => C5Free; /** * Compute CircularArc property from graph structure. * Intersection graph of arcs on a circle * @param g * @param _policy */ declare const computeCircularArc: (g: AnalyzerGraph, _policy: ComputePolicy) => CircularArc; /** * Compute claw-free property (no K1,3 induced subgraph). * @param g */ declare const computeClawFree: (g: AnalyzerGraph) => { kind: "claw_free"; } | { kind: "has_claw"; } | { kind: "unconstrained"; }; /** * Compute cograph property (P4-free graph). * @param g */ declare const computeCograph: (g: AnalyzerGraph) => { kind: "cograph"; } | { kind: "non_cograph"; } | { kind: "unconstrained"; }; /** * Compute community coverage. * * @param sampledNodes - Nodes discovered by expansion * @param communities - Array of community node sets * @returns Fraction of communities with at least one sampled node */ export declare const computeCommunityCoverage: (sampledNodes: Set, communities: Array>) => number; /** * Compute modular/community structure property. * Uses modularity maximization as heuristic. * @param g * @param policy */ declare const computeCommunityStructure: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "modular"; numCommunities: number; } | { kind: "non_modular"; } | { kind: "unconstrained"; }; /** * Compute complete bipartite property K_{m,n}. * @param g */ declare const computeCompleteBipartite: (g: AnalyzerGraph) => { kind: "complete_bipartite"; m: number; n: number; } | { kind: "not_complete_bipartite"; } | { kind: "unconstrained"; }; declare const computeCompleteness: (g: AnalyzerGraph) => { kind: "incomplete"; } | { kind: "complete"; }; declare const computeConnectivity: (g: AnalyzerGraph) => { kind: "unconstrained"; } | { kind: "connected"; }; /** * Compute cubic graph property (3-regular). * @param g */ declare const computeCubic: (g: AnalyzerGraph) => { kind: "cubic"; } | { kind: "non_cubic"; } | { kind: "unconstrained"; }; declare const computeCycles: (g: AnalyzerGraph) => { kind: "cycles_allowed"; } | { kind: "acyclic"; }; declare const computeDegreeConstraint: (g: AnalyzerGraph) => { kind: "unconstrained"; } | { kind: "regular"; degree: number; } | { kind: "degree_sequence"; sequence: readonly number[]; }; /** * Compute degree distribution as a normalized histogram. * * @param degrees - Array of degree values * @returns Map from degree to probability (sum = 1) */ export declare const computeDegreeDistribution: (degrees: number[]) => Map; /** * Compute degree histogram bucket counts (for visualization). * * @param degrees - Array of degree values * @returns Map from bucket label to count */ export declare const computeDegreeHistogram: (degrees: number[]) => Map; declare const computeDensity: (g: AnalyzerGraph) => { kind: "unconstrained"; } | { kind: "sparse"; } | { kind: "dense"; }; declare const computeDirectionality: (g: AnalyzerGraph) => { kind: "undirected"; } | { kind: "directed"; } | { kind: "mixed"; } | { kind: "bidirected"; } | { kind: "antidirected"; }; /** * Compute DistanceHereditary property from graph structure. * Distances preserved in all connected induced subgraphs * @param g * @param _policy */ declare const computeDistanceHereditary: (g: AnalyzerGraph, _policy: ComputePolicy) => DistanceHereditary; declare const computeEdgeArity: (g: AnalyzerGraph) => { kind: "binary"; } | { kind: "k_ary"; k: number; }; declare const computeEdgeData: (g: AnalyzerGraph) => { kind: "unlabelled"; } | { kind: "labelled"; } | { kind: "attributed"; }; /** * Compute mutual information for a single edge. * * This is a convenience function for computing MI for individual edges * without pre-computing the entire graph. For ranking multiple paths, * use `precomputeMutualInformation` instead for better performance. * * Note: This function only supports attribute-based and structural MI. * For full modifier support (temporal, signed, probabilistic, etc.), * use `precomputeMutualInformation` which applies all modifiers. * * @template N - Node type * @template E - Edge type * @param graph - The graph containing the edge * @param edge - The edge to compute MI for * @param config - Optional configuration * @returns MI value for the edge */ export declare const computeEdgeMI: (graph: Graph, edge: E, config?: MutualInformationConfig) => number; declare const computeEdgeMultiplicity: (g: AnalyzerGraph) => { kind: "simple"; } | { kind: "multi"; }; declare const computeEdgeOrdering: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "unordered"; } | { kind: "ordered"; }; /** * Compute k-hop ego network from a single seed node. * * This is the ground truth for N=1 seed case. * * @param graph - The graph to search * @param seed - Seed node ID * @param k - Maximum hops from seed (default: 3) * @returns Ego network result */ export declare const computeEgoNetwork: (graph: Graph, seed: string, k?: number) => BetweenGraphResult; declare const computeEmbedding: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "abstract"; } | { kind: "geometric_metric_space"; } | { kind: "spatial_coordinates"; dims: 2 | 3; }; /** * Compute GemFree property from graph structure. * Contains no induced gem graph * @param g * @param _policy */ declare const computeGemFree: (g: AnalyzerGraph, _policy: ComputePolicy) => GemFree; export declare const computeGraphSpecFromGraph: (g: AnalyzerGraph, policy?: Partial) => InferredGraphSpec; /** * Compute importance-based ground truth ranking for paths * * @param graph - Graph containing the paths * @param paths - Paths to rank * @param config - Ground truth configuration * @returns Paths sorted by ground truth score (descending) */ export declare const computeGroundTruth: (graph: Graph, paths: Path[], config: GroundTruthConfig) => GroundTruthPath[]; /** * Compute Hamiltonian property using exhaustive search with pruning. * NP-complete, so this is expensive for larger graphs. * @param g */ declare const computeHamiltonian: (g: AnalyzerGraph) => { kind: "hamiltonian"; } | { kind: "non_hamiltonian"; } | { kind: "unconstrained"; }; /** * Compute HHFree property from graph structure. * No induced house or hole (cycle of length >= 5) * @param g * @param _policy */ declare const computeHHFree: (g: AnalyzerGraph, _policy: ComputePolicy) => HHFree; /** * Compute hub coverage: fraction of paths traversing high-degree nodes. * * @param paths - Array of paths, where each path is an array of node IDs * @param hubNodes - Set of node IDs considered "hubs" (high-degree nodes) * @returns Fraction of paths that traverse at least one hub */ export declare const computeHubCoverage: (paths: string[][], hubNodes: Set) => number; declare const computeLayering: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "single_layer"; } | { kind: "multi_layer"; } | { kind: "multiplex"; } | { kind: "interdependent"; }; /** * Compute line graph property. * @param g */ declare const computeLine: (g: AnalyzerGraph) => { kind: "line_graph"; } | { kind: "non_line_graph"; } | { kind: "unconstrained"; }; declare const computeMeasureSemantics: (g: AnalyzerGraph) => { kind: "none"; } | { kind: "metric"; } | { kind: "cost"; } | { kind: "utility"; }; /** * Compute Modular property from graph structure. * Every module is trivial (no twin vertices with identical neighborhoods) * * A modular graph has no non-trivial modules. Two vertices form a module if they * have identical external neighborhoods. * * For small graphs (n <= 10): Exhaustive pairwise comparison * For large graphs: Heuristic twin-finding (may return unconstrained for complex cases) * * @param g - Analyzer graph * @param _policy - Computation policy (unused) * @returns Modular property: "modular", "not_modular", or "unconstrained" */ declare const computeModular: (g: AnalyzerGraph, _policy?: ComputePolicy) => Modular; declare const computeObservability: (g: AnalyzerGraph) => { kind: "fully_specified"; } | { kind: "partially_observed"; } | { kind: "latent_or_inferred"; }; declare const computeOperationalSemantics: (g: AnalyzerGraph) => { kind: "structural_only"; } | { kind: "annotated_with_functions"; } | { kind: "executable"; }; /** * Compute P5Free property from graph structure. * Contains no induced path on 5 vertices * @param g * @param _policy */ declare const computeP5Free: (g: AnalyzerGraph, _policy: ComputePolicy) => P5Free; declare const computePartiteness: (g: AnalyzerGraph) => { kind: "unrestricted"; } | { kind: "bipartite"; }; /** * Compute comprehensive path diversity metrics. * * @param paths - Array of paths, where each path is an array of node IDs * @returns Complete diversity metrics */ export declare const computePathDiversityMetrics: (paths: string[][]) => PathDiversityMetrics; /** * Compute perfect graph property. * Perfect graphs have no odd holes or odd anti-holes. * @param g */ declare const computePerfect: (g: AnalyzerGraph) => { kind: "perfect"; } | { kind: "imperfect"; } | { kind: "unconstrained"; }; /** * Compute Planar property from graph structure. * A graph is planar if it can be drawn in the plane without edge crossings. * * Uses Kuratowski's theorem: A graph is planar iff it contains no subdivision * of K5 or K3,3 (complete graph on 5 vertices or complete bipartite 3,3). * * Detection strategy: * 1. Trivial cases (n < 5): Always planar * 2. Edge count heuristic: If m > 3n - 6, then nonplanar (necessary condition) * 3. For small graphs (n <= 10): Check for K5 and K3,3 subgraphs * 4. For large graphs: Return unconstrained if heuristic passes * * @param g - Analyzer graph * @param _policy - Computation policy (unused) * @returns Planar property: "planar", "nonplanar", or "unconstrained" */ declare const computePlanar: (g: AnalyzerGraph, _policy?: ComputePolicy) => Planar; export declare type ComputePolicy = Readonly<{ vertexOrderKey: string; edgeOrderKey: string; posKey: string; layerKey: string; timeKey: string; rootKey: string; portKey: string; weightVectorKey: string; probabilityKey: string; }>; declare const computePorts: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "none"; } | { kind: "port_labelled_vertices"; }; /** * Compute ProbeChordal property. * @param g * @param _policy */ declare const computeProbeChordal: (g: AnalyzerGraph, _policy: ComputePolicy) => ProbeChordal; /** * Compute ProbeInterval property. * @param g * @param _policy */ declare const computeProbeInterval: (g: AnalyzerGraph, _policy: ComputePolicy) => ProbeInterval; /** * Compute ProperCircularArc property from graph structure. * Circular arc graph with no arc containment * @param g * @param _policy */ declare const computeProperCircularArc: (g: AnalyzerGraph, _policy: ComputePolicy) => ProperCircularArc; /** * Compute Ptolemaic property from graph structure. * Ptolemaic graphs are both distance-hereditary AND chordal. * * A graph is Ptolemaic if and only if it satisfies both: * 1. Distance-hereditary: No induced house, hole, domino, or gem * 2. Chordal: No induced cycle of length >= 4 * * Equivalently: Ptolemaic = chordal + distance-hereditary * * @param g - Analyzer graph * @param _policy - Computation policy (unused) * @returns Ptolemaic property: "ptolemaic" or "not_ptolemaic" */ declare const computePtolemaic: (g: AnalyzerGraph, _policy?: ComputePolicy) => Ptolemaic; /** * Compute QuasiLine property from graph structure. * Quasi-line graphs have no induced gem and no induced co-gem. * * A gem is a graph with 5 vertices: P4 (path of length 4) plus a universal vertex * connected to all vertices of the P4. The co-gem is the complement of the gem. * * Detection strategy: * 1. Check for induced gem * 2. Check for induced co-gem (gem in complement graph) * * @param g - Analyzer graph * @param _policy - Computation policy (unused) * @returns QuasiLine property: "quasi_line" or "not_quasi_line" */ declare const computeQuasiLine: (g: AnalyzerGraph, _policy?: ComputePolicy) => QuasiLine; declare const computeRooting: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "unrooted"; } | { kind: "rooted"; } | { kind: "multi_rooted"; }; /** * Compute scale-free property (power-law degree distribution). * Uses maximum likelihood estimation and Kolmogorov-Smirnov test. * @param g */ declare const computeScaleFree: (g: AnalyzerGraph) => { kind: "scale_free"; exponent: number; } | { kind: "not_scale_free"; }; declare const computeSchemaHomogeneity: (g: AnalyzerGraph) => { kind: "homogeneous"; } | { kind: "heterogeneous"; }; /** * Compute self-complementary property (graph isomorphic to its complement). * GI-complete, so this is expensive. * @param g */ declare const computeSelfComplementary: (g: AnalyzerGraph) => { kind: "self_complementary"; } | { kind: "not_self_complementary"; } | { kind: "unconstrained"; }; declare const computeSelfLoops: (g: AnalyzerGraph) => { kind: "disallowed"; } | { kind: "allowed"; }; /** * Compute set overlap metrics between sampled and ground truth node sets. * * @param sampledNodes - Nodes discovered by expansion method * @param groundTruthNodes - Nodes in ground truth between-graph * @returns Coverage, precision, and F1 score */ export declare const computeSetOverlap: (sampledNodes: Set, groundTruthNodes: Set) => { coverage: number; precision: number; f1Score: number; intersection: number; }; declare const computeSignedness: (g: AnalyzerGraph) => { kind: "unsigned"; } | { kind: "signed"; }; /** * Compute small-world property (high clustering + short paths). * @param g */ declare const computeSmallWorld: (g: AnalyzerGraph) => { kind: "small_world"; } | { kind: "not_small_world"; } | { kind: "unconstrained"; }; /** * Compute split graph property (partition into clique + independent set). * @param g */ declare const computeSplit: (g: AnalyzerGraph) => { kind: "split"; } | { kind: "non_split"; } | { kind: "unconstrained"; }; /** * Compute strongly regular graph property. * Strongly regular: (n, k, λ, μ) where every vertex has degree k, * adjacent vertices have λ common neighbors, non-adjacent have μ common neighbors. * @param g */ declare const computeStronglyRegular: (g: AnalyzerGraph) => { kind: "strongly_regular"; k: number; lambda: number; mu: number; } | { kind: "not_strongly_regular"; } | { kind: "unconstrained"; }; /** * Compute comprehensive structural representativeness metrics. * * @param sampledNodes - Nodes discovered by expansion method * @param groundTruthNodes - Nodes in ground truth between-graph * @param sampledDegrees - Degrees of sampled nodes * @param groundTruthDegrees - Degrees of ground truth nodes * @param communities - Optional community partition for coverage metric * @returns Complete representativeness metrics */ export declare const computeStructuralRepresentativeness: (sampledNodes: Set, groundTruthNodes: Set, sampledDegrees: Map, groundTruthDegrees: Map, communities?: Array>) => StructuralRepresentativenessResult; declare const computeTemporal: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "static"; } | { kind: "dynamic_structure"; } | { kind: "temporal_edges"; } | { kind: "temporal_vertices"; } | { kind: "time_ordered"; }; /** * Compute threshold graph property (split + cograph). * @param g */ declare const computeThreshold: (g: AnalyzerGraph) => { kind: "threshold"; } | { kind: "non_threshold"; } | { kind: "unconstrained"; }; /** * Compute traceable property (has Hamiltonian path). * @param g */ declare const computeTraceable: (g: AnalyzerGraph) => { kind: "traceable"; } | { kind: "non_traceable"; } | { kind: "unconstrained"; }; /** * Computes triangle support for all edges in the graph. * * Triangle support = number of triangles an edge participates in. * For undirected graph: edge (u,v) is in triangle with node w if edges (u,w) and (v,w) exist. * For directed graph: treat all edges as undirected for triangle counting. * * Algorithm: * 1. For each edge (u,v), find common neighbors of u and v * 2. Each common neighbor w forms a triangle (u,v,w) * 3. Count triangles = |neighbors(u) ∩ neighbors(v)| * @param graph - Input graph (directed or undirected) * @returns Result containing map of edge ID to triangle count * @example * ```typescript * const result = computeTriangleSupport(graph); * if (result.ok) { * const support = result.value; * console.log(`Edge e1 participates in ${support.get('e1')} triangles`); * } * ``` */ export declare const computeTriangleSupport: (graph: Graph) => Result, ExtractionError_2>; declare const computeUncertainty: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "deterministic"; } | { kind: "probabilistic"; min?: number; max?: number; }; declare const computeVertexCardinality: (g: AnalyzerGraph) => { kind: "finite"; n: number; }; declare const computeVertexData: (g: AnalyzerGraph) => { kind: "unlabelled"; } | { kind: "labelled"; } | { kind: "attributed"; }; declare const computeVertexIdentity: (g: AnalyzerGraph) => { kind: "distinguishable"; } | { kind: "indistinguishable"; }; declare const computeVertexOrdering: (g: AnalyzerGraph, policy: ComputePolicy) => { kind: "unordered"; } | { kind: "total_order"; } | { kind: "partial_order"; }; /** * Compute vertex-transitive property. * GI-hard, so this is conservative. * @param g */ declare const computeVertexTransitive: (g: AnalyzerGraph) => { kind: "vertex_transitive"; } | { kind: "not_vertex_transitive"; } | { kind: "unconstrained"; }; /** * Compute WeaklyChordal property from graph structure. * No hole or antihole of length >= 5 * * @param g - Analyzer graph * @param _g * @param _policy - Computation policy (unused in generated analyzers) * @returns WeaklyChordal with computed value */ declare const computeWeaklyChordal: (g: AnalyzerGraph, _policy: ComputePolicy) => WeaklyChordal; declare const computeWeighting: (g: AnalyzerGraph, _policy: ComputePolicy) => { kind: "unweighted"; } | { kind: "weighted_numeric"; min?: number; max?: number; }; /** * Conductance score * Range: [0.0, 1.0], lower is better (fewer boundary edges) */ export declare type Conductance = number; /** * Find all connected components in an undirected graph (or weakly connected components in directed graph). * * Uses DFS to traverse each component. For directed graphs, treats edges as undirected. * * Time Complexity: O(V + E) * Space Complexity: O(V) * @param graph - The graph to analyze * @returns Result containing array of components */ export declare const connectedComponents: (graph: Graph) => Result[], InvalidInputError>; /** Connectivity property */ export declare type Connectivity = { kind: "connected"; } | { kind: "unconstrained"; }; /** * Cora citation network. * * A citation network of machine learning papers. * Nodes are papers, edges are citations. */ export declare const CORA: BenchmarkDatasetMeta; /** * K-core decomposition result. * Maximal subgraph where all nodes have degree ≥ k within the subgraph. */ export declare interface Core { /** Core number (minimum degree within core) */ k: number; /** Nodes in the k-core */ nodes: Set; /** Number of nodes in core */ size: number; /** Maximum k value across all cores (graph degeneracy) */ degeneracy: number; /** Per-node core numbers (highest k-core each node belongs to) */ coreNumbers: Map; } /** * Coreness score for core-periphery decomposition * Range: [0.0, 1.0], core membership strength */ export declare type CorenessScore = number; /** * Perform core-periphery decomposition on a graph using Borgatti-Everett model. * * Identifies a dense core of highly connected nodes and a sparse periphery. * Core nodes have high coreness scores (> threshold) and are densely connected to each other. * Periphery nodes have low coreness scores and are sparsely connected. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param options - Optional parameters (threshold, iterations, epsilon) * @returns Result with core-periphery structure or error * @example * ```typescript * const result = corePeripheryDecomposition(citationGraph, { coreThreshold: 0.7 }); * if (result.ok) { * console.log(`Core: ${result.value.structure.coreNodes.size} nodes`); * console.log(`Periphery: ${result.value.structure.peripheryNodes.size} nodes`); * console.log(`Fit quality: ${result.value.structure.fitQuality}`); * } * ``` */ export declare const corePeripheryDecomposition: (graph: Graph, options?: CorePeripheryOptions) => CorePeripheryResult; /** * Options for core-periphery decomposition. */ export declare interface CorePeripheryOptions { /** Threshold for core membership (default: 0.7) */ coreThreshold?: number; /** Maximum iterations for convergence (default: 100) */ maxIterations?: number; /** Convergence epsilon (default: 0.001) */ epsilon?: number; } /** * Result type for Core-Periphery Decomposition. */ export declare type CorePeripheryResult = Result<{ structure: CorePeripheryStructure; metadata: { algorithm: "core-periphery"; runtime: number; iterations: number; converged: boolean; parameters: { coreThreshold?: number; maxIterations?: number; epsilon?: number; }; }; }, DecompositionError>; /** * Core-periphery structure. * Network decomposition into dense core and sparse periphery. */ export declare interface CorePeripheryStructure { /** Nodes identified as core (coreness > threshold) */ coreNodes: Set; /** Nodes identified as periphery (coreness ≤ threshold) */ peripheryNodes: Set; /** Per-node coreness scores (0.0 to 1.0) */ corenessScores: Map; /** Threshold used to separate core from periphery (default: 0.7) */ coreThreshold: number; /** Correlation between observed and ideal core-periphery structure */ fitQuality: number; } export declare const countSelfLoopsBinary: (g: AnalyzerGraph) => number; /** * Create a domain-specific importance function from node attributes * * @param nodes * @param attributeKey - Key to extract from node attributes * @param defaultValue - Default value if attribute is missing * @returns Importance function for use with domain-specific ground truth */ export declare const createAttributeImportance: (nodes: N[], attributeKey: string, defaultValue?: number) => (nodeId: string) => number; /** * Create a reusable path ranker with pre-computed MI cache. * * For ranking paths across multiple queries on the same graph, * this is more efficient than calling rankPaths repeatedly. * * @template N - Node type * @template E - Edge type * @param graph - The graph to analyse * @param config - Configuration for MI computation * @returns Object with ranking methods that reuse the MI cache * * @example * ```typescript * // Pre-compute once * const ranker = createPathRanker(graph, { * attributeExtractor: (node) => [node.value] * }); * * // Use for multiple queries (reuses MI cache) * const result1 = ranker.rank('A', 'B'); * const result2 = ranker.rank('C', 'D'); * const result3 = ranker.getBest('E', 'F'); * ``` */ export declare const createPathRanker: (graph: Graph, config?: Omit, "miCache">) => { /** * Rank paths between two nodes. * @param startId * @param endId * @param overrides */ rank: (startId: string, endId: string, overrides?: Partial>) => Result[]>, GraphError>; /** * Get the best path between two nodes. * @param startId * @param endId * @param overrides */ getBest: (startId: string, endId: string, overrides?: Partial>) => Result>, GraphError>; /** * Access the underlying MI cache. */ getMICache: () => MutualInformationCache; }; /** * Convenience helper for creating specs with commonly-used properties * @param overrides */ export declare const createSpec: (overrides?: GraphSpecPatch) => GraphSpec_2; /** * Regularity Properties * * Properties related to regular graphs and degree constraints. */ /** Cubic graph property (3-regular) */ export declare type Cubic = { kind: "cubic"; } | { kind: "non_cubic"; } | { kind: "unconstrained"; }; /** * Cycle detected error (for DAG-only algorithms like topological sort). */ export declare type CycleDetectedError = { type: "cycle-detected"; message: string; cyclePath: string[]; }; /** * Information about a detected cycle. * Contains the nodes and edges that form the cycle. * @template N - Node type * @template E - Edge type * nodes - Nodes forming the cycle * edges - Edges connecting the cycle nodes * @invariant nodes.length >= 2 (at least two nodes form a cycle) * @invariant edges.length === nodes.length (cycle closes back to start) * @example * ```typescript * const result = detectCycle(graph); * if (result.ok && result.value.some) { * const cycle = result.value.value; * console.log('Cycle nodes:', cycle.nodes.map(n => n.id)); * console.log('Cycle edges:', cycle.edges.map(e => e.id)); * } * ``` */ export declare interface CycleInfo { /** Nodes forming the cycle */ nodes: N[]; /** Edges connecting the cycle nodes */ edges: E[]; } /** Cycle presence property */ export declare type Cycles = { kind: "acyclic"; } | { kind: "cycles_allowed"; }; export declare const dag: DAGSpec; /** DAG specification */ export declare type DAGSpec = GraphSpec_2 & Readonly<{ directionality: { kind: "directed"; }; cycles: { kind: "acyclic"; }; edgeMultiplicity: { kind: "simple"; }; selfLoops: { kind: "disallowed"; }; }>; /** * Map of dataset IDs to metadata. */ export declare const DATASETS_BY_ID: Map; /** * DBLP co-authorship network. * * Large-scale collaboration network from computer science bibliography. * Nodes are authors, edges represent co-authorship on publications. * Note: This is a large dataset (300K+ nodes) and may take time to load. */ export declare const DBLP: BenchmarkDatasetMeta; /** * Error type for decomposition algorithms (k-core, core-periphery, biconnected). */ export declare type DecompositionError = { type: "EmptyGraph"; message: string; } | { type: "InvalidInput"; message: string; } | { type: "InsufficientNodes"; message: string; required: number; actual: number; }; export declare const defaultComputePolicy: ComputePolicy; /** Default graph specification for common cases */ export declare const defaultGraphSpec: GraphSpec_2; /** * Default weight function that uses edge.weight with fallback to 1. * This maintains backward compatibility with existing behavior. * @param edge */ export declare const defaultWeightFunction: (edge: E) => number; /** * Rank paths by sum of node degrees along path. * Prefers paths through high-degree hubs. * * @param graph - Graph to analyse * @param paths - Paths to rank * @returns Paths sorted by total degree (descending) */ export declare const degreeBasedRanker: (graph: Graph, paths: Path[]) => RankedPath[]; /** Degree constraints */ export declare type DegreeConstraint = { kind: "unconstrained"; } | { kind: "bounded"; max: number; } | { kind: "regular"; degree: number; } | { kind: "degree_sequence"; sequence: readonly number[]; }; /** * Compute degree distribution from a graph's node degrees. * * @param nodeDegrees - Map from node ID to degree * @returns Normalized degree distribution */ export declare const degreeDistributionFromMap: (nodeDegrees: Map) => Map; /** * Degree distribution comparison metrics. */ export declare interface DegreeDistributionMetrics { /** KL divergence from ground truth to sampled */ klDivergence: number; /** Jensen-Shannon divergence (symmetric) */ jsDivergence: number; /** Earth Mover's Distance */ emd: number; /** Mean degree of sampled */ sampledMeanDegree: number; /** Mean degree of ground truth */ groundTruthMeanDegree: number; /** Standard deviation of sampled degrees */ sampledStdDegree: number; /** Standard deviation of ground truth degrees */ groundTruthStdDegree: number; /** Max degree in sampled */ sampledMaxDegree: number; /** Max degree in ground truth */ groundTruthMaxDegree: number; } /** * Degree-Prioritised Bidirectional Expansion * * **Thesis Alignment**: This is the primary implementation of the seed-bounded * sampling algorithm described in Chapter 4 of the thesis. It embodies the * parameter-free design with implicit termination via frontier exhaustion. * * **Design Relationship**: * - BidirectionalBFS: Earlier design, N=2 only, has termination parameters (targetPaths, maxIterations) * - DegreePrioritisedExpansion: Refined design (this file), N≥1 with identical code path, parameter-free * * Use this implementation when: * - Representative sampling of graph structure is required * - Evaluation dataset construction demands bias-free samples * - N≥1 seed nodes need to be supported * - Termination should be determined by graph structure, not arbitrary limits * * For production pathfinding with resource constraints, consider BidirectionalBFS instead. * * A unified algorithm for representative graph sampling between N ≥ 1 seed nodes. * Uses node degree as priority (low degree = high priority) to explore peripheral * routes before hub-dominated paths. * * **Key Design Properties**: * 1. **Parameter-free termination**: No arbitrary limits on nodes, edges, or iterations. * The sole termination condition is structural: all frontiers exhausted. * 2. **N-seed generalisation**: Single algorithm handles N=1 (ego-network), N=2 * (bidirectional), and N≥3 (multi-frontier) with identical code path. * 3. **Emergent behaviour**: Different behaviours for different N values emerge * naturally from the same loop—no conditional branching based on seed count. * 4. **Degree prioritisation**: Always expands the globally lowest-degree node * across all frontiers, naturally avoiding hub explosion. * * **Algorithm**: * ``` * 1. Initialize N frontiers, one per seed * 2. While any frontier is non-empty: * a. Select the frontier with the lowest-degree node at its front * b. Pop that node and expand its neighbours * c. For each new neighbour, check intersection with all other frontiers * d. If intersection found, record path between the two seeds * 3. Return sampled subgraph (union of all visited nodes) * ``` * * **Complexity**: O(E log V) where E = edges explored, V = vertices * * @template T - Type of node data returned by expander * @example * ```typescript * const expansion = new DegreePrioritisedExpansion(expander, ['seedA', 'seedB']); * const result = await expansion.run(); * console.log(`Found ${result.paths.length} paths`); * console.log(`Sampled ${result.sampledNodes.size} nodes`); * ``` * * @see BidirectionalBFS - Parameterised version for N=2 with resource constraints */ export declare class DegreePrioritisedExpansion { private readonly expander; private readonly seeds; private readonly maxNodes?; private readonly hubThreshold; private readonly frontiers; private readonly paths; private readonly sampledEdges; private stats; /** Tracks when each node was first discovered (iteration number) */ private readonly nodeDiscoveryIteration; /** Track which frontier owns each node for O(1) intersection checking */ private readonly nodeToFrontierIndex; /** Track path signatures for O(1) deduplication */ private readonly pathSignatures; /** Maps hub node IDs to the expansion step when first expanded */ private readonly hubEncounterOrder; /** * Create a new degree-prioritised expansion. * * @param expander - Graph expander providing neighbour access * @param seeds - Array of seed node IDs (N ≥ 1) * @param maxNodes - Optional maximum nodes to expand * @param hubThreshold - Degree threshold for hub tracking (default: Infinity = no tracking) * @throws Error if no seeds provided */ constructor(expander: GraphExpander, seeds: readonly string[], maxNodes?: number | undefined, hubThreshold?: number); /** * Run the expansion to completion. * * Terminates when all frontiers are exhausted (no unexpanded nodes remain). * This is the ONLY termination condition—no arbitrary limits. * * @returns Expansion results including paths and sampled subgraph */ run(): Promise; /* Excluded from this release type: hasNonEmptyFrontier */ /* Excluded from this release type: selectLowestDegreeFrontier */ /* Excluded from this release type: peekPriority */ /* Excluded from this release type: reconstructPath */ /* Excluded from this release type: createPathSignature */ /* Excluded from this release type: recordDegree */ /* Excluded from this release type: getDegreeBucket */ } /** * Result from degree-prioritised expansion. */ export declare interface DegreePrioritisedExpansionResult { /** Discovered paths (only populated when N ≥ 2 seeds) */ paths: Array<{ fromSeed: number; toSeed: number; nodes: string[]; }>; /** Union of all nodes visited by all frontiers */ sampledNodes: Set; /** Set of edges visited during expansion */ sampledEdges: Set; /** Per-frontier visited sets (for diagnostics) */ visitedPerFrontier: Array>; /** Statistics about the expansion */ stats: ExpansionStats; /** * Maps each sampled node to the iteration when it was first discovered. * Used for computing coverage efficiency metrics (first-discovery iteration, * budget checkpoint coverage, area-under-curve). */ nodeDiscoveryIteration: Map; /** Maps hub node IDs to the expansion step when first expanded. Hub = degree >= hubThreshold */ hubEncounterOrder?: Map; } export declare const degreesUndirectedBinary: (g: AnalyzerGraph) => number[]; /** * Convert degree map to betweenness-like ranking. * * Since computing true betweenness centrality is expensive, * we use degree as a proxy (highly correlated in most networks). * * @param degrees - Map from node ID to degree * @returns Map from node ID to rank (1 = highest degree) */ export declare const degreeToRanking: (degrees: Map) => Map; /** * Hierarchical clustering dendrogram. * Tree structure showing nested clustering levels with cut operations. */ export declare interface Dendrogram { /** Sequence of cluster merge operations (n-1 merges for n nodes) */ merges: MergeStep[]; /** Height at which each merge occurred (non-decreasing) */ heights: number[]; /** Original graph nodes (leaves of dendrogram) */ leafNodes: N[]; /** Size of cluster formed at each merge step */ clusterSizes: number[]; /** * Cut dendrogram at specified height to produce flat clusters. * @param height - Height threshold for cutting * @returns Array of clusters (sets of nodes) */ cutAtHeight(height: number): Set[]; /** * Get exactly k clusters by cutting dendrogram. * @param numClusters - Desired number of clusters * @returns Array of exactly k clusters (sets of nodes) */ getClusters(numberClusters: number): Set[]; } /** Target density for graph generation */ export declare type Density = { kind: "sparse"; } | { kind: "moderate"; } | { kind: "dense"; } | { kind: "unconstrained"; }; /** * Generate a human-readable description of a GraphSpec. * @param spec */ export declare const describeSpec: (spec: GraphSpec_2) => string; /** * Information-theoretic description length (bits) */ export declare type DescriptionLength = number; /** * Detect bibliographic coupling pairs in directed citation graph. * * Two papers are bibliographically coupled when they cite the same references. * Identifies papers with similar research topics. * * Algorithm: * 1. Build reference sets for each paper * 2. Compare reference sets pairwise * 3. Return pairs with sufficient overlap * * Time complexity: O(N^2 * R) where N = papers, R = avg references * Space complexity: O(N * R) for reference sets * @param graph - Directed citation graph * @param options - Detection options * @returns Array of bibliographic coupling pairs * @example * ```typescript * const result = detectBibliographicCoupling(graph, { minShared: 3 }); * if (result.ok) { * result.value.forEach(pair => { * console.log(`${pair.paper1.id} and ${pair.paper2.id} share ${pair.sharedReferences} refs`); * }); * } * ``` */ export declare const detectBibliographicCoupling: (graph: Graph, options: BibliographicCouplingOptions) => Result[], InvalidInputError>; /** * Detect co-citation pairs in directed citation graph. * * Two papers are co-cited when multiple papers cite both of them. * Identifies papers with similar research impact. * * Algorithm: * 1. For each citing paper, find all its references * 2. Count pairs of references cited together * 3. Return pairs meeting minimum threshold * * Time complexity: O(N * R^2) where N = papers, R = avg references per paper * Space complexity: O(P^2) where P = unique papers * @param graph - Directed citation graph * @param options - Detection options * @returns Array of co-citation pairs * @example * ```typescript * const result = detectCoCitations(graph, { minCount: 5 }); * if (result.ok) { * result.value.forEach(pair => { * console.log(`${pair.paper1.id} and ${pair.paper2.id} co-cited ${pair.count} times`); * }); * } * ``` */ export declare const detectCoCitations: (graph: Graph, options: CoCitationOptions) => Result[], InvalidInputError>; /** * Detect communities using the Louvain algorithm. * * The Louvain method is a greedy optimization method that attempts to optimize * the modularity of a partition of the network. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param options - Optional configuration (combines legacy and optimization parameters) * @param options.weightFn - Weight function for edges (default: all edges weight 1.0) [Legacy] * @param options.resolution - Resolution parameter (default: 1.0, higher values favor more communities) [Legacy] * @param options.mode - Neighbor selection strategy ("auto", "best", "random") [spec-027 Phase 2] * @param options.seed - Random seed for deterministic shuffling [spec-027 Phase 2] * @param options.minModularityIncrease - Minimum modularity improvement to continue (adaptive default via getAdaptiveThreshold) * @param options.maxIterations - Maximum iterations per phase (adaptive default via getAdaptiveIterationLimit) * @returns Array of detected communities * @remarks * **Adaptive Defaults** (spec-027 Phase 1): * - `minModularityIncrease`: 1e-5 for >500 nodes, 1e-6 otherwise * - `maxIterations`: 20 for >200 nodes (level 0), 40-50 otherwise * * **Neighbor Selection Modes** (spec-027 Phase 2): * - `"auto"`: Best-neighbor for <200 nodes, random for ≥500 nodes * - `"best"`: Always use best-neighbor (quality-first) * - `"random"`: Always use random-neighbor (speed-first, Fast Louvain) * @example * ```typescript * const graph = new Graph(true); * // ... add nodes and edges ... * * // Basic usage (adaptive defaults) * const { communities, stats } = detectCommunities(graph); * console.log(`Found ${communities.length} communities in ${stats.totalIterations} iterations`); * * // Quality-first mode * const result = detectCommunities(graph, { mode: "best" }); * * // Speed-first mode for large graphs * const fast = detectCommunities(graph, { mode: "random", maxIterations: 10 }); * * // Reproducible results * const deterministic = detectCommunities(graph, { seed: 42 }); * ``` */ export declare const detectCommunities: (graph: Graph, options?: { weightFn?: WeightFunction; resolution?: number; mode?: "auto" | "best" | "random"; seed?: number; minModularityIncrease?: number; maxIterations?: number; }) => LouvainResult; /** * Detect cycles in a graph using DFS. * * For directed graphs: detects back edges (edges to ancestors in DFS tree) * For undirected graphs: detects any edge except parent edge * * Time Complexity: O(V + E) * Space Complexity: O(V) * @param graph - The graph to check for cycles * @returns Result containing Option with cycle info if found */ export declare const detectCycle: (graph: Graph) => Result>, InvalidInputError>; /** * Detect star patterns (hub nodes with high degree). * * For directed graphs: * - in-star: hub has high in-degree (many nodes point to it) * - out-star: hub has high out-degree (hub points to many nodes) * * For undirected graphs: only out-star makes sense (total degree) * * Time complexity: O(N + E) where N = nodes, E = edges * Space complexity: O(S) where S = number of stars * @param graph - Graph to analyze * @param options - Detection options * @returns Array of star patterns found * @example * ```typescript * const result = detectStarPatterns(graph, { minDegree: 10, type: 'out' }); * if (result.ok) { * result.value.forEach(star => { * console.log(`Hub ${star.hub.id} has ${star.leaves.length} connections`); * }); * } * ``` */ export declare const detectStarPatterns: (graph: Graph, options: StarPatternOptions) => Result[], InvalidInputError>; /** * Detect all triangles (3-cliques) in an undirected graph. * * Algorithm: For each edge (u,v), find common neighbors of u and v. * Each common neighbor w forms a triangle (u,v,w). * * Time complexity: O(E * d^2) where E = edges, d = max degree * Space complexity: O(T) where T = number of triangles * @param graph - Undirected graph to analyze * @returns Array of triangles found * @example * ```typescript * const graph = createTriangleGraph(); * const result = detectTriangles(graph); * if (result.ok) { * console.log(`Found ${result.value.length} triangles`); * } * ``` */ export declare const detectTriangles: (graph: Graph) => Result[], InvalidInputError>; /** * Determine optimal neighbor selection mode based on graph size. * @param nodeCount - Number of nodes in graph * @returns Neighbor selection mode ("best" or "random") * @remarks * **UPDATE (Phase 4 debugging)**: Random mode disabled for citation networks. * * Testing revealed Fast Louvain random-neighbor selection causes severe quality degradation * for citation network graphs (Q=0.05-0.12 vs Q=0.37 with best mode), failing the minimum * quality threshold of Q≥0.19. Random mode also paradoxically SLOWED convergence (201 iterations * vs 103 with best mode), resulting in 3x slower runtime. * * Root cause: Citation networks have different structural properties than the social/web networks * where Fast Louvain was benchmarked in literature. Accepting first positive ΔQ leads to poor-quality * moves that require many iterations to correct. * * **Current strategy**: Always use best-neighbor mode for quality. Random mode remains available * via explicit `mode: "random"` parameter for experimentation but is not recommended. */ export declare const determineOptimalMode: () => "best" | "random"; /** * Depth-First Search traversal. * @param graph * @param startId */ export declare const dfs: (graph: ReadableGraph, startId: string) => Result_3, InvalidInputError_3>; export declare interface DFSTraversalResult { /** Nodes in visitation order (depth-first) */ visitOrder: N[]; /** Parent mapping for path reconstruction (child → parent) */ parents: Map; /** Discovery timestamps for each node (when first visited) */ discovered: Map; /** Finish timestamps for each node (when all descendants visited) */ finished: Map; } /** * Metric Properties * * Properties based on distance metrics and graph dimensions. */ /** Longest shortest path in graph */ export declare type Diameter = { kind: "diameter"; value: number; } | { kind: "unconstrained"; }; /** * Dijkstra's shortest path algorithm. * * Finds the shortest path between two nodes in a weighted graph. * Uses a min-heap priority queue for efficient selection of next node to process. * * Time Complexity: O((V + E) log V) where V = vertices, E = edges * Space Complexity: O(V) for distances, predecessors, and priority queue * * **Important**: Does not work with negative edge weights. Use Bellman-Ford for graphs * with negative weights. * @param graph - The graph to search * @param startId - ID of the start node * @param endId - ID of the end node * @param weightFn - Optional function to extract weight from edges/nodes. Defaults to edge.weight ?? 1 * @param weightFunction * @returns Result containing Option or error * - Ok(Some(path)) if path exists * - Ok(None) if no path exists (disconnected) * - Err(NegativeWeightError) if negative weights detected * - Err(InvalidInputError) if start/end nodes not found * @example * ```typescript * const graph = new Graph(true); * graph.addNode({ id: 'A', type: 'test', elevation: 100 }); * graph.addNode({ id: 'B', type: 'test', elevation: 200 }); * graph.addEdge({ id: 'E1', source: 'A', target: 'B', type: 'edge', weight: 5 }); * * // Use default edge weights * const result1 = dijkstra(graph, 'A', 'B'); * * // Use custom edge attribute * const result2 = dijkstra(graph, 'A', 'B', (edge) => edge.customCost); * * // Use node elevation difference * const result3 = dijkstra(graph, 'A', 'B', (edge, source, target) => * Math.abs(source.elevation - target.elevation) * ); * ``` */ export declare const dijkstra: (graph: Graph, startId: string, endId: string, weightFunction?: WeightFunction) => Result>, GraphError>; /** * Core Graph Properties * * Fundamental property axes used in current test fixtures. */ /** Edge direction property */ export declare type Directionality = { kind: "directed"; } | { kind: "undirected"; }; /** * Intersection graph of disks in the plane */ declare type Disk = { kind: "disk"; } | { kind: "not_disk"; } | { kind: "unconstrained"; }; /** * Distances preserved in all connected induced subgraphs */ declare type DistanceHereditary = { kind: "distance_hereditary"; } | { kind: "not_distance_hereditary"; } | { kind: "unconstrained"; }; /** * Parsed UCINet DL document structure. */ export declare interface DlDocument { /** Number of nodes */ n: number; /** Number of matrices (for multi-relational data) */ nm?: number; /** Number of rows (if different from n) */ nr?: number; /** Number of columns (if different from n) */ nc?: number; /** Format type */ format: DlFormat; /** Whether the diagonal should be present (for fullmatrix) */ diagonal?: boolean; /** Node labels */ labels?: string[]; /** Row labels (for 2-mode networks) */ rowLabels?: string[]; /** Column labels (for 2-mode networks) */ colLabels?: string[]; /** Edge data - adjacency matrix or edge list depending on format */ edges: DlEdge[]; /** Matrix names (for multi-relational data) */ matrixLabels?: string[]; } /** * An edge in a DL document. */ export declare interface DlEdge { /** Source node (0-indexed after parsing) */ source: number; /** Target node (0-indexed after parsing) */ target: number; /** Edge weight */ weight: number; /** Matrix index (for multi-relational data) */ matrix?: number; } /** * UCINet DL format type definitions. * * UCINet is a software package for network analysis. * The DL format is its primary text-based network format. */ /** * Supported DL format types. */ export declare type DlFormat = "fullmatrix" | "edgelist1" | "edgelist2" | "nodelist1" | "nodelist2"; /** * Convert a parsed DL document to normalized JSON format. * * @param doc - Parsed DL document * @param document * @param options - Conversion options * @returns Graph in normalized JSON format */ export declare const dlToJson: (document: DlDocument, options: DlToJsonOptions) => GraphJson; /** * Options for converting DL to JSON. */ export declare interface DlToJsonOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection (default: true for DL format) */ directed?: boolean; } /** Domination number (γ): minimum vertices dominating all others */ export declare type DominationNumber = { kind: "domination_number"; value: number; } | { kind: "unconstrained"; }; /** * Duplicate node ID error (attempting to add node with existing ID). */ export declare type DuplicateNodeError = { type: "duplicate-node"; message: string; nodeId: string; }; /** * Compute Earth Mover's Distance (Wasserstein-1) for degree distributions. * * EMD measures the minimum "work" to transform one distribution into another. * For 1D distributions, this equals the integral of the absolute difference * between cumulative distribution functions. * * @param p - First distribution * @param q - Second distribution * @returns EMD (non-negative) */ export declare const earthMoversDistance: (p: Map, q: Map) => number; /** * Base Edge interface with required fields for graph connectivity. * All edge types must extend this interface. * * id - Unique edge identifier * source - ID of source node (must exist in graph) * target - ID of target node (must exist in graph) * type - Discriminator field for runtime type narrowing * weight - Optional edge weight (default: 1 if not specified) * * @example * ```typescript * type CitationEdge = { * id: string; * source: string; * target: string; * type: 'citation'; * year: number; * }; * * type AuthorshipEdge = { * id: string; * source: string; * target: string; * type: 'authorship'; * position: number; * }; * * type AcademicEdge = CitationEdge | AuthorshipEdge; * ``` */ export declare interface Edge extends EdgeBase_2 { id: string; type: string; weight?: number; [key: string]: unknown; } /** Edge arity (binary vs hypergraph) */ export declare type EdgeArity = { kind: "binary"; } | { kind: "k_ary"; k: number; }; /** * Base interface for graph edges. * * @template T - Additional properties extending the base edge */ export declare interface EdgeBase { /** Source node identifier */ source: string; /** Target node identifier */ target: string; /** Optional edge type/label */ type?: string; } /** * Base edge interface - minimum requirements. * All edge types must extend this with source and target fields. */ declare interface EdgeBase_2 { source: string; target: string; } /** Edge metadata */ export declare type EdgeData = { kind: "unlabelled"; } | { kind: "labelled"; } | { kind: "attributed"; }; export declare const edgeKeyBinary: (u: AnalyzerVertexId, v: AnalyzerVertexId, directed: boolean) => string; /** * Configuration for edge list loading */ export declare interface EdgeListConfig { /** Delimiter between fields (default: whitespace) */ delimiter?: string | RegExp; /** Whether graph is directed (default: false) */ directed?: boolean; /** Whether to skip lines starting with # (default: true) */ skipComments?: boolean; /** Number of header lines to skip (default: 0) */ headerLines?: number; /** Default node type (default: 'Node') */ nodeType?: string; /** Column index for source node (default: 0) */ sourceColumn?: number; /** Column index for target node (default: 1) */ targetColumn?: number; /** Column index for edge weight (default: undefined = no weight) */ weightColumn?: number; } /** Multiple edges between same vertices property */ export declare type EdgeMultiplicity = { kind: "simple"; } | { kind: "multi"; }; /** Edge ordering */ export declare type EdgeOrdering = { kind: "unordered"; } | { kind: "ordered"; }; /** Edge-transitive property (automorphisms can map any edge to any other) */ export declare type EdgeTransitive = { kind: "edge_transitive"; } | { kind: "not_edge_transitive"; } | { kind: "unconstrained"; }; export declare interface EgoNetworkOptions { /** Number of hops to include (0 = seed nodes only, 1 = immediate neighbors) */ radius: number; /** Seed node IDs to extract ego networks around */ seedNodes: string[]; /** Whether to include seed nodes in result (default: true) */ includeSeed?: boolean; } /** Graph embedding */ export declare type Embedding = { kind: "abstract"; } | { kind: "planar"; } | { kind: "surface_embedded"; } | { kind: "geometric_metric_space"; } | { kind: "spatial_coordinates"; dims: 2 | 3; }; /** * Enumerate all paths between two seed nodes up to a maximum length. * * Uses DFS with backtracking to find all simple paths (no repeated nodes). * This is exponential in the worst case but tractable for small graphs * and limited path lengths. * * @param graph - The graph to search * @param seedA - First seed node ID * @param seedB - Second seed node ID * @param options - Enumeration options * @returns Between-graph result with all nodes, edges, and paths */ export declare const enumerateBetweenGraph: (graph: Graph, seedA: string, seedB: string, options?: BetweenGraphOptions) => BetweenGraphResult; /** * Enumerate between-graph for multiple seed pairs. * * The result is the union of all individual between-graphs. * * @param graph - The graph to search * @param seedPairs - Array of seed pairs [[A1, B1], [A2, B2], ...] * @param options - Enumeration options * @returns Combined between-graph result */ export declare const enumerateMultiSeedBetweenGraph: (graph: Graph, seedPairs: Array<[string, string]>, options?: BetweenGraphOptions) => BetweenGraphResult; /** * Create a failed Result. * @template E - Error type * @param error - The error value * @returns Result with ok: false * @example * ```typescript * const result = Err('Something went wrong'); * // Result * ``` */ export declare const Err: (error: E) => Result; declare interface Error_ { ok: false; error: E; } declare interface Error__2 { ok: false; error: E; } declare interface Error__3 { ok: false; error: E; } /** Eulerian circuit property (uses every edge exactly once, returns to start) */ export declare type Eulerian = { kind: "eulerian"; } | { kind: "semi_eulerian"; } | { kind: "non_eulerian"; } | { kind: "unconstrained"; }; /** * Complete evaluation results for a single experiment. * * Note: The experiment runner uses flexible metric storage (Record) * to support different metric combinations without rigid schema requirements. */ export declare interface EvaluationResult { /** Spearman's ρ correlation */ spearman: number; /** Kendall's τ correlation */ kendall: number; /** NDCG at various cutoffs */ ndcg: { at5: number; at10: number; at20: number; full: number; }; /** Mean Average Precision */ map: number; /** Mean Reciprocal Rank */ mrr: number; /** Precision/Recall at K */ precision: { at5: number; at10: number; at20: number; }; recall: { at5: number; at10: number; at20: number; }; } /** * Statistics collected during expansion. */ export declare interface ExpansionStats { /** Total nodes expanded (popped from frontiers) */ nodesExpanded: number; /** Total edges traversed */ edgesTraversed: number; /** Iterations (single node expansions) performed */ iterations: number; /** Breakdown of nodes by degree ranges */ degreeDistribution: Map; /** Fraction of total expansion complete when first hub is expanded (0-1). -1 if no hubs. */ firstHubEncounterFraction?: number; /** Mean fraction of expansion complete across all hub encounters */ meanHubEncounterFraction?: number; } /** * Complete experiment configuration. */ export declare interface ExperimentConfig { /** Experiment name/identifier */ name: string; /** Description of what's being tested */ description?: string; /** Number of experiment repetitions (for statistical robustness) */ repetitions: number; /** Path planting configuration */ pathPlanting: PlantedPathConfig; /** Methods to compare */ methods: MethodConfig[]; /** Metrics to compute */ metrics: MetricType[]; /** Statistical tests to run */ statisticalTests: StatisticalTestType[]; /** Significance level for statistical tests (default: 0.05) */ alpha?: number; /** Number of bootstrap samples (default: 10000) */ nBootstrap?: number; /** Random seed for reproducibility */ seed: number; /** Optional: Cross-validation folds (default: no cross-validation) */ crossValidationFolds?: number; } /** * Full experiment report. */ export declare interface ExperimentReport { name: string; graphSpec: string; methods: MethodComparison[]; statisticalTests: StatisticalTestResult[]; winner: string; timestamp: string; duration?: number; } /** * Extracts a k-hop ego network around one or more seed nodes. * * An ego network includes all nodes within k hops (radius) of the seed nodes, * along with all edges between those nodes. This is useful for exploring * citation contexts, local neighborhoods, and relationship patterns. * * @param graph - Source graph to extract from (any ReadableGraph implementation) * @param options - Ego network extraction options * @returns Extracted subgraph or validation error * @example * ```typescript * // Using algorithms Graph class (via adapter) * const graph = new Graph(true); * // ... add nodes and edges ... * * const adapter = new GraphAdapter(graph); * const result = extractEgoNetwork(adapter, { * radius: 2, * seedNodes: ['P123'], * }); * * if (result.ok) { * console.log(`Found ${result.value.nodes.length} papers in 2-hop neighborhood`); * } * * // Using custom graph implementation * class MyDatabaseGraph implements ReadableGraph { * // ... implementation ... * } * * const result = extractEgoNetwork(new MyDatabaseGraph(), { * radius: 1, * seedNodes: ['A123', 'A456'], * }); * ``` */ export declare const extractEgoNetwork: (graph: ReadableGraph, options: EgoNetworkOptions) => Result_4, ExtractionError>; /** * Extracts an induced subgraph containing only the specified nodes * and all edges between them. * @param graph - Source graph * @param nodeIds - Set of node IDs to include in subgraph * @returns A new graph containing only the specified nodes and their interconnecting edges * * Time Complexity: O(V + E) where V is nodeIds.size and E is edges in original graph * Space Complexity: O(V + E') where E' is edges in induced subgraph */ export declare const extractInducedSubgraph: (graph: Graph, nodeIds: Set) => Result, InvalidInputError>; export declare interface ExtractionError { type: "invalid-input" | "invalid-options"; message: string; } /** * Extraction error discriminated union for graph extraction operations. */ declare type ExtractionError_2 = InvalidInputError | NodeNotFoundError | InvalidRadiusError | InvalidFilterError | InvalidTrussError; /** * Extracts k-truss subgraph from the input graph. * * K-truss: maximal subgraph where every edge participates in at least (k-2) triangles. * - 2-truss = entire graph (k-2=0, all edges included) * - 3-truss = edges in at least 1 triangle * - 4-truss = edges in at least 2 triangles * * Algorithm (iterative edge removal): * 1. Compute initial triangle support for all edges * 2. Create a working copy of the graph * 3. While edges with support < (k-2) exist: * a. Remove edge with insufficient support * b. Update triangle support for affected edges * c. Mark affected edges for recheck * 4. Return remaining subgraph * @param graph - Input graph (directed or undirected) * @param options - K-truss options (k value, hierarchy flag) * @returns Result containing k-truss subgraph or error * @example * ```typescript * // Extract 3-truss (edges in at least 1 triangle) * const result = extractKTruss(graph, { k: 3 }); * if (result.ok) { * const truss = result.value; * console.log(`3-truss has ${truss.getNodeCount()} nodes`); * } * ``` */ export declare const extractKTruss: (graph: Graph, options: KTrussOptions) => Result, ExtractionError_2>; /** * Convenience wrapper for extracting multi-source ego network. * * Extracts the union of ego networks around multiple seed nodes. * This is a simplified API for the common case of multi-source extraction. * * @param graph - Source graph * @param seedNodes - Array of seed node IDs * @param radius - Number of hops to include * @param includeSeed - Whether to include seed nodes (default: true) * @returns Extracted subgraph or error * @example * ```typescript * // Extract 1-hop neighborhoods around multiple authors * const result = extractMultiSourceEgoNetwork( * adapter, * ['A123', 'A456', 'A789'], * 1 * ); * ``` */ export declare const extractMultiSourceEgoNetwork: (graph: ReadableGraph, seedNodes: string[], radius: number, includeSeed?: boolean) => Result_4, ExtractionError>; /** * Facebook ego network. * * Combined ego networks from Facebook, representing friendships. * Nodes are users, edges are friendships (undirected). */ export declare const FACEBOOK: BenchmarkDatasetMeta; /** * Fetch a dataset from a URL, extract GML from zip, and convert to JSON. * * @param url - URL to a zip archive containing a GML file * @param options - Conversion options including metadata * @returns The converted graph and fetch metadata * * @example * ```typescript * const result = await fetchDataset( * 'https://websites.umich.edu/~mejn/netdata/karate.zip', * { * meta: { * name: "Zachary's Karate Club", * description: "Social network of friendships...", * source: "https://websites.umich.edu/~mejn/netdata/", * url: "https://websites.umich.edu/~mejn/netdata/karate.zip", * citation: { authors: ["W. W. Zachary"], title: "...", year: 1977 }, * retrieved: "2024-01-17" * } * } * ); * console.log(result.graph.nodes.length); // 34 * ``` */ export declare const fetchDataset: (url: string, options: FetchDatasetOptions) => Promise; /** * Options for fetching a dataset. */ export declare interface FetchDatasetOptions extends GmlToJsonOptions { /** Custom fetch function (for testing or custom environments) */ fetch?: typeof globalThis.fetch; /** File extension to look for in the archive (default: .gml) */ extension?: string; } /** * Result of fetching a dataset, including the graph and metadata about the fetch. */ export declare interface FetchDatasetResult { /** The converted graph */ graph: GraphJson; /** The filename that was extracted */ filename: string; /** Size of the downloaded archive in bytes */ archiveSize: number; /** Size of the extracted GML content in bytes */ contentSize: number; } /** * Fetch multiple datasets in parallel. * * @param datasets - Array of [url, options] tuples * @returns Array of fetch results */ export declare const fetchDatasets: (datasets: Array<[string, FetchDatasetOptions]>) => Promise; /** * Fetch a UCINet dataset from URL, decompress if needed, and convert to JSON. * * @param url - URL to .dl, .dl.gz, or .zip file * @param options - Conversion options * @returns Converted graph and fetch metadata */ export declare const fetchDlDataset: (url: string, options: FetchDlOptions) => Promise; /** * Options for fetching a UCINet dataset. */ export declare interface FetchDlOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection */ directed?: boolean; /** Custom fetch function */ fetch?: typeof globalThis.fetch; } /** * Result of fetching a UCINet dataset. */ export declare interface FetchDlResult { /** The converted graph */ graph: GraphJson; /** Original filename (from URL or archive) */ filename: string; /** Size of downloaded archive in bytes */ archiveSize: number; /** Size of decompressed content in bytes */ contentSize: number; } /** * Fetch a GD4 dataset from URL, decompress if needed, and convert to JSON. * * @param url - URL to .gd4 or .zip file * @param options - Conversion options * @returns Converted graph and fetch metadata */ export declare const fetchGd4Dataset: (url: string, options: FetchGd4Options) => Promise; /** * Options for fetching a GD4 dataset. */ export declare interface FetchGd4Options { /** Metadata to include in output */ meta: Omit; /** Custom fetch function */ fetch?: typeof globalThis.fetch; /** Specific .gd4 filename to extract from ZIP (e.g. "challenge/prob1.gd4") */ entryName?: string; } /** * Result of fetching a GD4 dataset. */ export declare interface FetchGd4Result { /** The converted graph */ graph: GraphJson; /** Original filename (from URL or archive) */ filename: string; /** Size of downloaded archive in bytes */ archiveSize: number; /** Size of decompressed content in bytes */ contentSize: number; } /** * Fetch a Matrix Market dataset from SuiteSparse URL. * * Expects a .tar.gz archive containing a .mtx file and optional _nodename.txt. * * @param url - URL to .tar.gz archive * @param options - Conversion options * @returns Converted graph and fetch metadata */ export declare const fetchMtxDataset: (url: string, options: FetchMtxOptions) => Promise; /** * Options for fetching a Matrix Market dataset. */ export declare interface FetchMtxOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection */ directed?: boolean; /** Custom fetch function */ fetch?: typeof globalThis.fetch; } /** * Result of fetching a Matrix Market dataset. */ export declare interface FetchMtxResult { /** The converted graph */ graph: GraphJson; /** Original filename */ filename: string; /** Size of downloaded archive in bytes */ archiveSize: number; } /** * Fetch a Pajek dataset from URL, decompress if needed, and convert to JSON. * * @param url - URL to .net, .net.gz, or .zip file * @param options - Conversion options * @returns Converted graph and fetch metadata */ export declare const fetchPajekDataset: (url: string, options: FetchPajekOptions) => Promise; /** * Options for fetching a Pajek dataset. */ export declare interface FetchPajekOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection */ directed?: boolean; /** Custom fetch function */ fetch?: typeof globalThis.fetch; } /** * Result of fetching a Pajek dataset. */ export declare interface FetchPajekResult { /** The converted graph */ graph: GraphJson; /** Original filename (from URL or archive) */ filename: string; /** Size of downloaded archive in bytes */ archiveSize: number; /** Size of decompressed content in bytes */ contentSize: number; } /** * Fetch a SNAP dataset from URL, decompress, and convert to JSON. * * @param url - URL to .txt.gz file * @param options - Conversion options * @returns Converted graph and fetch metadata */ export declare const fetchSnapDataset: (url: string, options: FetchSnapOptions) => Promise; /** * Options for fetching a SNAP dataset. */ export declare interface FetchSnapOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection */ directed?: boolean; /** Custom fetch function */ fetch?: typeof globalThis.fetch; } /** * Result of fetching a SNAP dataset. */ export declare interface FetchSnapResult { /** The converted graph */ graph: GraphJson; /** Size of downloaded archive in bytes */ archiveSize: number; /** Size of decompressed content in bytes */ contentSize: number; } /** * Creates a copy of the graph with only specific edge types. * @param graph - Source graph * @param edgeTypes - Set of edge types to include * @returns A new graph containing only edges of the specified types */ export declare const filterByEdgeType: (graph: Graph, edgeTypes: Set) => Result, InvalidInputError>; /** * Extracts a subgraph by filtering nodes and edges based on predicates. * @param graph - Source graph * @param nodePredicate - Function to determine if a node should be included * @param edgePredicate - Optional function to determine if an edge should be included * @returns A new graph containing only nodes/edges that pass the predicates * * Time Complexity: O(V + E) * Space Complexity: O(V' + E') */ export declare const filterGraph: (graph: Graph, nodePredicate: (node: N) => boolean, edgePredicate?: (edge: E) => boolean) => Result, InvalidInputError>; /** * Filters a graph based on node and edge attributes. * * Supports multiple filtering modes: * - Node predicates: Filter nodes by custom logic * - Edge predicates: Filter edges by custom logic * - Node attributes: Filter nodes by attribute values * - Edge types: Filter edges by type set * - Combine modes: AND (default) or OR for multiple filters * @param graph - Source graph to filter * @param filter - Filter specification with predicates and options * @returns Result containing filtered subgraph or error * * Time Complexity: O(V + E) where V = nodes, E = edges * Space Complexity: O(V' + E') where V', E' are filtered counts * @example * ```typescript * // Filter for recent high-impact papers * const result = filterSubgraph(graph, { * nodePredicate: (node) => node.year >= 2020 && node.citationCount >= 100, * edgeTypes: new Set(['cites']), * combineMode: 'and' * }); * ``` */ export declare const filterSubgraph: (graph: Graph, filter: SubgraphFilter) => Result, ExtractionError_2>; /** * Find the size of the maximum clique in a graph. * * A clique is a complete subgraph where all vertices are connected. * This uses the Bron-Kerbosch algorithm with pivot for efficiency. * * Time complexity: O(3^(n/3)) for n vertices * * @param nodes - Graph nodes * @param edges - Graph edges * @param directed - Whether graph is directed * @param _directed * @returns Size of maximum clique */ export declare const findMaxCliqueSize: (nodes: TestNode[], edges: TestEdge[], _directed: boolean) => number; /** Flow network property */ export declare type FlowNetwork = { kind: "flow_network"; source: string; sink: string; } | { kind: "not_flow_network"; } | { kind: "unconstrained"; }; /** * Format the age of a snapshot as a human-readable string. * * @param timestamp * @example * ```ts * formatAge("20260115111255"); // "2 days ago" * formatAge("20251117111255"); // "2 months ago" * ``` */ export declare const formatAge: (timestamp: string) => string; /** * Format a Wayback timestamp as a readable date string. * * @param timestamp * @example * ```ts * formatTimestamp("20260117111255"); // "2026-01-17 11:12:55" * ``` */ export declare const formatTimestamp: (timestamp: string) => string; /** * Frontier-Balanced Bidirectional BFS (Cerf et al. 2024) * * Baseline algorithm that balances expansion by always expanding from the * smaller frontier. This optimises for finding ANY path quickly by reducing * the total search space. * * Reference: Cerf et al. (2024) "Efficient Bidirectional Search" * * **Key Properties**: * - Always expands from the frontier with fewer unexpanded nodes * - Optimises for speed to find first path * - Still converges through hubs (no degree awareness) * - Better than standard BFS for finding single paths quickly * * **Comparison with Degree-Prioritised**: * - Frontier-balanced: Minimises nodes expanded before FIRST path found * - Degree-prioritised: Maximises path DIVERSITY by avoiding hubs * * @template T - Type of node data returned by expander */ export declare class FrontierBalancedExpansion { private readonly expander; private readonly seeds; private readonly maxNodes?; private readonly hubThreshold; private readonly frontiers; private readonly paths; private readonly sampledEdges; private stats; private readonly nodeDiscoveryIteration; /** Maps hub node IDs to the expansion step when first expanded */ private readonly hubEncounterOrder; private lastActiveFrontier; /** * Create a new frontier-balanced expansion. * * @param expander - Graph expander providing neighbour access * @param seeds - Array of seed node IDs (N >= 1) * @param maxNodes - Optional maximum nodes to expand * @param hubThreshold - Degree threshold for hub tracking (default: Infinity = no tracking) * @throws Error if no seeds provided */ constructor(expander: GraphExpander, seeds: readonly string[], maxNodes?: number | undefined, hubThreshold?: number); /** * Run the expansion to completion. * * Terminates when all frontiers are exhausted (no unexpanded nodes remain). * * @returns Expansion results including paths and sampled subgraph */ run(): Promise; /* Excluded from this release type: hasNonEmptyFrontier */ /* Excluded from this release type: selectSmallestFrontier */ /* Excluded from this release type: reconstructPath */ /* Excluded from this release type: pathExists */ /* Excluded from this release type: recordDegree */ /* Excluded from this release type: getDegreeBucket */ } /** * Result from frontier-balanced expansion - matches DegreePrioritisedExpansionResult. */ export declare interface FrontierBalancedResult { /** Discovered paths (only populated when N >= 2 seeds) */ paths: Array<{ fromSeed: number; toSeed: number; nodes: string[]; }>; /** Union of all nodes visited by all frontiers */ sampledNodes: Set; /** Set of edges visited during expansion */ sampledEdges: Set; /** Per-frontier visited sets (for diagnostics) */ visitedPerFrontier: Array>; /** Statistics about the expansion */ stats: FrontierBalancedStats; /** Maps each node to the iteration when it was first discovered */ nodeDiscoveryIteration: Map; /** Maps hub node IDs to the expansion step when first expanded. Hub = degree >= hubThreshold */ hubEncounterOrder: Map; } /** * Statistics collected during frontier-balanced expansion. */ export declare interface FrontierBalancedStats { /** Total nodes expanded (popped from frontiers) */ nodesExpanded: number; /** Total edges traversed */ edgesTraversed: number; /** Iterations (single node expansions) performed */ iterations: number; /** Breakdown of nodes by degree ranges */ degreeDistribution: Map; /** Number of frontier switches due to balancing */ frontierSwitches: number; /** Fraction of total expansion complete when first hub is expanded (0-1). -1 if no hubs. */ firstHubEncounterFraction: number; /** Mean fraction of expansion complete across all hub encounters */ meanHubEncounterFraction: number; } /** * Full experiment configuration with graph specs. */ export declare interface FullExperimentConfig { /** Base experiment configuration */ experiment: ExperimentConfig; /** Graph specifications to test */ graphSpecs: GraphSpec[]; /** Number of instances per graph spec (default: 1) */ instancesPerSpec?: number; } /** * Parsed GD4 document structure. */ export declare interface Gd4Document { /** Declared node count */ nodeCount: number; /** Node definitions with coordinates */ nodes: Gd4Node[]; /** Undirected edges */ edges: Gd4Edge[]; } /** * An edge in a GD4 document. */ export declare interface Gd4Edge { /** Source node index (0-indexed) */ source: number; /** Target node index (0-indexed) */ target: number; } /** * GD4 file format type definitions. * * The .gd4 format was used for the Graph Drawing 2004 contest. * It is a simple ASCII format for undirected graphs with node coordinates. * * Format: * - First line: N (number of nodes) * - Next N lines: X Y coordinate pairs (doubles, 0-indexed) * - Remaining lines: A B integer pairs (undirected edges, 0-indexed) * - Lines starting with # are comments */ /** * A node in a GD4 document. */ export declare interface Gd4Node { /** Node index (0-indexed) */ index: number; /** X coordinate */ x: number; /** Y coordinate */ y: number; } /** * Convert a parsed GD4 document to normalised JSON format. * * GD4 graphs are always undirected. * * @param document - Parsed GD4 document * @param options - Conversion options * @returns Graph in normalised JSON format */ export declare const gd4ToJson: (document: Gd4Document, options: Gd4ToJsonOptions) => GraphJson; /** * Options for converting GD4 to JSON. */ export declare interface Gd4ToJsonOptions { /** Metadata to include in output (directed is always false for GD4) */ meta: Omit; } /** * Contains no induced gem graph */ declare type GemFree = { kind: "gem_free"; } | { kind: "has_gem"; } | { kind: "unconstrained"; }; /** * Generate all valid permutations of core GraphSpec properties. * Filters out invalid combinations (e.g., connected + acyclic + complete). */ export declare const generateCoreSpecPermutations: () => GraphSpec_2[]; /** * Generate a test graph matching specified properties. * @param spec * @param config */ export declare const generateGraph: (spec: GraphSpec_2, config: GraphGenerationConfig) => TestGraph; /** * Generate comprehensive HTML report. * * @param report - Experiment report * @returns HTML string with embedded CSS * * @example * ```typescript * const html = generateHTMLReport(report); * // Save to file * fs.writeFileSync('report.html', html); * ``` */ export declare const generateHTMLReport: (report: ExperimentReport) => string; /** * Generate JSON summary for programmatic access. * * @param report - Experiment report * @returns JSON string with pretty formatting * * @example * ```typescript * const json = generateJSONSummary(report); * const data = JSON.parse(json); * console.log(data.methods[0].results.spearman); // 0.85 * ``` */ export declare const generateJSONSummary: (report: ExperimentReport) => string; /** * Generate LaTeX table from experiment results. * * @param report - Experiment report * @returns LaTeX table string * * @example * ```typescript * const latex = generateLatexTable(report); * console.log(latex); * // Output: * // \\begin{table}[h] * // \\centering * // \\begin{tabular}{lcccc} * // \\toprule * // Method & Spearman & Kendall & NDCG \\\\ * // \\midrule * // MI & 0.85 & 0.72 & 0.88 \\\\ * // Random & 0.02 & 0.01 & 0.05 \\\\ * // \\bottomrule * // \\end{tabular} * // \\end{table} * ``` */ export declare const generateLatexTable: (report: ExperimentReport) => string; /** * Generate markdown report from experiment results. * * @param report - Experiment report to format * @returns Formatted markdown string * * @example * ```typescript * const report = await runExperiment(config, graph); * const markdown = generateMarkdownReport(report); * console.log(markdown); * // Output: * // # MI vs Random Baseline * // * // ## Results * // * // ### Method Performance * // * // | Method | Spearman | Kendall | NDCG | * // |--------|----------|---------|------| * // | MI | 0.85 | 0.72 | 0.88 | * // | Random | 0.02 | 0.01 | 0.05 | * // ``` */ export declare const generateMarkdownReport: (report: ExperimentReport) => string; /** * Get adaptive iteration limit based on graph size and hierarchy level. * @param nodeCount - Number of nodes in graph * @param level - Hierarchy level (0 = first level) * @returns Maximum iterations (20, 40, or 50) * @remarks * First hierarchy level (level 0) with large graphs (>200 nodes) uses lower limit (20) * because most node movements happen in the first iteration. * Subsequent levels and small graphs use higher limits (40-50) for refinement. */ export declare const getAdaptiveIterationLimit: (nodeCount: number, level: number) => number; /** * Get adaptive convergence threshold based on graph size. * @param nodeCount - Number of nodes in graph * @returns Convergence threshold (1e-5 for large graphs, 1e-6 for small graphs) * @remarks * Large graphs (>500 nodes) use looser threshold for faster convergence. * Small graphs (≤500 nodes) use stricter threshold for higher quality. */ export declare const getAdaptiveThreshold: (nodeCount: number) => number; /** * Get adjusted validation expectations for impossible combinations. * For specs with warnings, relax certain validation constraints. * @param spec */ export declare const getAdjustedValidationExpectations: (spec: GraphSpec_2) => Partial>; /** * Get summary statistics for a loaded benchmark. * * @param benchmark - Loaded benchmark * @returns Summary string */ export declare const getBenchmarkSummary: (benchmark: LoadedBenchmark) => string; /** * Get the best (highest-ranked) path between two nodes. * * Convenience function that returns only the top-ranked path. * * @template N - Node type * @template E - Edge type * @param graph - The graph to search * @param startId - Source node ID * @param endId - Target node ID * @param config - Optional configuration * @returns Result containing best path or error * * @example * ```typescript * const result = getBestPath(graph, 'A', 'Z'); * if (result.ok && result.value.some) { * const best = result.value.value; * console.log('Best path score:', best.score); * } * ``` */ export declare const getBestPath: (graph: Graph, startId: string, endId: string, config?: PathRankingConfig) => Result>, GraphError>; /** * Get multiple historical snapshots for a URL. * * Uses the CDX Server API to retrieve snapshot history. * Results are returned in reverse chronological order (most recent first). * * @param url * @param options * @example * ```ts * // Get last 5 snapshots * const snapshots = await getSnapshots("https://example.com", { limit: 5 }); * for (const snapshot of snapshots) { * console.log(snapshot.archived); * } * * // Get snapshots from 2024 * const snapshots2024 = await getSnapshots("https://example.com", { * from: "20240101", * to: "20241231", * }); * ``` */ export declare const getSnapshots: (url: string, options?: SnapshotOptions) => Promise; /** Length of shortest cycle */ export declare type Girth = { kind: "girth"; girth: number; } | { kind: "unconstrained"; }; /** * Glass's delta (alternative to Cohen's d). * * Uses standard deviation of control group only instead of pooled SD. * Useful when treatment group variance is expected to differ from control. * * @param treatment - Samples from treatment group * @param control - Samples from control group (used for SD normalization) * @returns Effect size and interpretation * * @example * ```typescript * const treatment = [8, 9, 7, 8, 10]; * const control = [5, 6, 5, 6, 7]; * const result = glassDelta(treatment, control); * console.log(result.effectSize); // e.g., 1.8 * ``` */ export declare const glassDelta: (treatment: number[], control: number[]) => { effectSize: number; interpretation: "negligible" | "small" | "medium" | "large" | "very-large"; }; /** * Parsed GML document (intermediate representation). */ export declare interface GmlDocument { /** Creator comment (if present) */ creator?: string; /** Graph-level properties */ graph: { directed?: 0 | 1; [key: string]: unknown; }; /** Nodes from the GML file */ nodes: GmlNode[]; /** Edges from the GML file */ edges: GmlEdge[]; } /** * Edge as parsed from GML. */ export declare interface GmlEdge { source: number; target: number; value?: number; weight?: number; [key: string]: unknown; } /** * Node as parsed from GML. */ export declare interface GmlNode { id: number; label?: string; value?: unknown; [key: string]: unknown; } /** * Convert a parsed GML document to the normalized JSON format. * * @param doc - Parsed GML document * @param document * @param options - Conversion options including metadata * @returns Graph in normalized JSON format */ export declare const gmlToJson: (document: GmlDocument, options: GmlToJsonOptions) => GraphJson; /** * Options for converting GML to JSON. */ export declare interface GmlToJsonOptions { /** Metadata to include in the output */ meta: Omit; /** Map GML node IDs (numeric) to string IDs */ nodeIdMapper?: (id: number, node: GmlNode) => string; } /** * Generic graph data structure supporting both directed and undirected graphs. * Uses adjacency list representation for efficient neighbor lookup (O(1) average case). * @template N - Node type (must extend Node interface with id and type fields) * @template E - Edge type (must extend Edge interface with source, target fields) * @example * ```typescript * type WorkNode = { id: string; type: 'work'; title: string }; * type CitationEdge = { id: string; source: string; target: string; type: 'citation' }; * * const graph = new Graph(true); // directed graph * graph.addNode({ id: 'W1', type: 'work', title: 'Paper A' }); * graph.addNode({ id: 'W2', type: 'work', title: 'Paper B' }); * graph.addEdge({ id: 'E1', source: 'W1', target: 'W2', type: 'citation' }); * ``` */ export declare class Graph { /** Node storage (ID → Node) */ private nodes; /** Edge storage (ID → Edge) */ private edges; /** Adjacency list (Node ID → Set of neighbor IDs) */ private adjacencyList; /** Graph directionality */ private directed; /** * Create a new graph. * @param directed - Whether the graph is directed (true) or undirected (false) */ constructor(directed: boolean); /** * Add a node to the graph. * @param node - Node to add * @returns Ok(void) if successful, Err(DuplicateNodeError) if node ID already exists * @example * ```typescript * const result = graph.addNode({ id: 'N1', type: 'test', label: 'Node 1' }); * if (!result.ok) { * console.error('Failed to add node:', result.error.message); * } * ``` */ addNode(node: N): Result; /** * Remove a node from the graph (and all incident edges). * @param id - Node ID to remove * @returns Ok(void) if successful, Err(InvalidInputError) if node not found */ removeNode(id: string): Result; /** * Check if node exists in graph. * @param id - Node ID to check * @returns true if node exists, false otherwise */ hasNode(id: string): boolean; /** * Get node by ID. * @param id - Node ID to retrieve * @returns Some(node) if found, None if not found * @example * ```typescript * const nodeOption = graph.getNode('N1'); * if (nodeOption.some) { * console.log('Found:', nodeOption.value); * } * ``` */ getNode(id: string): Option_2; /** * Add an edge to the graph. * @param edge - Edge to add * @returns Ok(void) if successful, Err(InvalidInputError) if source/target nodes don't exist * @example * ```typescript * const result = graph.addEdge({ id: 'E1', source: 'N1', target: 'N2', type: 'link' }); * if (!result.ok) { * console.error('Failed to add edge:', result.error.message); * } * ``` */ addEdge(edge: E): Result; /** * Remove an edge from the graph. * @param id - Edge ID to remove * @returns Ok(void) if successful, Err(InvalidInputError) if edge not found */ removeEdge(id: string): Result; /** * Get neighbor node IDs for a given node. * @param id - Node ID to get neighbors for * @returns Ok(neighbor IDs) if successful, Err(InvalidInputError) if node not found * @example * ```typescript * const result = graph.getNeighbors('N1'); * if (result.ok) { * console.log('Neighbors:', result.value); * } * ``` */ getNeighbors(id: string): Result; /** * Get total number of nodes in graph. * @returns Node count */ getNodeCount(): number; /** * Get total number of edges in graph. * @returns Edge count */ getEdgeCount(): number; /** * Check if graph is directed. * @returns true if directed, false if undirected */ isDirected(): boolean; /** * Get all nodes in the graph. * @returns Array of all nodes * @example * ```typescript * const nodes = graph.getAllNodes(); * console.log('Total nodes:', nodes.length); * ``` */ getAllNodes(): N[]; /** * Get all edges in the graph. * @returns Array of all edges * @example * ```typescript * const edges = graph.getAllEdges(); * console.log('Total edges:', edges.length); * ``` */ getAllEdges(): E[]; /** * Get an edge by its ID. * @param id - Edge ID to look up * @returns Option containing the edge, or None if not found * @example * ```typescript * const edge = graph.getEdge('E1'); * if (edge.some) { * console.log('Edge found:', edge.value); * } * ``` */ getEdge(id: string): Option_2; /** * Get all outgoing edges from a node. * * For directed graphs: Returns edges where node is the source. * For undirected graphs: Returns edges where node is either source or target. * @param id - Node ID to get outgoing edges from * @returns Result containing array of outgoing edges, or error if node not found * @example * ```typescript * const result = graph.getOutgoingEdges('N1'); * if (result.ok) { * console.log('Outgoing edges:', result.value); * } * ``` */ getOutgoingEdges(id: string): Result; } /** * Adapts the algorithms Graph class to the ReadableGraph interface. * * @template N - Node type extending Node * @template E - Edge type extending Edge * @example * ```typescript * const graph = new Graph(true); * graph.addNode({ id: 'A', type: 'test' }); * graph.addNode({ id: 'B', type: 'test' }); * graph.addEdge({ id: 'E1', source: 'A', target: 'B', type: 'edge' }); * * const adapter = new GraphAdapter(graph); * const result = bfs(adapter, 'A'); * ``` */ export declare class GraphAdapter implements ReadableGraph { private readonly graph; constructor(graph: Graph); hasNode(id: string): boolean; getNode(id: string): N | null; getNeighbors(id: string): string[]; getAllNodes(): N[]; isDirected(): boolean; getOutgoingEdges(id: string): E[]; } /** * An edge in the graph. */ export declare interface GraphEdge { /** Source node ID */ source: string; /** Target node ID */ target: string; /** Optional edge weight */ weight?: number; /** Per-edge directed override (if different from graph default) */ directed?: boolean; /** Additional arbitrary properties */ [key: string]: unknown; } /** * Base discriminated union for all graph operation errors. * Pattern match using the `type` discriminator field. * @example * ```typescript * const handleError = (error: GraphError) => { * switch (error.type) { * case 'invalid-input': * console.error('Invalid input:', error.message); * break; * case 'negative-weight': * console.error('Negative weight on edge:', error.edgeId); * break; * case 'cycle-detected': * console.error('Cycle found:', error.cyclePath); * break; * case 'duplicate-node': * console.error('Duplicate node:', error.nodeId); * break; * case 'invalid-weight': * console.error('Invalid weight type:', typeof error.weight); * break; * } * }; * ``` */ export declare type GraphError = InvalidInputError | InvalidWeightError | NegativeWeightError | CycleDetectedError | DuplicateNodeError; /** * GraphExpander - Interface for dynamic neighbor discovery during graph traversal. * * Unlike ReadableGraph (which assumes fully-loaded graphs), GraphExpander enables * algorithms to work with partially-loaded graphs by dynamically fetching neighbors * from external sources (APIs, databases, file systems). * * Key difference from ReadableGraph: * - ReadableGraph: Assumes entire graph is loaded in memory * - GraphExpander: Supports lazy-loading and dynamic expansion * * Use cases: * - OpenAlex API calls during traversal * - Database queries for large graphs * - File-based graph streaming * - Caching layers (memory → disk → API) * * @template T - Type of node data */ declare interface GraphExpander { /** * Get neighbors of a node, potentially fetching from external source. * * This method may: * - Return cached neighbors (already fetched) * - Query an API/database (lazy loading) * - Throw errors if fetch fails (caller should handle) * * @param nodeId - Node whose neighbors to fetch * @returns Promise resolving to array of neighbor relationships */ getNeighbors(nodeId: string): Promise; /** * Get node degree for priority computation. * * Used to prioritize low-degree (specific) nodes over high-degree (generic) * nodes in traversal algorithms like BidirectionalBFS. * * This should return the CURRENT degree (neighbors already loaded), * not the POTENTIAL degree (all possible neighbors). * * @param nodeId - Node to get degree for * @returns Number of relationships (higher = lower priority) */ getDegree(nodeId: string): number; /** * Calculate weighted priority for thesis-aligned degree-prioritised expansion. * * Implements the priority function from Equation 4.106: * $$\pi(v) = \frac{\deg^{+}(v) + \deg^{-}(v)}{w_V(v) + \epsilon}$$ * * Where: * - $\deg^{+}(v)$: Weighted out-degree (sum of outgoing edge weights) * - $\deg^{-}(v)$: Weighted in-degree (sum of incoming edge weights) * - $w_V(v)$: Node weight for normalization (default 1) * - $\epsilon$: Small constant to prevent division by zero (default 1e-10) * * @param nodeId - Node to calculate priority for * @param options - Optional configuration for weighted calculation * @returns Priority value (lower = higher priority, expanded earlier) */ calculatePriority(nodeId: string, options?: PriorityOptions): number; /** * Get node data (may fetch from cache/API). * * @param nodeId - Node to retrieve * @returns Promise resolving to node data or null if not found */ getNode(nodeId: string): Promise; /** * Add an edge to the final graph output. * * Called during node expansion to track discovered relationships. * This is separated from fetching to allow algorithms to: * - Discover edges without storing them * Filter edges before adding * Build output graphs separately from input graphs * * @param source - Source node ID * @param target - Target node ID * @param relationshipType - Type of relationship */ addEdge(source: string, target: string, relationshipType: string): void; } /** * Configuration for graph generation. */ export declare interface GraphGenerationConfig { /** Number of nodes to generate */ nodeCount: number; /** Node type distribution (for heterogeneous graphs) */ nodeTypes?: { type: string; proportion: number; }[]; /** Edge type distribution (for heterogeneous graphs) */ edgeTypes?: { type: string; proportion: number; }[]; /** Weight range for weighted graphs */ weightRange?: { min: number; max: number; }; /** Random seed for reproducibility */ seed?: number; } /** * Complete graph in the normalized JSON format. */ export declare interface GraphJson { /** Metadata about the graph */ meta: GraphMeta; /** Array of nodes */ nodes: GraphNode[]; /** Array of edges */ edges: GraphEdge[]; } /** * Metadata for a graph dataset. */ export declare interface GraphMeta { /** Human-readable name of the dataset */ name: string; /** Description of what the graph represents */ description: string; /** Canonical human-readable web page for the dataset */ source: string; /** Direct download URL for the data file */ url: string; /** Structured citation information */ citation: Citation; /** Date when the data was retrieved (ISO format) */ retrieved: string; /** Whether edges are directed */ directed: boolean; /** Original creator of the GML file (if applicable) */ creator?: string; } /** * A node in the graph. */ export declare interface GraphNode { /** Unique identifier for the node */ id: string; /** Optional label/name for display */ label?: string; /** Additional arbitrary properties (preserved from source) */ [key: string]: unknown; } /** * Graph specification for experiment. * * Defines what type of graph to use for experiments. */ export declare interface GraphSpec { /** Graph type identifier */ type: string; /** Number of nodes */ nodeCount: number; /** Edge probability (for random graphs) */ edgeProbability?: number; /** Number of communities (for community-structured graphs) */ communities?: number; /** Whether graph is directed */ directed?: boolean; /** Whether graph is weighted */ weighted?: boolean; /** Optional seed for deterministic graph generation */ seed?: number; } /** * Complete graph specification with all 46 property axes. * Uses discriminated unions for type-safe property composition. */ declare type GraphSpec_2 = Readonly<{ directionality: Directionality; weighting: Weighting; cycles: Cycles; connectivity: Connectivity; schema: SchemaHomogeneity; edgeMultiplicity: EdgeMultiplicity; selfLoops: SelfLoops; density: Density; completeness: Completeness; vertexCardinality?: VertexCardinality; vertexIdentity?: VertexIdentity; vertexOrdering?: VertexOrdering; edgeArity?: EdgeArity; signedness?: Signedness; uncertainty?: Uncertainty; vertexData?: VertexData; edgeData?: EdgeData; degreeConstraint?: DegreeConstraint; partiteness?: Partiteness; embedding?: Embedding; rooting?: Rooting; temporal?: Temporal; layering?: Layering; edgeOrdering?: EdgeOrdering; ports?: Ports; observability?: Observability; operationalSemantics?: OperationalSemantics; measureSemantics?: MeasureSemantics; scaleFree?: ScaleFree; smallWorld?: SmallWorld; communityStructure?: CommunityStructure; unitDisk?: UnitDisk; planar?: Planar; hamiltonian?: Hamiltonian; traceable?: Traceable; perfect?: Perfect; split?: Split; cograph?: Cograph; threshold?: Threshold; line?: Line; clawFree?: ClawFree; cubic?: Cubic; specificRegular?: SpecificRegular; stronglyRegular?: StronglyRegular; selfComplementary?: SelfComplementary; vertexTransitive?: VertexTransitive; edgeTransitive?: EdgeTransitive; arcTransitive?: ArcTransitive; diameter?: Diameter; radius?: Radius; girth?: Girth; circumference?: Circumference; hereditaryClass?: HereditaryClass; independenceNumber?: IndependenceNumber; vertexCover?: VertexCover; dominationNumber?: DominationNumber; spectrum?: Spectrum; algebraicConnectivity?: AlgebraicConnectivity; spectralRadius?: SpectralRadius; toughness?: Toughness; integrity?: Integrity; cage?: Cage; moore?: MooreGraph; ramanujan?: Ramanujan; cartesianProduct?: CartesianProduct; tensorProduct?: TensorProduct; strongProduct?: StrongProduct; lexicographicProduct?: LexicographicProduct; minorFree?: MinorFree; topologicalMinorFree?: TopologicalMinorFree; completeBipartite?: CompleteBipartite; eulerian?: Eulerian; kVertexConnected?: KVertexConnected; kEdgeConnected?: KEdgeConnected; wheel?: Wheel; grid?: Grid; toroidal?: Toroidal; star?: Star; comparability?: Comparability; interval?: Interval; permutation?: Permutation; chordal?: Chordal; perfectMatching?: PerfectMatching; kColorable?: KColorable; chromaticNumber?: ChromaticNumber; treewidth?: Treewidth; branchwidth?: Branchwidth; flowNetwork?: FlowNetwork; binaryTree?: BinaryTree; spanningTree?: SpanningTree; tournament?: Tournament; p5Free?: P5Free; c5Free?: C5Free; bullFree?: BullFree; gemFree?: GemFree; atFree?: ATFree; hhFree?: HHFree; distanceHereditary?: DistanceHereditary; circularArc?: CircularArc; properCircularArc?: ProperCircularArc; diskGraphNew?: Disk; probeChordal?: ProbeChordal; probeInterval?: ProbeInterval; pathwidth?: Pathwidth; cliquewidth?: Cliquewidth; modular?: Modular; ptolemaic?: Ptolemaic; quasiLine?: QuasiLine; planarNew?: Planar; }>; /** * Mathematical impossibility in a graph specification. */ export declare interface GraphSpecImpossibility { property: string; reason: string; severity: "error" | "warning"; } /** Helper type for partial specifications */ export declare type GraphSpecPatch = Partial>; /** * Complete validation results for a graph. */ export declare interface GraphValidationResult { properties: PropertyValidationResult_2[]; valid: boolean; errors: string[]; warnings?: string[]; } /** * Greedy graph coloring algorithm. * Assigns colors to vertices sequentially, always using the smallest * available color that doesn't conflict with already-colored neighbors. * * This is an approximation algorithm that uses at most Δ(G) + 1 colors, * where Δ(G) is the maximum degree of the graph. The actual chromatic * number χ(G) may be smaller. * * Time complexity: O(V + E) where V = vertices, E = edges * Space complexity: O(V) for color storage * * @param nodes - Array of graph nodes * @param edges - Array of graph edges * @param directed - Whether the graph is directed * @returns Map of node ID to color (0-indexed) */ export declare const greedyColoring: (nodes: TestNode[], edges: TestEdge[], directed: boolean) => Map; /** Grid/lattice graph property */ export declare type Grid = { kind: "grid"; rows: number; cols: number; } | { kind: "not_grid"; } | { kind: "unconstrained"; }; /** * Configuration for ground truth computation */ export declare interface GroundTruthConfig { /** Type of ground truth to compute */ type: GroundTruthType; /** For combined: weight for degree component (default: 0.5) */ degreeWeight?: number; /** For domain-specific: custom importance function per node */ customImportance?: (nodeId: string) => number; /** PageRank damping factor (default: 0.85) */ dampingFactor?: number; /** Aggregation method: 'mean' or 'sum' (default: 'mean') */ aggregation?: "mean" | "sum" | "geometric-mean"; /** Pre-computed importance values (avoids re-computing for same graph) */ precomputedImportance?: Map; } /** * Result of ground truth computation for a single path */ export declare interface GroundTruthPath { path: Path; score: number; nodeScores: number[]; } /** * Ground truth type identifier */ export declare type GroundTruthType = "degree" | "pagerank" | "combined" | "domain-specific"; /** * Path and Cycle Properties * * Properties related to Hamiltonian paths and cycles. */ /** Hamiltonian cycle property */ export declare type Hamiltonian = { kind: "hamiltonian"; } | { kind: "non_hamiltonian"; } | { kind: "unconstrained"; }; export declare const hasAnyDirectedEdges: (g: AnalyzerGraph) => boolean; export declare const hasAnyUndirectedEdges: (g: AnalyzerGraph) => boolean; /** * Create a predicate that checks if graph matches a partial GraphSpec. * Only checks the axes specified in the expected partial spec. * @param expected * @param policy */ export declare const hasGraphSpec: (expected: Partial, policy?: Partial) => AnalyzerGraphPredicate; /** * Graph Invariants and Spectral Properties * * Numerical invariants, forbidden subgraphs, and spectral properties. */ /** Hereditary class with forbidden induced subgraphs */ export declare type HereditaryClass = { kind: "hereditary_class"; forbidden: readonly string[]; } | { kind: "unconstrained"; }; /** * Extended configuration for heterogeneous graphs. */ export declare interface HeterogeneousPathConfig extends PlantedPathConfig { /** Path template specifying node types along path */ pathTemplate: string[]; /** Entity types in the graph */ entityTypes: string[]; } /** * No induced house or hole */ declare type HHFree = { kind: "hh_free"; } | { kind: "has_house_or_hole"; } | { kind: "unconstrained"; }; /** * Perform hierarchical clustering on a graph. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param options - Configuration options * @param options.linkage - Linkage method: 'single', 'complete', or 'average' (default: 'average') * @returns Result containing dendrogram or error * @example * ```typescript * const graph = new Graph(false); * // ... add nodes and edges ... * * const result = hierarchicalClustering(graph, { linkage: 'average' }); * if (result.ok) { * const { dendrogram } = result.value; * const clusters = dendrogram.getClusters(5); * console.log(`Extracted ${clusters.length} clusters`); * } * ``` */ export declare const hierarchicalClustering: (graph: Graph, options?: { linkage?: LinkageMethod; }) => HierarchicalResult; /** * Error type for hierarchical clustering. */ export declare type HierarchicalError = { type: "EmptyGraph"; message: string; } | { type: "InvalidInput"; message: string; } | { type: "InsufficientNodes"; message: string; required: number; actual: number; } | { type: "InvalidHeight"; message: string; height: number; }; /** * Apply hierarchical layout to graph * @param nodes Graph nodes * @param edges Graph edges * @param options Layout configuration * @returns Positioned nodes with layout coordinates */ export declare const hierarchicalLayout: (nodes: LayoutNode[], edges: LayoutEdge[], options?: HierarchicalLayoutOptions) => HierarchicalLayoutResult; /** * Layout configuration options */ export declare interface HierarchicalLayoutOptions { /** Distance between levels (horizontal) */ levelSpacing?: number; /** Distance between nodes on same level (vertical) */ nodeSpacing?: number; /** Root node ID (if null, selects node with no incoming edges) */ rootNodeId?: string | null; /** Direction of tree growth */ direction?: "horizontal" | "vertical"; } /** * Layout result with positioned nodes */ export declare interface HierarchicalLayoutResult { /** Nodes with their positions */ nodes: HierarchicalPositionedNode[]; /** Maximum depth of the tree */ maxDepth: number; /** Root node ID used */ rootNodeId: string; } /** * Positioned node with layout coordinates */ export declare interface HierarchicalPositionedNode { node: N; x: number; y: number; level: number; } /** * Result type for Hierarchical Clustering. */ export declare type HierarchicalResult = Result<{ dendrogram: Dendrogram; metadata: { algorithm: "hierarchical"; runtime: number; parameters: { linkage: "single" | "complete" | "average"; }; }; }, HierarchicalError>; /** * Holm-Bonferroni method (step-down procedure). * * Less conservative than Bonferroni but still controls FWER. * More powerful than Bonferroni when not all hypotheses are rejected. * * Procedure: * 1. Sort p-values in ascending order * 2. Compare smallest p-value to α/m, next to α/(m-1), etc. * 3. Stop when you find first non-significant p-value * * @param pValues - Array of p-values from multiple tests * @param alpha - Original significance level (default: 0.05) * @returns Adjusted p-values and which tests are significant * * @example * ```typescript * const pValues = [0.001, 0.02, 0.045, 0.08, 0.12]; * const result = holmBonferroni(pValues, 0.05); * console.log(result.significant); // [true, false, false, false, false] * ``` */ export declare const holmBonferroni: (pValues: number[], alpha?: number) => { adjustedPValues: number[]; significant: boolean[]; }; /** * Identify hub nodes (top percentile by degree). * * @param nodeDegrees - Map from node ID to degree * @param percentile - Top percentile to consider as hubs (e.g., 0.1 for top 10%) * @returns Set of hub node IDs */ export declare const identifyHubNodes: (nodeDegrees: Map, percentile?: number) => Set; /** Independence number (α): size of largest independent set */ export declare type IndependenceNumber = { kind: "independence_number"; value: number; } | { kind: "unconstrained"; }; export declare interface InducedSubgraph { /** Nodes in the extracted subgraph */ nodes: N[]; /** Edges in the extracted subgraph (only edges between nodes in this subgraph) */ edges: E[]; } export declare type InferredGraphSpec = Readonly<{ vertexCardinality: ReturnType; vertexIdentity: ReturnType; vertexOrdering: ReturnType; edgeArity: ReturnType; edgeMultiplicity: ReturnType; selfLoops: ReturnType; directionality: ReturnType; weighting: ReturnType; signedness: ReturnType; uncertainty: ReturnType; vertexData: ReturnType; edgeData: ReturnType; schema: ReturnType; connectivity: ReturnType; cycles: ReturnType; degreeConstraint: ReturnType; completeness: ReturnType; partiteness: ReturnType; density: ReturnType; embedding: ReturnType; rooting: ReturnType; temporal: ReturnType; layering: ReturnType; edgeOrdering: ReturnType; ports: ReturnType; observability: ReturnType; operationalSemantics: ReturnType; measureSemantics: ReturnType; scaleFree: ReturnType; smallWorld: ReturnType; communityStructure: ReturnType; hamiltonian: ReturnType; traceable: ReturnType; perfect: ReturnType; split: ReturnType; cograph: ReturnType; threshold: ReturnType; line: ReturnType; clawFree: ReturnType; modular: ReturnType; ptolemaic: ReturnType; quasiLine: ReturnType; p5Free: ReturnType; c5Free: ReturnType; bullFree: ReturnType; gemFree: ReturnType; atFree: ReturnType; hhFree: ReturnType; distanceHereditary: ReturnType; weaklyChordal: ReturnType; circularArc: ReturnType; properCircularArc: ReturnType; probeChordal: ReturnType; probeInterval: ReturnType; planarNew: ReturnType; cubic: ReturnType; specificRegular: ReturnType; stronglyRegular: ReturnType; selfComplementary: ReturnType; vertexTransitive: ReturnType; completeBipartite: ReturnType; }>; /** * Detect communities using the Infomap algorithm. * * Infomap uses information theory to find communities by minimizing the * description length (map equation) of random walks on the network. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param options - Optional configuration * @param options.weightFn - Weight function for edges (default: all edges weight 1.0) * @param options.maxIterations - Maximum iterations for optimization (default: 100) * @param options.numTrials - Number of random trials for greedy search (default: 10) * @param options.seed - Random seed for reproducibility (default: undefined) * @returns Result containing modules with compression ratio * @example * ```typescript * const graph = new Graph(true); * // ... add nodes and edges ... * * const result = infomap(graph); * if (result.ok) { * console.log(`Found ${result.value.modules.length} modules`); * console.log(`Compression ratio: ${result.value.compressionRatio}`); * } * ``` */ export declare const infomap: (graph: Graph, options?: { weightFn?: WeightFunction; maxIterations?: number; numTrials?: number; seed?: number; }) => InfomapResult; /** * Infomap module. * Information-theoretic community based on flow compression. */ export declare interface InfomapModule { /** Module identifier */ id: ModuleId; /** Nodes in this module */ nodes: Set; /** Bits required to describe random walk within module */ descriptionLength: number; /** Steady-state probability of random walk visiting this module */ visitProbability: number; /** initial_description_length / module_description_length (> 1.0 is good) */ compressionRatio: number; } /** * Result type for Infomap clustering. */ export declare type InfomapResult = Result<{ modules: InfomapModule[]; metrics: ClusterMetrics; descriptionLength: number; compressionRatio: number; metadata: { algorithm: "infomap"; runtime: number; iterations: number; parameters: { maxIterations?: number; numTrials?: number; seed?: number; }; }; }, ClusteringError>; /** Integrity: resilience measure based on vertex removal */ export declare type Integrity = { kind: "integrity"; value: number; } | { kind: "unconstrained"; }; /** * Intelligent Delayed Termination (IDT) * * **Novel Contribution**: Two-phase expansion that transitions from degree * prioritisation to MI-guided exploration after overlap detection. * * **Motivation**: Experimental results show that standard expansion methods * (including delayed termination with fixed iterations) achieve 0% salience * coverage. IDT addresses this by using MI-based priority guidance during * the delayed phase to steer exploration toward high-salience regions. * * **Algorithm**: * 1. **Phase 1 (Pre-overlap)**: Standard degree-prioritised expansion * - π(v) = deg(v) [ascending] * - Defers high-degree nodes, explores peripheral routes first * * 2. **Overlap Detection**: Uses Threshold Sharing strategy with Jaccard >= 0.5 * - Jaccard(A,B) = |A ∩ B| / |A ∪ B| * - Transition occurs when any two frontiers achieve sufficient overlap * * 3. **Phase 2 (Post-overlap, Delayed)**: MI-guided degree prioritisation * - π(v) = deg(v) × (1 - estimated_MI(v)) [ascending] * - Continue for exactly `delayIterations` additional iterations * - Terminate when post-overlap iteration count reaches limit * * **MI Estimation**: * - Uses Jaccard similarity between node neighbours and discovered path nodes * - Estimated MI(v) = max over all paths of Jaccard(neighbors(v), nodes(P)) * - Higher Jaccard = node likely appears on high-quality paths * * **Key Differences from RSGE**: * - RSGE: Runs to frontier exhaustion * - IDT: Terminates after N iterations post-overlap * - IDT: Explicitly detects overlap satisfaction condition * * **Complexity**: * - Time: O(E log V + P × D) where E = edges, V = vertices, P = paths, D = avg degree * - Space: O(V + E + P × K) where K = avg path length * * @template T - Node data type */ export declare class IntelligentDelayedTermination { private readonly expander; private readonly seeds; private readonly frontiers; private readonly paths; private readonly sampledEdges; private stats; /** Tracks when each node was first discovered (iteration number) */ private readonly nodeDiscoveryIteration; /** Track which frontier owns each node for O(1) intersection checking */ private readonly nodeToFrontierIndex; /** Track path signatures for O(1) deduplication */ private readonly pathSignatures; /** Cache of node neighbor sets for Jaccard similarity */ private readonly neighborCache; /** Current estimated MI scores for each node */ private readonly estimatedMI; /** Phase tracking: false = degree-only, true = MI-guided */ private saliencePhaseActive; /** Track when overlap was first detected */ private overlapDetectedAt; /** Configuration */ private readonly delayIterations; private readonly overlapThreshold; /** * Create a new intelligent delayed termination expansion. * * @param expander - Graph expander providing neighbour access * @param seeds - Array of seed node IDs (N ≥ 2 required for overlap detection) * @param config - Configuration for delay iterations and overlap threshold * @throws Error if fewer than 2 seeds provided */ constructor(expander: GraphExpander, seeds: readonly string[], config?: IntelligentDelayedTerminationConfig); /** * Run the expansion with intelligent delayed termination. * * Terminates when: * - Pre-overlap: All frontiers exhausted (standard termination) * - Post-overlap: `delayIterations` additional iterations completed * * @returns Expansion results including paths and sampled subgraph */ run(): Promise; /* Excluded from this release type: detectOverlap */ /* Excluded from this release type: calculateJaccardSimilarity */ /* Excluded from this release type: shouldTerminate */ /* Excluded from this release type: calculateNodePriority */ /* Excluded from this release type: transitionToSaliencePhase */ /* Excluded from this release type: updateMIEstimates */ /* Excluded from this release type: computeJaccardSimilarity */ /* Excluded from this release type: hasNonEmptyFrontier */ /* Excluded from this release type: selectLowestPriorityFrontier */ /* Excluded from this release type: peekPriority */ /* Excluded from this release type: reconstructPath */ /* Excluded from this release type: createPathSignature */ /* Excluded from this release type: recordDegree */ /* Excluded from this release type: getDegreeBucket */ } /** * Configuration for Intelligent Delayed Termination. */ export declare interface IntelligentDelayedTerminationConfig { /** * Number of additional iterations to continue after overlap is detected. * Default: 50 */ delayIterations?: number; /** * Jaccard similarity threshold to consider frontiers as overlapping. * Range: [0, 1] where 0 = no overlap, 1 = identical sets * Default: 0.5 (50% overlap) */ overlapThreshold?: number; } /** Interval graph property (intersection of intervals) */ export declare type Interval = { kind: "interval"; } | { kind: "not_interval"; } | { kind: "unconstrained"; }; /** * Invalid filter error (malformed filter specification). */ export declare type InvalidFilterError = { type: "invalid-filter"; message: string; filter: unknown; }; /** * Invalid input error (null, undefined, or malformed input). */ export declare type InvalidInputError = { type: "invalid-input"; message: string; input?: unknown; }; declare interface InvalidInputError_2 { type: "invalid-input"; message: string; } declare interface InvalidInputError_3 { type: "invalid-input"; message: string; } /** * Invalid radius error (negative or non-integer radius). */ export declare type InvalidRadiusError = { type: "invalid-radius"; message: string; radius: number; }; /** * Invalid truss value error (k < 2). */ export declare type InvalidTrussError = { type: "invalid-truss"; message: string; k: number; }; /** * Invalid weight error (non-numeric, NaN, or Infinity). */ export declare type InvalidWeightError = { type: "invalid-weight"; message: string; weight: unknown; edgeId: string; }; /** * Type guard for acyclic graphs * @param spec */ export declare const isAcyclic: (spec: GraphSpec_2) => spec is GraphSpec_2 & { cycles: { kind: "acyclic"; }; }; export declare const isAcyclicDirectedBinary: (g: AnalyzerGraph) => boolean; /** * Check if graph is bipartite. * Uses direct bipartite check instead of full spec computation for performance. * @param g */ export declare const isBipartite: (g: AnalyzerGraph) => boolean; export declare const isBipartiteUndirectedBinary: (g: AnalyzerGraph) => boolean; /** * Check if graph is chordal (every cycle of length >= 4 has a chord). * Equivalent to having a perfect elimination ordering. * Uses Maximum Cardinality Search (MCS) algorithm. * @param g */ export declare const isChordal: (g: AnalyzerGraph) => boolean; /** * Check if an undirected binary graph is chordal using Maximum Cardinality Search. * A graph is chordal if every cycle of length >= 4 has a chord (equivalent to having a PEO). * @param g - Graph to check * @returns True if graph is chordal */ export declare const isChordalUndirectedBinary: (g: AnalyzerGraph) => boolean; /** * Check if graph is claw-free (no K1,3 induced subgraph). * @param g */ export declare const isClawFree: (g: AnalyzerGraph) => boolean; /** * Check if graph is a cograph (P4-free, no induced path on 4 vertices). * Uses direct computation instead of full spec computation for performance. * @param g */ export declare const isCograph: (g: AnalyzerGraph) => boolean; /** * Check if graph is a comparability graph (has transitive orientation). * Comparability graphs represent partial orders. * @param g */ export declare const isComparability: (g: AnalyzerGraph) => boolean; /** * Check if graph is complete. * @param g */ export declare const isComplete: (g: AnalyzerGraph) => boolean; /** * Check if graph is complete bipartite K_{m,n}. * @param g */ export declare const isCompleteBipartite: (g: AnalyzerGraph) => boolean; /** * Type guard for connected graphs * @param spec */ export declare const isConnected: (spec: GraphSpec_2) => spec is GraphSpec_2 & { connectivity: { kind: "connected"; }; }; export declare const isConnectedUndirectedBinary: (g: AnalyzerGraph) => boolean; /** * Check if graph is cubic (3-regular). * @param g */ export declare const isCubic: (g: AnalyzerGraph) => boolean; /** * Check if graph is a DAG (directed, acyclic). * * Optimised O(V+E) implementation that avoids computing the full graph spec. * Uses Kahn's algorithm for cycle detection. * * @param g - Graph to check * @returns true if graph is a DAG */ export declare const isDAG: (g: AnalyzerGraph) => boolean; /** * Check if graph is dense (density > 75%). * @param g */ export declare const isDense: (g: AnalyzerGraph) => boolean; /** * Type guard for directed graphs * @param spec */ export declare const isDirected: (spec: GraphSpec_2) => spec is GraphSpec_2 & { directionality: { kind: "directed"; }; }; /** * Check if graph is Eulerian (all vertices have even degree). * For undirected graphs, this means an Eulerian circuit exists. * For directed graphs, checks if strongly connected with equal in/out degrees. * @param g */ export declare const isEulerian: (g: AnalyzerGraph) => boolean; /** * Check if graph is a forest (undirected, acyclic). * * Optimised O(V+E) implementation that avoids computing the full graph spec. * A forest must be: * - All edges undirected * - Simple (no multi-edges) * - No self-loops * - Acyclic (E < V for undirected graph) * * @param g - Graph to check * @returns true if graph is a forest */ export declare const isForest: (g: AnalyzerGraph) => boolean; /** * Check if graph is connected (runtime check for AnalyzerGraph). * Note: Different from graph-spec.isConnected which is a type guard for GraphSpec. * @param g */ export declare const isGraphConnected: (g: AnalyzerGraph) => boolean; /** * Check if a graph spec combination is mathematically impossible. * @param spec */ export declare const isGraphSpecImpossible: (spec: GraphSpec_2) => boolean; /** * Check if graph is Hamiltonian (has cycle visiting every vertex exactly once). * NP-complete to determine, so this is conservative for graphs with n > 10. * @param g */ export declare const isHamiltonian: (g: AnalyzerGraph) => boolean; /** * Type guard for heterogeneous graphs * @param spec */ export declare const isHeterogeneous: (spec: GraphSpec_2) => spec is GraphSpec_2 & { schema: { kind: "heterogeneous"; }; }; /** * Check if graph is an interval graph. * Interval graphs are chordal and can be represented as intersection of intervals. * @param g */ export declare const isInterval: (g: AnalyzerGraph) => boolean; /** * Check if graph is k-regular for a specific k. * @param k */ export declare const isKRegular: (k: number) => (g: AnalyzerGraph) => boolean; /** * Check if graph is a line graph (represents edge adjacencies of another graph). * @param g */ export declare const isLineGraph: (g: AnalyzerGraph) => boolean; /** * Check if graph has modular community structure. * @param g */ export declare const isModular: (g: AnalyzerGraph) => boolean; /** * Type guard for multigraphs * @param spec */ export declare const isMultigraph: (spec: GraphSpec_2) => spec is GraphSpec_2 & { edgeMultiplicity: { kind: "multi"; }; }; /** * Check if graph is perfect (ω(H) = χ(H) for all induced subgraphs H). * Perfect graphs have no odd holes or odd anti-holes. * Uses sufficient conditions: bipartite graphs and chordal graphs are perfect. * @param g */ export declare const isPerfect: (g: AnalyzerGraph) => boolean; /** * Check if graph is a permutation graph. * Permutation graphs are both comparability graphs and their complements are too. * @param g */ export declare const isPermutation: (g: AnalyzerGraph) => boolean; /** * Check if graph is planar (can be drawn without edge crossings). * Uses Euler's formula heuristics: E <= 3V - 6 for simple graphs. * For bipartite planar graphs: E <= 2V - 4. * Note: This is a necessary but not sufficient condition. * @param g */ export declare const isPlanar: (g: AnalyzerGraph) => boolean; /** * Check if graph is regular (all vertices have same degree). * @param g */ export declare const isRegular: (g: AnalyzerGraph) => boolean; /** * Check if graph is scale-free (power-law degree distribution). * @param g */ export declare const isScaleFree: (g: AnalyzerGraph) => boolean; /** * Check if graph is self-complementary (isomorphic to its complement). * @param g */ export declare const isSelfComplementary: (g: AnalyzerGraph) => boolean; /** * Check if graph has small-world property (high clustering + short paths). * @param g */ export declare const isSmallWorld: (g: AnalyzerGraph) => boolean; /** * Check if graph is sparse (density <= 10%). * @param g */ export declare const isSparse: (g: AnalyzerGraph) => boolean; /** * Check if graph is a split graph (partition into clique + independent set). * Uses direct computation instead of full spec computation for performance. * @param g */ export declare const isSplit: (g: AnalyzerGraph) => boolean; /** * Check if graph is a star (one central vertex connected to all others). * @param g */ export declare const isStar: (g: AnalyzerGraph) => boolean; /** * Check if graph is strongly regular (n,k,λ,μ) parameters. * @param g */ export declare const isStronglyRegular: (g: AnalyzerGraph) => boolean; /** * Check if graph is a threshold graph (both split and cograph). * @param g */ export declare const isThreshold: (g: AnalyzerGraph) => boolean; /** * Check if graph is traceable (has path visiting every vertex exactly once). * NP-complete to determine, so this is conservative for graphs with n > 10. * @param g */ export declare const isTraceable: (g: AnalyzerGraph) => boolean; /** * Check if graph is a tree (undirected, acyclic, connected). * * Optimised O(V+E) implementation that avoids computing the full graph spec. * A tree must be: * - All edges undirected * - Simple (no multi-edges) * - No self-loops * - Connected * - Acyclic (for connected undirected graph: E = V - 1) * * @param g - Graph to check * @returns true if graph is a tree */ export declare const isTree: (g: AnalyzerGraph) => boolean; /** * Check if graph is a unit disk graph. * Requires vertices to have position attributes ({x, y}). * Graph is unit disk if edges exist exactly when distance <= threshold. * @param g */ export declare const isUnitDisk: (g: AnalyzerGraph) => boolean; /** * Validate that a GraphSpec doesn't contain contradictory properties. * @param spec */ export declare const isValidSpec: (spec: GraphSpec_2) => boolean; /** * Check if graph is vertex-transitive (all vertices equivalent under automorphisms). * GI-hard to determine, so this is conservative for graphs with n > 6. * @param g */ export declare const isVertexTransitive: (g: AnalyzerGraph) => boolean; /** * Type guard for weighted graphs * @param spec */ export declare const isWeighted: (spec: GraphSpec_2) => spec is GraphSpec_2 & { weighting: { kind: "weighted_numeric"; }; }; /** * Compute Jaccard distance between two sets. * Jaccard distance = 1 - Jaccard similarity = 1 - |A ∩ B| / |A ∪ B| * * @param setA - First set * @param setB - Second set * @returns Distance in [0, 1] where 0 = identical, 1 = completely disjoint */ export declare const jaccardDistance: (setA: Set, setB: Set) => number; /** * Compute Jensen-Shannon divergence (symmetric version of KL). * * JS(P, Q) = 0.5 * KL(P || M) + 0.5 * KL(Q || M) * where M = 0.5 * (P + Q) * * @param p - First distribution * @param q - Second distribution * @returns JS divergence in [0, log(2)] ≈ [0, 0.693] */ export declare const jsDivergence: (p: Map, q: Map) => number; /** * Zachary's Karate Club network. * * Classic social network of a university karate club. * Nodes are members, edges represent friendships outside the club. */ export declare const KARATE: BenchmarkDatasetMeta; /** k-colorable property */ export declare type KColorable = { kind: "k_colorable"; k: number; } | { kind: "bipartite_colorable"; } | { kind: "unconstrained"; }; /** * K-Core Decomposition using Batagelj-Zaversnik algorithm. * * Computes the core number for each node and extracts all k-cores from k=1 to degeneracy. * Core number = highest k such that node belongs to k-core. * * Algorithm: * 1. Compute initial degrees for all nodes * 2. Sort nodes by degree (using bin sort for O(n) complexity) * 3. Process nodes in degree order, removing each and updating neighbors * 4. Track core number when node is removed (= current degree at removal time) * 5. Construct nested k-core hierarchy from core numbers * @param graph - Input graph (directed or undirected) * @returns Result containing cores map, degeneracy, and core numbers * @example * ```typescript * const result = kCoreDecomposition(graph); * if (result.ok) { * const { cores, degeneracy, coreNumbers } = result.value; * console.log(`Graph degeneracy: ${degeneracy}`); * const core3 = cores.get(3); * if (core3) { * console.log(`3-core has ${core3.size} nodes`); * } * } * ``` */ export declare const kCoreDecomposition: (graph: Graph) => KCoreResult; /** * Result type for K-Core Decomposition. */ export declare type KCoreResult = Result<{ cores: Map>; degeneracy: number; coreNumbers: Map; metadata: { algorithm: "k-core"; runtime: number; }; }, DecompositionError>; /** k-edge-connected property (cannot disconnect by removing < k edges) */ export declare type KEdgeConnected = { kind: "k_edge_connected"; k: number; } | { kind: "unconstrained"; }; /** * Kendall's tau rank correlation. * Counts concordant vs discordant pairs. * * @param predicted - Predicted ranking * @param groundTruth - Ground truth ranking * @returns τ ∈ [-1, 1] */ export declare const kendallTau: (predicted: string[], groundTruth: string[]) => number; /** * Compute KL divergence between two distributions. * * KL(P || Q) = Σ P(x) * log(P(x) / Q(x)) * * Uses Laplace smoothing to handle zero probabilities. * * @param p - True distribution (what we want to approximate) * @param q - Approximate distribution (what we sampled) * @param smoothing - Laplace smoothing constant (default: 1e-10) * @returns KL divergence (non-negative, 0 = identical distributions) */ export declare const klDivergence: (p: Map, q: Map, smoothing?: number) => number; /** * Options for k-truss extraction */ declare interface KTrussOptions { /** Minimum triangle support (k) for edges to be included */ k: number; /** Whether to return all k-trusses up to max k */ returnHierarchy?: boolean; } /** k-vertex-connected property (cannot disconnect by removing < k vertices) */ export declare type KVertexConnected = { kind: "k_vertex_connected"; k: number; } | { kind: "unconstrained"; }; /** * Label propagation cluster. * Fast clustering result from asynchronous label propagation. */ export declare interface LabelCluster { /** Cluster label (inherited from seed node or converged label) */ label: ClusterId; /** Nodes with this label */ nodes: Set; /** Cluster size */ size: number; /** Number of iterations until convergence (or max iterations) */ iterations: number; /** True if converged, false if hit max iterations */ stable: boolean; } /** * Label Propagation clustering algorithm. * * Fast semi-supervised clustering algorithm that propagates labels through * the network based on neighbor voting. Nodes iteratively adopt the most * frequent label among their neighbors. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param options - Optional configuration * @param options.weightFn - Weight function for edges (default: all edges weight 1.0) * @param options.maxIterations - Maximum iterations (default: 100) * @param options.seed - Random seed for reproducibility (default: Date.now()) * @returns Result containing clusters or error * @example * ```typescript * const graph = new Graph(true); * // ... add nodes and edges ... * * const result = labelPropagation(graph); * if (result.ok) { * console.log(`Found ${result.value.clusters.length} clusters`); * console.log(`Converged: ${result.value.metadata.converged}`); * console.log(`Iterations: ${result.value.metadata.iterations}`); * } * ``` */ export declare const labelPropagation: (graph: Graph, options?: { weightFn?: WeightFunction; maxIterations?: number; seed?: number; }) => LabelPropagationResult; /** * Result type for Label Propagation clustering. */ export declare type LabelPropagationResult = Result<{ clusters: LabelCluster[]; metadata: { algorithm: "label-propagation"; runtime: number; converged: boolean; iterations: number; parameters: { maxIterations?: number; seed?: number; }; }; }, ClusteringError>; /** Layering (multiplex networks, etc.) */ export declare type Layering = { kind: "single_layer"; } | { kind: "multi_layer"; } | { kind: "multiplex"; } | { kind: "interdependent"; }; /** * Generic edge interface for graph layout algorithms. * * Used by layout algorithms for edge routing and positioning. * * @template T - Additional properties for the edge */ export declare interface LayoutEdge { /** Source node ID */ source: string; /** Target node ID */ target: string; /** Edge type/label */ type?: string; /** Edge weight for weighted algorithms */ weight?: number; /** Additional edge properties */ [key: string]: unknown; } /** * Generic node interface for graph layout algorithms. * * Used by layout algorithms that position nodes in 2D space. * * @template T - Additional properties for the node */ export declare interface LayoutNode { /** Unique identifier for the node */ id: string; /** X coordinate for graph positioning */ x: number; /** Y coordinate for graph positioning */ y: number; /** Additional node properties */ [key: string]: unknown; } /** * Detect communities using the Leiden algorithm. * * The Leiden algorithm improves upon Louvain by adding a refinement phase that * guarantees all detected communities are connected subgraphs. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param options - Optional configuration * @param options.weightFn - Weight function for edges (default: all edges weight 1.0) * @param options.resolution - Resolution parameter (default: 1.0, higher values favor more communities) * @param options.maxIterations - Maximum iterations per phase (default: 100) * @returns Result with array of detected Leiden communities * @example * ```typescript * const graph = new Graph(true); * // ... add nodes and edges ... * * const result = leiden(graph); * if (result.ok) { * console.log(`Found ${result.value.communities.length} communities`); * result.value.communities.forEach((community) => { * console.log(`Community ${community.id}: ${community.nodes.size} nodes, connected: ${community.isConnected}`); * }); * } * ``` */ export declare const leiden: (graph: Graph, options?: { weightFn?: WeightFunction; resolution?: number; maxIterations?: number; }) => Result<{ communities: LeidenCommunity[]; metrics: ClusterMetrics; metadata: { algorithm: "leiden"; runtime: number; iterations: number; parameters: { resolution?: number; maxIterations?: number; }; }; }, ClusteringError>; /** * Leiden clustering community. * Enhanced community structure with connectivity guarantee. */ export declare interface LeidenCommunity { /** Community identifier */ id: CommunityId; /** Nodes in this Leiden community */ nodes: Set; /** Modularity contribution */ modularity: number; /** Connectivity guarantee (always true for Leiden) */ isConnected: boolean; /** Edges within community */ internalEdges: number; /** Boundary quality metric (lower is better) */ conductance: number; } /** * Result type for Leiden clustering algorithm. */ export declare type LeidenResult = Result<{ communities: LeidenCommunity[]; metrics: ClusterMetrics; metadata: { algorithm: "leiden"; runtime: number; iterations: number; parameters: { resolution?: number; maxIterations?: number; }; }; }, ClusteringError>; /** * Les Misérables character co-appearance network. * * Characters from Victor Hugo's novel connected by co-appearance. * Nodes are characters, edges weighted by number of co-appearances. */ export declare const LESMIS: BenchmarkDatasetMeta; /** Lexicographic product G ∘ H */ export declare type LexicographicProduct = { kind: "lexicographic_product"; leftFactors: number; rightFactors: number; } | { kind: "not_lexicographic_product"; } | { kind: "unconstrained"; }; /** Line graph property */ export declare type Line = { kind: "line_graph"; } | { kind: "non_line_graph"; } | { kind: "unconstrained"; }; /** * Linkage method for computing cluster-to-cluster distances. */ declare type LinkageMethod = "single" | "complete" | "average"; /** * Load all benchmark datasets. * * @param benchmarksRoot - Optional root directory for benchmarks * @returns Map of dataset ID to loaded benchmark */ export declare const loadAllBenchmarks: (benchmarksRoot?: string) => Promise>; /** * Load a benchmark dataset. * * Uses remote URL with caching if configured, otherwise loads from local file. * * @param meta - Dataset metadata * @param benchmarksRoot - Optional root directory for benchmarks (only used if no remoteUrl) * @returns Loaded benchmark with graph and metadata * @throws Error if file not found or parsing fails */ export declare const loadBenchmark: (meta: BenchmarkDatasetMeta, benchmarksRoot?: string) => Promise; /** * Load a benchmark dataset by ID. * * @param id - Dataset identifier (e.g., 'cora', 'citeseer', 'facebook') * @param benchmarksRoot - Optional root directory for benchmarks * @returns Loaded benchmark with graph and metadata * @throws Error if dataset ID not found */ export declare const loadBenchmarkById: (id: string, benchmarksRoot?: string) => Promise; /** * A loaded benchmark dataset with graph and metadata. */ export declare interface LoadedBenchmark { /** The loaded graph */ graph: Graph; /** Dataset metadata */ meta: BenchmarkDatasetMeta; /** Actual node count after loading */ nodeCount: number; /** Actual edge count after loading */ edgeCount: number; /** Actual content size in bytes */ contentSize: number; } /** * Generic edge type for loaded graphs */ export declare interface LoadedEdge extends Edge { id: string; type: string; source: string; target: string; weight?: number; relation?: string; } /** * Load a graph from edge list format * * Edge list format: one edge per line * - Simple: "node1 node2" * - Weighted: "node1 node2 weight" * * @param content - File content as string * @param config - Loading configuration * @returns Loaded graph with metadata */ export declare const loadEdgeList: (content: string, config?: EdgeListConfig) => LoadResult; /** * Generic node type for loaded graphs */ export declare interface LoadedNode extends Node_2 { id: string; type: string; label?: string; attributes?: Record; } /** * Load a graph from file content with auto-detection * * Attempts to detect format based on content structure: * - 3 columns with relation-like middle field → triples * - 2-3 columns with numeric third field → weighted edge list * - 2 columns → edge list * * @param content - File content as string * @param hint - Optional format hint ('edge-list' | 'triples') * @returns Loaded graph with metadata */ export declare const loadGraph: (content: string, hint?: "edge-list" | "triples" | "weighted-edge-list") => LoadResult; /** * Load graph from a URL (for downloading benchmark datasets) * * @param url - URL to fetch graph data from * @param hint - Optional format hint * @returns Promise resolving to loaded graph with metadata */ export declare const loadGraphFromUrl: (url: string, hint?: "edge-list" | "triples" | "weighted-edge-list") => Promise; /** * Result of graph loading operation */ export declare interface LoadResult { graph: Graph; nodeCount: number; edgeCount: number; nodeTypes: Set; edgeTypes: Set; warnings: string[]; } /** * Load a knowledge graph from triple format * * Triple format: one triple per line * - Standard: "head\trelation\ttail" * * Creates a heterogeneous graph where: * - Nodes are entities (head/tail) * - Edges have relation types * * @param content - File content as string * @param config - Loading configuration * @returns Loaded graph with metadata */ export declare const loadTriples: (content: string, config?: TripleConfig) => LoadResult; /** * Configuration for Louvain algorithm optimization. * @remarks * All fields are optional. If not provided, adaptive defaults are used based on graph size. */ export declare interface LouvainConfiguration { /** * Resolution parameter for modularity calculation. * @remarks * Controls community size detection: * - Values > 1.0: Favor smaller, more granular communities * - Value = 1.0 (default): Standard Newman-Girvan modularity * - Values < 1.0: Favor larger, coarser communities * * Higher resolution = more communities detected * Lower resolution = fewer communities detected * @default 1.0 */ resolution?: number; /** * Neighbor selection strategy. * @remarks * **UPDATE (Phase 4)**: Auto mode now always selects "best" mode. * Random mode caused quality degradation (Q: 0.37 → 0.05) and slower convergence * (103 → 201 iterations) for citation networks. * * - `"auto"` (default): Best-neighbor mode for all graphs (Phase 4 update) * - `"best"`: Always evaluate all neighbors, select maximum ΔQ (quality-first) * - `"random"`: Accept first neighbor with positive ΔQ (not recommended) * @default "auto" */ mode?: "auto" | "best" | "random"; /** * Random seed for deterministic neighbor shuffling. * @remarks * If provided, enables reproducible test results by seeding the PRNG. * If undefined, uses Math.random() (non-deterministic). * * Used for: * - Neighbor order randomization (Fisher-Yates shuffle) * - Tie-breaking in modularity optimization */ seed?: number; /** * Modularity convergence threshold override. * @remarks * Adaptive default (if undefined): * - 1e-5 for graphs >500 nodes (looser, faster) * - 1e-6 for graphs ≤500 nodes (stricter, higher quality) * * Stops iteration when ΔQ < threshold: * - Lower values = stricter convergence, higher quality, slower performance * - Higher values = looser convergence, lower quality, faster performance * @default Adaptive (1e-5 or 1e-6 based on graph size) */ minModularityIncrease?: number; /** * Maximum iterations per hierarchy level override. * @remarks * Adaptive default (if undefined): * - 20 iterations for first hierarchy level (level 0) with >200 nodes * - 40 iterations for graphs with 100-200 nodes * - 50 iterations for graphs with <100 nodes * * Prevents infinite loops while allowing convergence: * - Lower values = faster but may not fully converge * - Higher values = more thorough but slower * * Most node movements occur in first few iterations, so lower limits * are effective for large graphs. * @default Adaptive (20, 40, or 50 based on graph size and level) */ maxIterations?: number; } /** * Result of Louvain community detection including performance statistics. */ export declare interface LouvainResult { /** Detected communities */ communities: Community[]; /** Performance and convergence statistics */ stats: { /** Total iterations across all hierarchy levels */ totalIterations: number; /** Number of hierarchy levels processed */ hierarchyLevels: number; /** Runtime in milliseconds */ runtimeMs: number; }; } /** * Create a GraphSpec from defaults + overrides. * Provides type-safe property composition. * @param patch */ export declare const makeGraphSpec: (patch?: GraphSpecPatch) => GraphSpec_2; /** * Mean Average Precision. * Average of precision at each relevant item position. * * @param predicted - Predicted ranking (item IDs) * @param relevantItems - Set of relevant item IDs * @returns MAP ∈ [0, 1] */ export declare const meanAveragePrecision: (predicted: string[], relevantItems: Set) => number; /** * Compute path diversity using edge overlap. * * Converts paths to edge sets and computes Jaccard distance. * This is more sensitive than node-based diversity because * paths can share nodes but use different edges. * * @param paths - Array of paths, where each path is an array of node IDs * @returns Mean pairwise edge-based Jaccard distance in [0, 1] */ export declare const meanPairwiseEdgeJaccardDistance: (paths: string[][]) => number; /** * Compute mean pairwise Jaccard distance between paths. * * This measures how different the paths are from each other on average. * Higher values indicate more diverse path exploration. * * @param paths - Array of paths, where each path is an array of node IDs * @returns Mean pairwise Jaccard distance in [0, 1] */ export declare const meanPairwiseJaccardDistance: (paths: string[][]) => number; /** * Mean Reciprocal Rank. * Reciprocal of rank of first relevant item. * * @param predicted - Predicted ranking (item IDs) * @param relevantItems - Set of relevant item IDs * @returns MRR ∈ [0, 1] */ export declare const meanReciprocalRank: (predicted: string[], relevantItems: Set) => number; /** Measure semantics (cost, utility, etc.) */ export declare type MeasureSemantics = { kind: "none"; } | { kind: "metric"; } | { kind: "cost"; } | { kind: "utility"; }; /** * Merge step in hierarchical clustering dendrogram. * Represents joining two clusters at a specific distance/height. */ export declare interface MergeStep { /** Index of first cluster being merged (< 0 for leaves) */ cluster1: number; /** Index of second cluster being merged (< 0 for leaves) */ cluster2: number; /** Distance/dissimilarity between clusters */ distance: number; /** Size of resulting merged cluster */ size: number; } /** * Comparison between methods. */ export declare interface MethodComparison { method: string; results: MetricResults; runtime: number; } /** * Method configuration for comparison experiments. */ export declare interface MethodConfig { /** Unique name for this method */ name: string; /** Path ranking function */ ranker: PathRanker; /** Optional parameters for the ranker */ params?: Record; } /** * Flexible metric results storage. * Used by experiment runner for dynamic metric collection. */ export declare type MetricResults = Record; /** * Available evaluation metrics. */ export declare type MetricType = "spearman" | "kendall" | "ndcg" | "map" | "mrr" | "precision" | "recall"; /** * Min-Heap based priority queue implementation. * * Provides O(log n) insert and extractMin operations, * and O(log n) decreaseKey with element tracking. * * Time Complexity: * - insert: O(log n) * - extractMin: O(log n) * - decreaseKey: O(log n) * - isEmpty: O(1) * - size: O(1) * * Space Complexity: O(n) for heap array and position map * @template T - Type of elements stored in the queue * @example * ```typescript * const heap = new MinHeap(); * heap.insert('task1', 10); * heap.insert('task2', 5); * heap.insert('task3', 15); * * const min = heap.extractMin(); // Some('task2') - priority 5 * ``` */ export declare class MinHeap { private heap; private positions; /** * Insert an element with given priority. * @param element - Element to insert * @param priority - Priority value (lower = higher priority) */ insert(element: T, priority: number): void; /** * Extract and return the element with minimum priority. * @returns Option containing the minimum element, or None if heap is empty */ extractMin(): Option_2; /** * Decrease the priority of an existing element. * @param element - Element whose priority to decrease * @param newPriority - New priority value (must be lower than current) * @returns Result indicating success or error */ decreaseKey(element: T, newPriority: number): Result; /** * Check if the heap is empty. * @returns true if heap contains no elements */ isEmpty(): boolean; /** * Get the number of elements in the heap. * @returns Number of elements */ size(): number; /* Excluded from this release type: extractMinBatch */ /* Excluded from this release type: bubbleUp */ /* Excluded from this release type: bubbleDown */ /* Excluded from this release type: swap */ } /** Minor-free: excludes specific graph minors (Kuratowski-Wagner theorem) */ export declare type MinorFree = { kind: "minor_free"; forbiddenMinors: string[]; } | { kind: "not_minor_free"; } | { kind: "unconstrained"; }; /** * perfect_variants Graph Class Type Definitions * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.827Z */ /** * Every module is trivial */ declare type Modular = { kind: "modular"; } | { kind: "not_modular"; } | { kind: "unconstrained"; }; /** * Modularity score * Range: [-0.5, 1.0], higher is better */ export declare type Modularity = number; /** * Module identifier for Infomap */ export declare type ModuleId = number; /** Moore graph: maximum vertices for given (diameter, degree) bound */ export declare type MooreGraph = { kind: "moore"; diameter: number; degree: number; } | { kind: "not_moore"; } | { kind: "unconstrained"; }; /** * Parsed Matrix Market document. */ export declare interface MtxDocument { /** Number of rows */ rows: number; /** Number of columns */ cols: number; /** Number of non-zero entries */ nnz: number; /** Value type (real, integer, complex, pattern) */ valueType: MtxValueType; /** Symmetry (general, symmetric, skew-symmetric, hermitian) */ symmetry: MtxSymmetry; /** Edges as (row, col, value?) triples (1-indexed) */ entries: MtxEntry[]; /** Comment lines from the header */ comments: string[]; /** Node labels from auxiliary _nodename.txt file */ nodeLabels?: string[]; } /** * A single Matrix Market entry. */ export declare interface MtxEntry { /** Row index (1-indexed) */ row: number; /** Column index (1-indexed) */ col: number; /** Value (undefined for pattern matrices) */ value?: number; } /** * Matrix Market symmetry type. */ export declare type MtxSymmetry = "general" | "symmetric" | "skew-symmetric" | "hermitian"; /** * Convert a parsed Matrix Market document to normalised JSON format. * * Directed detection: symmetric matrices are undirected; general matrices * are directed unless overridden. * * @param document - Parsed Matrix Market document * @param options - Conversion options * @returns Graph in normalised JSON format */ export declare const mtxToJson: (document: MtxDocument, options: MtxToJsonOptions) => GraphJson; /** * Options for converting Matrix Market to JSON. */ export declare interface MtxToJsonOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection */ directed?: boolean; /** Node labels from auxiliary file */ nodeLabels?: string[]; } /** * Type definitions for Matrix Market (.mtx) format. * * Matrix Market is a standard format for exchanging sparse matrices, * commonly used by the SuiteSparse Matrix Collection. */ /** * Matrix Market value type. */ export declare type MtxValueType = "real" | "integer" | "complex" | "pattern"; /** * Pre-computed mutual information cache for a graph. * Stores MI values keyed by edge ID for O(1) lookup during path ranking. */ export declare interface MutualInformationCache { /** * Get the MI value for an edge. * @param edgeId - The edge identifier * @returns MI value, or undefined if not cached */ get(edgeId: string): number | undefined; /** * Get all cached edge IDs. */ keys(): IterableIterator; /** * Number of cached entries. */ readonly size: number; } /** * Mutual information computation for graph edges. * * Provides multiple computation strategies that automatically adapt to graph properties: * 1. **Attribute-based**: When nodes have attributes, computes MI from attribute correlation * 2. **Node type-based**: For heterogeneous node types, computes MI from type co-occurrence rarity * 3. **Edge type-based**: For heterogeneous edge types, computes MI from edge type rarity * 4. **Structural**: Falls back to Jaccard similarity of neighbourhoods * * Additional modifiers that multiply the base MI: * - **Temporal**: Edge stability/recency modifier * - **Signed**: Positive/negative edge modifier * - **Probabilistic**: Edge probability modifier * - **Community**: Same-community boost modifier * - **Multiplex**: Aggregates MI across layers * - **Hypergraph**: Handles hyperedges connecting multiple nodes * * @module pathfinding/mutual-information */ /** * Configuration for mutual information computation. * @template N - Node type extending base Node * @template E - Edge type extending base Edge */ export declare interface MutualInformationConfig { /** * Extract numeric attributes from a node for MI computation. * If not provided, structural similarity is used. * @param node - The node to extract attributes from * @returns Array of numeric attribute values, or undefined if no attributes */ attributeExtractor?: (node: N) => number[] | undefined; /** * Extract community/cluster identifier from a node. * Edges within the same community get boosted MI. * @param node - The node to extract community from * @returns Community identifier, or undefined if not clustered */ communityExtractor?: (node: N) => string | number | undefined; /** * Extract layer identifier from an edge for multiplex graphs. * MI is aggregated across layers using geometric mean. * @param edge - The edge to extract layer from * @returns Layer identifier, or undefined if single-layer */ layerExtractor?: (edge: E) => string | number | undefined; /** * Extract timestamp from an edge for temporal graphs. * More recent edges get higher MI via temporal decay. * @param edge - The edge to extract timestamp from * @returns Unix timestamp, or undefined if static */ timestampExtractor?: (edge: E) => number | undefined; /** * Extract sign from an edge for signed graphs. * Negative edges get penalized MI. * @param edge - The edge to extract sign from * @returns Sign value (positive > 0, negative < 0), or undefined if unsigned */ signExtractor?: (edge: E) => number | undefined; /** * Extract probability from an edge for probabilistic graphs. * MI is multiplied by edge probability. * @param edge - The edge to extract probability from * @returns Probability in [0, 1], or undefined if deterministic */ probabilityExtractor?: (edge: E) => number | undefined; /** * Extract hyperedge node IDs for hypergraph edges. * Returns all nodes connected by this hyperedge (beyond source/target). * @param edge - The edge to extract hyperedge nodes from * @returns Array of additional node IDs, or undefined if simple edge */ hyperedgeExtractor?: (edge: E) => string[] | undefined; /** * Whether to use edge types for MI computation in heterogeneous edge graphs. * @default false (auto-detected) */ useEdgeTypes?: boolean; /** * Boost factor for edges within the same community. * MI is multiplied by (1 + communityBoost) for same-community edges. * @default 0.5 */ communityBoost?: number; /** * Penalty factor for negative edges in signed graphs. * Negative edges have MI multiplied by (1 - negativePenalty). * @default 0.5 */ negativePenalty?: number; /** * Decay rate for temporal MI modifier. * MI_temporal = exp(-temporalDecay * age) where age is time since referenceTime. * @default 0.001 */ temporalDecay?: number; /** * Reference time for temporal decay computation (Unix timestamp). * @default Date.now() */ referenceTime?: number; /** * Small constant added to avoid log(0). * @default 1e-10 */ epsilon?: number; /** * Enable degree-based penalty to reduce MI for high-degree nodes (hubs). * Penalizes edges connected to nodes with many connections. * @default false */ useDegreeBasedPenalty?: boolean; /** * Penalty factor for degree-based MI reduction. * MI_adjusted = MI_base × exp(-degreeBasedPenaltyFactor × (log(deg(u)+1) + log(deg(v)+1))) * Higher values = stronger penalty for high-degree nodes. * @default 0.5 */ degreeBasedPenaltyFactor?: number; /** * Enable IDF-style weighting to reduce MI for high-degree nodes. * Uses inverse document frequency formula from information retrieval. * MI_adjusted = MI_base × log(N/(deg(u)+1)) × log(N/(deg(v)+1)) * @default false */ useIDFWeighting?: boolean; /** * Enable edge type rarity penalty. * Penalizes common edge types (like "has_concept") and boosts rare ones. * MI_adjusted = MI_base × (-log(P(edge_type))) * @default false */ useEdgeTypeRarity?: boolean; /** * Use Adamic-Adar instead of Jaccard for structural MI. * AA(u,v) = Σ_{w ∈ N(u) ∩ N(v)} 1/log(deg(w)) * Naturally downweights common neighbors with high degree. * Better for dense social networks where Jaccard is less discriminative. * @default false */ useAdamicAdar?: boolean; /** * Normalize Jaccard by expected overlap given graph density. * normalized = (observed - expected) / (1 - expected) * where expected ≈ density² (random graph baseline). * Adjusts structural MI for graph density effects. * @default false */ useDensityNormalization?: boolean; /** * Graph density for density normalization (edges / max_possible_edges). * If not provided, computed automatically from the graph. * @default undefined (auto-computed) */ graphDensity?: number; /** * Penalize MI for nodes with high local clustering coefficient. * MI_adjusted = MI × (1 - max(cc(u), cc(v))) * Favors paths through structural holes (bridges) over clustered regions. * Useful for finding diverse, non-redundant paths. * @default false */ useClusteringPenalty?: boolean; /** * Estimated total nodes for IDF weighting in streaming/incremental contexts. * When provided, uses this value instead of computing from graph. * Enables IDF-Weighted MI without full graph awareness. * * Example values: * - OpenAlex: ~250,000,000 works * - Local subgraph: use maxSeenNodes during exploration * * @default undefined (compute from graph) */ estimatedTotalNodes?: number; } /** * Normalized Discounted Cumulative Gain. * Measures ranking quality with position-based discounting. * * @param predicted - Predicted ranking with relevance scores * @param groundTruth - Ideal ranking (sorted by true relevance) * @param k - Cutoff position (default: all items) * @returns NDCG@k ∈ [0, 1], where 1 = perfect ranking */ export declare const ndcg: (predicted: Array<{ id: string; relevance: number; }>, groundTruth: Array<{ id: string; relevance: number; }>, k?: number) => number; /** * Negative weight error (for algorithms requiring non-negative weights). */ export declare type NegativeWeightError = { type: "negative-weight"; message: string; weight: number; edgeId: string; }; /** * Neighbor relationship returned by GraphExpander.getNeighbors(). * * Represents a directed relationship from one node to another with * metadata about the relationship type. */ declare interface Neighbor { /** Target node ID */ targetId: string; /** Type of relationship (e.g., 'citation', 'authorship', 'affiliation') */ relationshipType: string; } /** * Base Node interface with required discriminator field. * All node types must extend this interface. * * id - Unique node identifier (must be unique within graph) * type - Discriminator field for runtime type narrowing * * @example * ```typescript * type WorkNode = { * id: string; * type: 'work'; * title: string; * year: number; * }; * * type AuthorNode = { * id: string; * type: 'author'; * name: string; * }; * * type AcademicNode = WorkNode | AuthorNode; * * const processNode = (node: AcademicNode) => { * if (node.type === 'work') { * console.log(node.title); // TypeScript knows it's WorkNode * } else { * console.log(node.name); // TypeScript knows it's AuthorNode * } * }; * ``` */ declare interface Node_2 extends NodeBase_2 { type: string; [key: string]: unknown; } export { Node_2 as Node } /** * ReadableGraph - Minimal generic interface for graph traversal algorithms. * * Provides the minimal API required for BFS, DFS, bidirectional BFS, * ego network extraction, and other traversal algorithms. */ /** * Base interface for graph nodes. * * @template T - Additional properties extending the base node */ export declare interface NodeBase { /** Unique identifier for the node */ id: string; } /** * Core graph algorithm types. */ /** * Base node interface - minimum requirements. * All node types must extend this with an id field. */ declare interface NodeBase_2 { id: string; } /** * Node not found error (seed node doesn't exist in graph). */ export declare type NodeNotFoundError = { type: "node-not-found"; message: string; nodeId: string; }; /** * Create an Option with no value. * @template T - Value type (inferred from context) * @returns Option with some: false * @example * ```typescript * const option: Option = None(); * // Option with some: false * ``` */ export declare const None: () => Option_2; /** Observability */ export declare type Observability = { kind: "fully_specified"; } | { kind: "partially_observed"; } | { kind: "latent_or_inferred"; }; /** * Create a successful Result. * @template T - Success value type * @param value - The success value * @returns Result with ok: true * @example * ```typescript * const result = Ok(42); * // Result * ``` */ export declare const Ok: (value: T) => Result; declare interface Ok_2 { ok: true; value: T; } declare interface Ok_3 { ok: true; value: T; } declare interface Ok_4 { ok: true; value: T; } /** Operational semantics */ export declare type OperationalSemantics = { kind: "structural_only"; } | { kind: "annotated_with_functions"; } | { kind: "executable"; }; /** * Option type for optional values. * Discriminated union with `some` field for pattern matching. * @template T - Value type * @example * ```typescript * const option: Option = Some(42); * if (option.some) { * console.log(option.value); // 42 * } else { * console.log('No value'); * } * ``` */ declare type Option_2 = { some: true; value: T; } | { some: false; }; export { Option_2 as Option } /** * forbidden_subgraph Graph Class Type Definitions * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.823Z */ /** * Contains no induced path on 5 vertices */ declare type P5Free = { kind: "p5_free"; } | { kind: "has_p5"; } | { kind: "unconstrained"; }; /** * Rank paths by sum of PageRank scores along path. * Prefers paths through important nodes. * * @param graph - Graph to analyse * @param paths - Paths to rank * @param dampingFactor - PageRank damping (default: 0.85) * @returns Paths sorted by total PageRank (descending) */ export declare const pageRankRanker: (graph: Graph, paths: Path[], dampingFactor?: number) => RankedPath[]; /** * Paired t-test for comparing two methods. * * Tests whether the mean difference between paired observations is significantly * different from zero. Assumes differences are normally distributed. * * @param method1Results - Results from method 1 across experiments * @param method2Results - Results from method 2 across experiments (same length as method1Results) * @param alpha - Significance level (default: 0.05) * @returns p-value, t-statistic, and whether result is significant * * @example * ```typescript * const miScores = [0.85, 0.82, 0.88, 0.90, 0.87]; * const baselineScores = [0.65, 0.70, 0.68, 0.72, 0.69]; * const result = pairedTTest(miScores, baselineScores); * console.log(result.pValue); // e.g., 0.001 (significant) * console.log(result.significant); // true * ``` */ export declare const pairedTTest: (method1Results: number[], method2Results: number[], alpha?: number) => { pValue: number; tStatistic: number; significant: boolean; }; /** * Parsed Pajek document structure. */ export declare interface PajekDocument { /** Declared vertex count */ vertexCount: number; /** Vertex definitions (may be empty if only count declared) */ vertices: PajekVertex[]; /** Edges (undirected connections) */ edges: PajekEdge[]; /** Arcs (directed connections) */ arcs: PajekEdge[]; /** Whether the network is directed (has arcs) */ directed: boolean; } /** * An edge/arc in a Pajek document. */ export declare interface PajekEdge { /** Source vertex ID */ source: number; /** Target vertex ID */ target: number; /** Optional edge weight */ weight?: number; } /** * Convert a parsed Pajek document to normalized JSON format. * * @param doc - Parsed Pajek document * @param document * @param options - Conversion options * @returns Graph in normalized JSON format */ export declare const pajekToJson: (document: PajekDocument, options: PajekToJsonOptions) => GraphJson; /** * Options for converting Pajek to JSON. */ export declare interface PajekToJsonOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection */ directed?: boolean; } /** * Pajek .net format type definitions. * * Pajek is a Windows program for analysis of large networks. * The .net format is its primary text-based network format. */ /** * A vertex in a Pajek document. */ export declare interface PajekVertex { /** Vertex ID (1-indexed in Pajek) */ id: number; /** Optional vertex label */ label?: string; /** Optional x coordinate */ x?: number; /** Optional y coordinate */ y?: number; /** Optional z coordinate */ z?: number; } /** * Parse a UCINet DL format string into a structured document. * * @param content - The .dl file content * @returns Parsed DL document */ export declare const parseDl: (content: string) => DlDocument; /** * Parse a GD4 format string into a structured document. * * @param content - The .gd4 file content * @returns Parsed GD4 document */ export declare const parseGd4: (content: string) => Gd4Document; /** * Parse a GML string into a structured document. * * @param gml - GML file content as string * @returns Parsed GML document */ export declare const parseGml: (gml: string) => GmlDocument; /** * Parse a Matrix Market .mtx string into a structured document. * * @param content - The .mtx file content * @returns Parsed Matrix Market document */ export declare const parseMtx: (content: string) => MtxDocument; /** * Parse a Pajek .net format string into a structured document. * * @param content - The .net file content * @returns Parsed Pajek document */ export declare const parsePajek: (content: string) => PajekDocument; /** * Parse a SNAP edge list string into a document. * * @param content - Edge list file content * @returns Parsed SNAP document */ export declare const parseSnap: (content: string) => SnapDocument; /** * Parse the timestamp from a Wayback Machine archived URL. * * @param archivedUrl * @example * ```ts * const timestamp = parseTimestamp("https://web.archive.org/web/20260117111255id_/https://example.com"); * // Returns "20260117111255" * ``` */ export declare const parseTimestamp: (archivedUrl: string) => string | null; /** * Parse a Wayback timestamp into a Date object. * @param timestamp */ export declare const parseTimestampToDate: (timestamp: string) => Date | null; /** Partiteness (bipartite, k-partite) */ export declare type Partiteness = { kind: "unrestricted"; } | { kind: "bipartite"; } | { kind: "k_partite"; k: number; }; /** * Balanced graph partition from spectral partitioning. * Divides graph into k subgraphs while minimizing edge cuts. */ export declare interface Partition { /** Partition identifier (0 to k-1) */ id: PartitionId; /** Nodes assigned to this partition */ nodes: Set; /** Number of nodes in partition */ size: number; /** Edges connecting this partition to other partitions */ edgeCuts: number; /** Size relative to ideal size (ideal = n/k) */ balance: number; } /** * Partition identifier (0 to k-1) */ export declare type PartitionId = number; /** * Error type for partitioning algorithms (spectral). */ export declare type PartitioningError = { type: "EmptyGraph"; message: string; } | { type: "InvalidInput"; message: string; } | { type: "InsufficientNodes"; message: string; required: number; actual: number; } | { type: "InvalidPartitionCount"; message: string; k: number; nodeCount: number; }; /** * Path from source to destination node. * Contains ordered nodes, connecting edges, and total weight. * @template N - Node type * @template E - Edge type * nodes - Nodes in path order (source to destination) * edges - Edges connecting consecutive nodes * totalWeight - Sum of edge weights * @invariant nodes.length >= 2 (at least source and destination) * @invariant edges.length === nodes.length - 1 * @invariant edges[i].source === nodes[i].id && edges[i].target === nodes[i+1].id * @example * ```typescript * const result = dijkstra(graph, 'A', 'Z'); * if (result.ok && result.value.some) { * const path = result.value.value; * console.log('Path length:', path.nodes.length); * console.log('Total weight:', path.totalWeight); * console.log('Path:', path.nodes.map(n => n.id).join(' -> ')); * } * ``` */ export declare interface Path { /** Nodes in path order (source to destination) */ nodes: N[]; /** Edges connecting nodes in path */ edges: E[]; /** Sum of edge weights */ totalWeight: number; } /** * Comprehensive path diversity metrics. */ export declare interface PathDiversityMetrics { /** Number of distinct paths */ pathCount: number; /** Mean pairwise node-based Jaccard distance */ nodeJaccardDistance: number; /** Mean pairwise edge-based Jaccard distance */ edgeJaccardDistance: number; /** Total unique nodes across all paths */ uniqueNodeCount: number; /** Total unique edges across all paths */ uniqueEdgeCount: number; /** Average path length */ meanPathLength: number; /** Standard deviation of path lengths */ stdPathLength: number; } /** * Check if a path follows a type template. * @param path * @param template */ export declare const pathFollowsTemplate: (path: Path, template: string[]) => boolean; /** * Path ranking function type. * * Takes a list of candidate paths and returns them ranked by relevance. */ export declare type PathRanker = (graph: Graph, paths: Path[]) => Array<{ path: Path; score: number; }>; /** * Configuration for path ranking. * @template N - Node type * @template E - Edge type */ export declare interface PathRankingConfig { /** * Traversal mode for path finding. * - 'directed': Only traverse edges in their natural direction * - 'undirected': Traverse edges in both directions (default) * @default 'undirected' */ traversalMode?: TraversalMode; /** * Length penalty parameter λ. * - λ = 0: Path length irrelevant, purely information quality (default) * - λ > 0: Longer paths penalised exponentially * - λ → ∞: Reduces to shortest path selection * @default 0 */ lambda?: number; /** * Weight mode for incorporating edge weights. * - 'none': Ignore weights (default) * - 'divide': Divide score by mean weight * - 'multiplicative': Apply multiplicative weight penalty * @default 'none' */ weightMode?: WeightMode; /** * Extract weight from an edge. * If not provided, uses edge.weight property (defaulting to 1). */ weightExtractor?: (edge: E) => number; /** * Maximum number of paths to return. * @default 10 */ maxPaths?: number; /** * Maximum path length to consider. * Prevents exponential blowup in dense graphs. * Only used when shortestOnly is false. * @default Infinity */ maxLength?: number; /** * Whether to only consider shortest paths. * - true (default): Only enumerate paths of minimum length (backwards compatible) * - false: Enumerate all paths up to maxLength, letting MI + λ determine ranking * * When false, the λ (lambda) parameter becomes meaningful: * - λ = 0: Pure MI quality, length irrelevant (may prefer longer paths) * - λ > 0: Trade-off between MI quality and path efficiency * - λ → ∞: Effectively reduces to shortest path selection * * @default true */ shortestOnly?: boolean; /** * Pre-computed MI cache. If not provided, MI will be computed on-demand. * For ranking multiple path queries on the same graph, pre-compute once * and pass the cache here for better performance. */ miCache?: MutualInformationCache; /** * Configuration for MI computation (only used if miCache not provided). */ miConfig?: MutualInformationConfig; /** * Small constant to avoid log(0). * @default 1e-10 */ epsilon?: number; } /** * Convert a path (array of node IDs) to a set for Jaccard computation. * * @param path - Array of node IDs forming a path * @returns Set of node IDs */ export declare const pathToNodeSet: (path: string[]) => Set; /** * width Graph Class Type Definitions * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.826Z */ /** * Pathwidth at most k */ declare type Pathwidth = { kind: "pathwidth_bounded"; } | { kind: "pathwidth_unbounded"; } | { kind: "unconstrained"; }; /** * Structural Graph Classes * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.828Z */ /** Perfect graph property (ω(H) = χ(H) for all induced subgraphs) */ export declare type Perfect = { kind: "perfect"; } | { kind: "imperfect"; } | { kind: "unconstrained"; }; /** Perfect matching property */ export declare type PerfectMatching = { kind: "perfect_matching"; } | { kind: "near_perfect"; } | { kind: "no_perfect_matching"; } | { kind: "unconstrained"; }; /** Permutation graph property */ export declare type Permutation = { kind: "permutation"; } | { kind: "not_permutation"; } | { kind: "unconstrained"; }; /** * geometric Graph Class Type Definitions * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.827Z */ /** * Can be drawn in plane without edge crossings */ export declare type Planar = { kind: "planar"; } | { kind: "nonplanar"; } | { kind: "unconstrained"; }; /** * Plant citation network paths with realistic structure. * * Creates paths that model actual scholarly communication patterns: * - Direct citation chains: Papers citing papers in sequence * - Co-citation bridges: Papers cited together by a third paper * - Bibliographic coupling: Papers sharing common references * - Author-mediated: Papers linked through shared authors * - Venue-mediated: Papers linked through publication venues * * @template N - Node type (typically Work nodes) * @template E - Edge type (typically cites or related edges) * @param graph - Citation network graph * @param pathType - Type of citation path to plant * @param config - Planting configuration * @returns PlantedPathResult with graph and ground truth paths */ export declare const plantCitationPaths: (graph: Graph, pathType: CitationPathType, config: CitationPathConfig) => PlantedPathResult; /** * Configuration for planted path generation. */ export declare interface PlantedPathConfig { /** Type marker for N (unused but required for type inference) */ _nodeType?: N; /** Type marker for E (unused but required for type inference) */ _edgeType?: E; /** Number of ground truth paths to plant */ numPaths: number; /** Path length range (number of edges) */ pathLength: { min: number; max: number; }; /** MI signal strength (higher = more distinguishable) */ signalStrength: "weak" | "medium" | "strong"; /** Whether planted paths should share nodes */ allowOverlap: boolean; /** Random seed for reproducibility */ seed?: number; /** Source node IDs to start paths from (optional) */ sourceNodes?: string[]; /** Target node IDs to end paths at (optional) */ targetNodes?: string[]; } /** * Result of path planting. */ export declare interface PlantedPathResult { /** Modified graph with planted paths */ graph: Graph; /** Ground truth paths (in order of "true" relevance) */ groundTruthPaths: Path[]; /** Relevance scores for each path */ relevanceScores: Map; /** Metadata about planting */ metadata: { nodesAdded: number; edgesAdded: number; avgPathMI: number; }; } /** * Plant ground truth paths in a graph for evaluation. * * Creates paths with controlled MI characteristics: * - Strong signal: High MI edges, clear separation from noise * - Medium signal: Moderate MI, some ambiguity * - Weak signal: Low MI delta, challenging to detect * * @template N - Node type * @template E - Edge type * @param baseGraph - Graph to modify * @param config - Planting configuration * @returns Graph with planted paths and ground truth */ export declare const plantGroundTruthPaths: (baseGraph: Graph, config: PlantedPathConfig) => PlantedPathResult; /** * Plant paths in heterogeneous graphs respecting entity type constraints. * * Ensures planted paths follow a type pattern (e.g., Work → Author → Work → Institution). * * @template N - Node type * @template E - Edge type * @param graph - Heterogeneous graph * @param pathTemplate - Template specifying node types along path * @param config - Planting configuration * @returns Graph with planted heterogeneous paths */ export declare const plantHeterogeneousPaths: (graph: Graph, pathTemplate: string[], config: HeterogeneousPathConfig) => PlantedPathResult; /** Port specification */ export declare type Ports = { kind: "none"; } | { kind: "port_labelled_vertices"; }; /** * Positioned node with layout coordinates. * * Used in hierarchical and force-directed layouts. */ export declare interface PositionedNode { /** Node data */ node: N; /** X coordinate */ x: number; /** Y coordinate */ y: number; /** Level in hierarchy (for tree layouts) */ level?: number; } /** * Precision at K. * Fraction of top-K items that are relevant. * * @param predicted - Predicted ranking (item IDs) * @param relevantItems - Set of relevant item IDs * @param k - Cutoff position * @returns P@K ∈ [0, 1] */ export declare const precisionAtK: (predicted: string[], relevantItems: Set, k: number) => number; /** * Pre-computed importance values for a graph */ export declare interface PrecomputedImportance { degree: Map; pagerank: Map; combined: Map; } /** * Pre-compute all importance values for a graph * * Call this once per graph, then pass the result to computeGroundTruth * via the precomputedImportance config option for efficiency. * * @param graph - Graph to compute importance for * @param dampingFactor - PageRank damping factor (default: 0.85) * @param degreeWeight - Weight for degree in combined score (default: 0.5) * @returns Pre-computed importance values for all types */ export declare const precomputeImportance: (graph: Graph, dampingFactor?: number, degreeWeight?: number) => PrecomputedImportance; /** * Pre-compute mutual information for all edges in a graph. * * Automatically selects the appropriate MI computation method based on * graph properties: * 1. If attributeExtractor is provided and returns values, use attribute-based MI * 2. If nodes have diverse types, use node type-based MI * 3. If useEdgeTypes is enabled or edges have diverse types, use edge type-based MI * 4. Otherwise, fall back to structural (Jaccard) MI * * Additional modifiers are applied multiplicatively: * - Temporal: Edge recency modifier * - Signed: Negative edge penalty modifier * - Probabilistic: Edge probability modifier * - Community: Same-community boost modifier * - Multiplex: Geometric mean across layers * - Hypergraph: Pairwise aggregation across hyperedge nodes * * Time Complexity: O(E × avg_degree) for structural MI, O(E) for attribute/type MI * Space Complexity: O(E) for the cache * * @template N - Node type * @template E - Edge type * @param graph - The graph to analyse * @param config - Optional configuration for MI computation * @returns Cache of pre-computed MI values keyed by edge ID * * @example * ```typescript * const graph = new Graph(true); * // ... add nodes and edges ... * * // With attribute extractor * const cache = precomputeMutualInformation(graph, { * attributeExtractor: (node) => [node.value, node.weight] * }); * * // With temporal decay * const cache = precomputeMutualInformation(graph, { * timestampExtractor: (edge) => edge.timestamp, * temporalDecay: 0.001, * referenceTime: Date.now() * }); * * // Without attributes (uses structural similarity) * const cache = precomputeMutualInformation(graph); * * // Get MI for an edge * const mi = cache.get('edge-1'); // number | undefined * ``` */ export declare const precomputeMutualInformation: (graph: Graph, config?: MutualInformationConfig) => MutualInformationCache; /** * Options for weighted priority calculation. * * Used by calculatePriority() to implement the thesis-aligned priority function. */ declare interface PriorityOptions { /** * Node weight for normalization (w_V(v) in thesis formula). * Higher values decrease priority (node is considered more important/central). * Default: 1 (unweighted nodes). */ nodeWeight?: number; /** * Small constant to prevent division by zero. * Default: 1e-10. */ epsilon?: number; /** * Whether to use simple degree count (legacy behavior) or weighted formula. * Default: false (use weighted formula). * * @deprecated Use weighted formula for thesis alignment. Set true only for backward compatibility. */ useSimpleDegree?: boolean; } /** * Priority queue for bidirectional BFS frontier management. * * Min-heap implementation that returns items with lowest priority first. * Includes duplicate prevention and iteration support. * * Time Complexity: * - push: O(log n) * - pop: O(log n) * - contains: O(1) * - length: O(1) * * Space Complexity: O(n) for heap array and item set * * @template T - Type of items stored in the queue * @example * ```typescript * const queue = new PriorityQueue(); * queue.push('nodeA', 10); // Low-degree node (high priority) * queue.push('nodeB', 100); // High-degree node (low priority) * * const next = queue.pop(); // Returns 'nodeA' (lower degree = higher priority) * ``` */ export declare class PriorityQueue { private heap; private itemSet; /** * Add an item to the queue with given priority. * Silently ignores duplicates. * * @param item - Item to add * @param priority - Priority value (lower values = higher priority) */ push(item: T, priority: number): void; /** * Remove and return the item with lowest priority. * * @returns Item with minimum priority, or undefined if queue is empty */ pop(): T | undefined; /** * Get the number of items in the queue. */ get length(): number; /** * Peek at the priority of the minimum item without removing it. * * @returns Priority of the item with minimum priority, or Infinity if queue is empty */ peekPriority(): number; /** * Check if an item is in the queue. * * @param item - Item to check * @returns true if item is in queue */ contains(item: T): boolean; /** * Make the queue iterable for checking connections. * Iterates over items in no particular order (not sorted by priority). */ [Symbol.iterator](): Iterator; /* Excluded from this release type: bubbleUp */ /* Excluded from this release type: bubbleDown */ } /** * probe Graph Class Type Definitions * * AUTO-GENERATED by scripts/codegen/generate-graph-classes.ts * DO NOT EDIT MANUALLY * * @generated 2026-01-18T16:10:41.826Z */ /** * Vertices partitioned into probes and non-probes, can add edges among non-probes to make chordal */ declare type ProbeChordal = { kind: "probe_chordal"; } | { kind: "not_probe_chordal"; } | { kind: "unconstrained"; }; /** * Can add edges among non-probes to form interval graph */ declare type ProbeInterval = { kind: "probe_interval"; } | { kind: "not_probe_interval"; } | { kind: "unconstrained"; }; /** * Circular arc graph with no arc containment */ declare type ProperCircularArc = { kind: "proper_circular_arc"; } | { kind: "not_proper_circular_arc"; } | { kind: "unconstrained"; }; /** * Result of a single property validation. */ export declare interface PropertyValidationResult { /** Property name being validated */ property: string; /** Expected value */ expected: string; /** Actual value */ actual: string; /** Whether validation passed */ valid: boolean; /** Optional error message */ message?: string; } /** * Validation result for a single property. */ declare interface PropertyValidationResult_2 { property: string; expected: string; actual: string; valid: boolean; message?: string; } /** * Validation result for a single property. */ declare interface PropertyValidationResult_3 { property: string; expected: string; actual: string; valid: boolean; message?: string; } /** * Distance hereditary and chordal */ declare type Ptolemaic = { kind: "ptolemaic"; } | { kind: "not_ptolemaic"; } | { kind: "unconstrained"; }; /** * No induced gem, no co-gem */ declare type QuasiLine = { kind: "quasi_line"; } | { kind: "not_quasi_line"; } | { kind: "unconstrained"; }; /** Minimum eccentricity among all vertices */ export declare type Radius = { kind: "radius"; value: number; } | { kind: "unconstrained"; }; /** Ramanujan graph: optimal expander with spectral gap property */ export declare type Ramanujan = { kind: "ramanujan"; degree: number; } | { kind: "not_ramanujan"; } | { kind: "unconstrained"; }; /** * Random Priority Bidirectional Expansion * * Baseline algorithm that selects nodes randomly from the frontier. * This serves as a null hypothesis baseline - if degree-prioritised expansion * doesn't outperform random selection, the degree heuristic provides no value. * * **Key Properties**: * - Random node selection from frontier (no priority) * - Seeded RNG for reproducibility * - No systematic hub avoidance OR hub seeking * - Terminates when all frontiers exhausted * * **Use in Experiments**: * - If MI ranking correlation is higher with degree-prioritised than random, * the degree heuristic is effective * - If path diversity is higher with degree-prioritised than random, * hub avoidance contributes to diversity * * @template T - Type of node data returned by expander */ export declare class RandomPriorityExpansion { private readonly expander; private readonly seeds; private readonly maxNodes?; private readonly hubThreshold; private readonly frontiers; private readonly paths; private readonly sampledEdges; private readonly rng; private stats; private readonly nodeDiscoveryIteration; /** Maps hub node IDs to the expansion step when first expanded */ private readonly hubEncounterOrder; /** * Create a new random-priority expansion. * * @param expander - Graph expander providing neighbour access * @param seeds - Array of seed node IDs (N >= 1) * @param seed - Random seed for reproducibility (default: 42) * @param maxNodes - Optional maximum nodes to expand * @param hubThreshold - Degree threshold for hub tracking (default: Infinity = no tracking) * @throws Error if no seeds provided */ constructor(expander: GraphExpander, seeds: readonly string[], seed?: number, maxNodes?: number | undefined, hubThreshold?: number); /** * Run the expansion to completion. * * Terminates when all frontiers are exhausted (no unexpanded nodes remain). * * @returns Expansion results including paths and sampled subgraph */ run(): Promise; /* Excluded from this release type: hasNonEmptyFrontier */ /* Excluded from this release type: selectRandomFrontier */ /* Excluded from this release type: reconstructPath */ /* Excluded from this release type: pathExists */ /* Excluded from this release type: recordDegree */ /* Excluded from this release type: getDegreeBucket */ } /** * Result from random-priority expansion - matches DegreePrioritisedExpansionResult. */ export declare interface RandomPriorityResult { /** Discovered paths (only populated when N >= 2 seeds) */ paths: Array<{ fromSeed: number; toSeed: number; nodes: string[]; }>; /** Union of all nodes visited by all frontiers */ sampledNodes: Set; /** Set of edges visited during expansion */ sampledEdges: Set; /** Per-frontier visited sets (for diagnostics) */ visitedPerFrontier: Array>; /** Statistics about the expansion */ stats: RandomPriorityStats; /** Maps each node to the iteration when it was first discovered */ nodeDiscoveryIteration: Map; /** Maps hub node IDs to the expansion step when first expanded. Hub = degree >= hubThreshold */ hubEncounterOrder: Map; } /** * Statistics collected during random-priority expansion. */ export declare interface RandomPriorityStats { /** Total nodes expanded (popped from frontiers) */ nodesExpanded: number; /** Total edges traversed */ edgesTraversed: number; /** Iterations (single node expansions) performed */ iterations: number; /** Breakdown of nodes by degree ranges */ degreeDistribution: Map; /** Fraction of total expansion complete when first hub is expanded (0-1). -1 if no hubs. */ firstHubEncounterFraction: number; /** Mean fraction of expansion complete across all hub encounters */ meanHubEncounterFraction: number; } /** * Random path ranking baseline. * Shuffles paths randomly for comparison. * * @param paths - Paths to rank * @param seed - Random seed for reproducibility * @returns Randomly ordered paths with scores */ export declare const randomRanker: (paths: Path[], seed?: number) => RankedPath[]; /** * Rank-biserial correlation (non-parametric effect size). * * Based on Mann-Whitney U test. Measures relationship between group * membership and rank ordering. * * Interpretation similar to Cliff's delta. * * @param group1 - Samples from group 1 * @param group2 - Samples from group 2 * @returns Effect size, correlation coefficient, and interpretation * * @example * ```typescript * const group1 = [8, 9, 7, 8, 10]; * const group2 = [5, 6, 5, 6, 7]; * const result = rankBiserialCorrelation(group1, group2); * console.log(result.correlation); // e.g., 0.85 (strong positive correlation) * console.log(result.effectSize); // e.g., 0.70 (large effect) * ``` */ export declare const rankBiserialCorrelation: (group1: number[], group2: number[]) => { effectSize: number; correlation: number; interpretation: "negligible" | "small" | "medium" | "large"; }; /** * A ranked path with its computed score. * @template N - Node type * @template E - Edge type */ export declare interface RankedPath { /** The path (nodes and edges) */ path: Path; /** Information-theoretic ranking score M(P) */ score: number; /** Geometric mean of MI values along the path (before length penalty) */ geometricMeanMI: number; /** Individual MI values for each edge in the path */ edgeMIValues: number[]; /** Length penalty factor exp(-λk), only present if lambda > 0 */ lengthPenalty?: number; /** Weight factor applied to score, only present if weightMode != 'none' */ weightFactor?: number; } /** * Rank paths between two nodes using information-theoretic scoring. * * Finds all shortest paths between source and target, then ranks them * by the geometric mean of mutual information along their edges. * * **Formula**: M(P) = exp((1/k) × Σᵢ log I(uᵢ; vᵢ)) × exp(-λk) * * Time Complexity: O(V + E) for path finding + O(n × k) for scoring n paths of length k * Space Complexity: O(V + E) for BFS + O(E) for MI cache * * @template N - Node type * @template E - Edge type * @param graph - The graph to search * @param startId - Source node ID * @param endId - Target node ID * @param config - Optional configuration * @returns Result containing ranked paths or error * * @example * ```typescript * const graph = new Graph(false); * // ... add nodes and edges ... * * // Basic usage: rank all shortest paths * const result = rankPaths(graph, 'A', 'Z'); * if (result.ok && result.value.some) { * const ranked = result.value.value; * console.log('Best path:', ranked[0].path.nodes.map(n => n.id).join(' -> ')); * console.log('Score:', ranked[0].score); * } * * // With custom MI computation * const result = rankPaths(graph, 'A', 'Z', { * miConfig: { * attributeExtractor: (node) => [node.value, node.weight] * }, * lambda: 0.1, // Slight penalty for longer paths * maxPaths: 5 * }); * ``` */ export declare const rankPaths: (graph: Graph, startId: string, endId: string, config?: PathRankingConfig) => Result[]>, GraphError>; /** * Minimal interface for readable graph operations. * * Graph implementations must implement this interface to work with * traversal algorithms (BFS, DFS, bidirectional BFS, etc.). * * @template N - Node type extending NodeBase * @template E - Edge type extending EdgeBase */ export declare interface ReadableGraph { /** * Check if a node exists in the graph. * @param id - Node ID to check * @returns true if node exists, false otherwise */ hasNode(id: string): boolean; /** * Get a node by ID. * @param id - Node ID to retrieve * @returns Node data or null if not found */ getNode(id: string): N | null; /** * Get neighbor node IDs for a given node. * @param id - Node ID to get neighbors for * @returns Array of neighbor IDs (empty array if node not found) */ getNeighbors(id: string): string[]; /** * Get all nodes in the graph. * @returns Array of all nodes */ getAllNodes(): N[]; /** * Check if graph is directed. * @returns true if directed, false if undirected */ isDirected(): boolean; /** * Get outgoing edges from a node. * * For directed graphs: Returns edges where node is the source. * For undirected graphs: Returns edges where node is either source or target. * * Used by ego-network extraction to preserve edge metadata. * * @param id - Node ID to get outgoing edges from * @returns Array of outgoing edges (empty array if node not found) */ getOutgoingEdges?(id: string): E[]; } /** * Recall at K. * Fraction of relevant items in top-K. * * @param predicted - Predicted ranking (item IDs) * @param relevantItems - Set of relevant item IDs * @param k - Cutoff position * @returns R@K ∈ [0, 1] */ export declare const recallAtK: (predicted: string[], relevantItems: Set, k: number) => number; /** * Resolve the path to a benchmark dataset file. * * @param meta - Dataset metadata * @param benchmarksRoot - Optional root directory for benchmarks (defaults to repo data/benchmarks/) * @returns Absolute path to the dataset file */ export declare const resolveBenchmarkPath: (meta: BenchmarkDatasetMeta, benchmarksRoot?: string) => string; /** * Result type for operations that can fail. * Discriminated union with `ok` field for pattern matching. * @template T - Success value type * @template E - Error type * @example * ```typescript * const result: Result = Ok(42); * if (result.ok) { * console.log(result.value); // 42 * } else { * console.error(result.error); * } * ``` */ export declare type Result = { ok: true; value: T; } | { ok: false; error: E; }; declare type Result_2 = Ok_2 | Error_; declare type Result_3 = Ok_3 | Error__2; declare type Result_4 = Ok_4 | Error__3; /** Tree rooting */ export declare type Rooting = { kind: "unrooted"; } | { kind: "rooted"; } | { kind: "multi_rooted"; }; /** * Run cross-validation experiment. * * Divides data into k folds, trains on k-1 folds, tests on held-out fold. * Provides more robust estimate of method performance. * * @template N - Node type * @template E - Edge type * @param config - Experiment configuration * @param baseGraph - Base graph * @param folds - Number of cross-validation folds (default: 5) * @returns Aggregated results across folds * * @example * ```typescript * const result = await runCrossValidation(config, graph, 5); * console.log(result.aggregated.spearman); // Average spearman across folds * console.log(result.stdDev.spearman); // Standard deviation * ``` */ export declare const runCrossValidation: (config: ExperimentConfig, baseGraph: Graph, folds?: number) => Promise<{ foldResults: ExperimentReport[]; aggregated: ExperimentReport; stdDev: ExperimentReport; }>; /** * Run a complete evaluation experiment. * * Executes all configured methods on multiple graph instances, * computes evaluation metrics, and performs statistical testing. * * @template N - Node type * @template E - Edge type * @param config - Experiment configuration * @param baseGraph - Base graph to use for experiments * @returns Complete experiment report * * @example * ```typescript * const config: ExperimentConfig = { * name: 'MI vs Random Baseline', * repetitions: 10, * pathPlanting: { numPaths: 5, signalStrength: 'medium', ... }, * methods: [ * { name: 'MI', ranker: miRanker }, * { name: 'Random', ranker: randomRanker }, * ], * metrics: ['spearman', 'ndcg'], * statisticalTests: ['paired-t'], * seed: 42, * }; * * const report = await runExperiment(config, graph); * console.log(report.winner); // 'MI' (if significantly better) * ``` */ export declare const runExperiment: (config: ExperimentConfig, baseGraph: Graph) => Promise; /** * Network Analysis Properties * * Properties from network science: scale-free, small-world, community structure. */ /** Scale-free property (power-law degree distribution) */ export declare type ScaleFree = { kind: "scale_free"; exponent?: number; } | { kind: "not_scale_free"; }; /** Node/edge type diversity property */ export declare type SchemaHomogeneity = { kind: "homogeneous"; } | { kind: "heterogeneous"; }; /** * Symmetry Properties * * Properties related to graph automorphisms and symmetries. */ /** Self-complementary property */ export declare type SelfComplementary = { kind: "self_complementary"; } | { kind: "not_self_complementary"; } | { kind: "unconstrained"; }; /** Self-loop permission property */ export declare type SelfLoops = { kind: "allowed"; } | { kind: "disallowed"; }; /** * Serialize a graph JSON object to GML format. * * @param graph - Graph in normalized JSON format * @param options - Serialization options * @returns GML string */ export declare const serializeGml: (graph: GraphJson, options?: SerializeGmlOptions) => string; /** * Options for GML serialization. */ export declare interface SerializeGmlOptions { /** Include creator comment */ creator?: string; /** Indentation string (default: two spaces) */ indent?: string; /** Use numeric IDs instead of labels */ useNumericIds?: boolean; } /** * Rank paths by length (shortest first). * Standard baseline for path finding. * * @param paths - Paths to rank * @returns Paths sorted by length (ascending) */ export declare const shortestPathRanker: (paths: Path[]) => RankedPath[]; /** * Shuffle an array in-place using Fisher-Yates algorithm. * @param array - Array to shuffle (modified in-place) * @param seed - Optional random seed for deterministic shuffling (for tests) * @returns The shuffled array (same reference as input) * @remarks * Fisher-Yates shuffle guarantees uniform distribution of permutations. * If seed is provided, uses simple linear congruential generator (LCG) for PRNG. * If seed is undefined, uses Math.random() (non-deterministic). * * LCG parameters: a=1664525, c=1013904223, m=2^32 (Numerical Recipes) */ export declare const shuffle: (array: T[], seed?: number) => T[]; /** Edge signedness */ export declare type Signedness = { kind: "unsigned"; } | { kind: "signed"; } | { kind: "multi_signed"; }; export declare const simpleDirectedGraph: SimpleDirectedGraphSpec; /** Type-level intersection for simple directed graphs */ export declare type SimpleDirectedGraphSpec = GraphSpec_2 & Readonly<{ edgeMultiplicity: { kind: "simple"; }; selfLoops: { kind: "disallowed"; }; directionality: { kind: "directed"; }; }>; export declare const simpleUndirectedGraph: SimpleUndirectedGraphSpec; /** Type-level intersection for simple undirected graphs */ export declare type SimpleUndirectedGraphSpec = GraphSpec_2 & Readonly<{ edgeMultiplicity: { kind: "simple"; }; selfLoops: { kind: "disallowed"; }; directionality: { kind: "undirected"; }; }>; /** Small-world property (high clustering + short paths) */ export declare type SmallWorld = { kind: "small_world"; rewireProbability?: number; meanDegree?: number; } | { kind: "not_small_world"; } | { kind: "unconstrained"; }; /** * Type definitions for SNAP edge list format. */ /** * Parsed SNAP document containing edges and metadata from comments. */ export declare interface SnapDocument { /** Edges as [source, target] pairs */ edges: Array<[string, string]>; /** Metadata extracted from comment lines */ meta: { /** Number of nodes (from comments) */ nodes?: number; /** Number of edges (from comments) */ edges?: number; /** Whether the graph is directed (from comments or inferred) */ directed?: boolean; /** Raw comment lines */ comments: string[]; }; } export declare interface SnapshotOptions extends UrlFormatOptions { limit?: number; from?: string; to?: string; } /** * Convert a parsed SNAP document to normalized JSON format. * * @param doc - Parsed SNAP document * @param document * @param options - Conversion options including metadata * @returns Graph in normalized JSON format */ export declare const snapToJson: (document: SnapDocument, options: SnapToJsonOptions) => GraphJson; /** * Options for converting SNAP to JSON. */ export declare interface SnapToJsonOptions { /** Metadata to include in output */ meta: Omit; /** Override directed detection (default: infer from comments or assume undirected) */ directed?: boolean; } /** * Create an Option with a value present. * @template T - Value type * @param value - The present value * @returns Option with some: true * @example * ```typescript * const option = Some(42); * // Option * ``` */ export declare const Some: (value: T) => Option_2; /** Spanning tree property */ export declare type SpanningTree = { kind: "spanning_tree"; of: string; } | { kind: "not_spanning_tree"; } | { kind: "unconstrained"; }; /** * Spearman's rank correlation coefficient. * Measures monotonic relationship between predicted and ground truth rankings. * * @param predicted - Predicted ranking (array of item IDs in rank order) * @param groundTruth - Ground truth ranking (array of item IDs in rank order) * @returns ρ ∈ [-1, 1], where 1 = perfect agreement, -1 = perfect disagreement */ export declare const spearmanCorrelation: (predicted: string[], groundTruth: string[]) => number; /** * Compute Spearman rank correlation between two rankings. * * @param ranking1 - First ranking (node ID -> rank) * @param ranking2 - Second ranking (node ID -> rank) * @param commonNodes - Set of nodes to compare (intersection) * @returns Spearman correlation coefficient in [-1, 1] */ export declare const spearmanRankCorrelation: (ranking1: Map, ranking2: Map, commonNodes: Set) => number; /** Specific regularity property */ export declare type SpecificRegular = { kind: "k_regular"; k: number; } | { kind: "not_k_regular"; } | { kind: "unconstrained"; }; /** * Perform spectral graph partitioning. * * Divides graph into k balanced partitions by analyzing the spectral properties * of the graph Laplacian matrix. * @template N - Node type * @template E - Edge type * @param graph - Input graph (directed or undirected) * @param k - Number of partitions to create * @param options - Optional configuration * @param options.weightFn - Weight function for edges (default: all edges weight 1.0) * @param options.balanceTolerance - Maximum allowed imbalance (default: 1.2) * @param options.maxKMeansIterations - Max iterations for k-means (default: 100) * @param options.seed - Random seed for k-means initialization (default: undefined) * @returns Result containing array of k partitions or error * @example * ```typescript * const graph = new Graph(true); * // ... add nodes and edges ... * * const result = spectralPartition(graph, 4); * if (result.ok) { * console.log(`Created ${result.value.length} partitions`); * } * ``` */ export declare const spectralPartition: (graph: Graph, k: number, options?: { weightFn?: WeightFunction; balanceTolerance?: number; maxKMeansIterations?: number; seed?: number; }) => Result[], PartitioningError>; /** * Result type for Spectral Partitioning. */ export declare type SpectralPartitionResult = Result<{ partitions: Partition[]; balanceRatio: number; totalEdgeCuts: number; metadata: { algorithm: "spectral"; runtime: number; parameters: { k: number; balanceTolerance?: number; }; }; }, PartitioningError>; /** Spectral radius (ρ): largest eigenvalue (Perron-Frobenius for non-negative) */ export declare type SpectralRadius = { kind: "spectral_radius"; value: number; } | { kind: "unconstrained"; }; /** Full spectrum: eigenvalue-based properties */ export declare type Spectrum = { kind: "spectrum"; eigenvalues: readonly number[]; } | { kind: "unconstrained"; }; /** Split graph property (clique + independent set partition) */ export declare type Split = { kind: "split"; } | { kind: "non_split"; } | { kind: "unconstrained"; }; /** * Standard Bidirectional BFS Expansion * * Baseline algorithm for comparison with degree-prioritised expansion. * Expands nodes in breadth-first order (FIFO queue) without any prioritisation. * * This converges through high-degree hub nodes because BFS explores all nodes * at distance k before k+1, regardless of degree. Hubs are often encountered * early and their many neighbors flood the queue. * * **Key Properties**: * - FIFO expansion order (level-by-level) * - No degree-based prioritisation * - Converges through hubs (hub-biased sampling) * - Terminates when all frontiers exhausted * * @template T - Type of node data returned by expander */ export declare class StandardBfsExpansion { private readonly expander; private readonly seeds; private readonly maxNodes?; private readonly hubThreshold; private readonly frontiers; private readonly paths; private readonly sampledEdges; private stats; /** Tracks when each node was first discovered (iteration number) */ private readonly nodeDiscoveryIteration; /** Maps hub node IDs to the expansion step when first expanded */ private readonly hubEncounterOrder; /** * Create a new standard BFS expansion. * * @param expander - Graph expander providing neighbour access * @param seeds - Array of seed node IDs (N >= 1) * @param maxNodes - Optional maximum nodes to expand * @param hubThreshold - Degree threshold for hub tracking (default: Infinity = no tracking) * @throws Error if no seeds provided */ constructor(expander: GraphExpander, seeds: readonly string[], maxNodes?: number | undefined, hubThreshold?: number); /** * Run the expansion to completion. * * Terminates when all frontiers are exhausted (no unexpanded nodes remain). * * @returns Expansion results including paths and sampled subgraph */ run(): Promise; /* Excluded from this release type: hasNonEmptyFrontier */ /* Excluded from this release type: selectNextFrontier */ /* Excluded from this release type: reconstructPath */ /* Excluded from this release type: pathExists */ /* Excluded from this release type: recordDegree */ /* Excluded from this release type: getDegreeBucket */ } /** * Result from standard BFS expansion - matches DegreePrioritisedExpansionResult. */ export declare interface StandardBfsResult { /** Discovered paths (only populated when N >= 2 seeds) */ paths: Array<{ fromSeed: number; toSeed: number; nodes: string[]; }>; /** Union of all nodes visited by all frontiers */ sampledNodes: Set; /** Set of edges visited during expansion */ sampledEdges: Set; /** Per-frontier visited sets (for diagnostics) */ visitedPerFrontier: Array>; /** Statistics about the expansion */ stats: BfsExpansionStats; /** * Maps each sampled node to the iteration when it was first discovered. * Used for computing coverage efficiency metrics. */ nodeDiscoveryIteration: Map; /** Maps hub node IDs to the expansion step when first expanded. Hub = degree >= hubThreshold */ hubEncounterOrder: Map; } /** Star graph property (one central vertex) */ export declare type Star = { kind: "star"; } | { kind: "not_star"; } | { kind: "unconstrained"; }; /** * Star pattern motif. * Hub node with multiple leaf connections. */ export declare interface StarPattern { /** Central hub node */ hub: N; /** Leaf nodes connected to hub */ leaves: N[]; /** Star type (in-star or out-star) */ type: "in" | "out"; } /** * Options for star pattern detection. */ export declare interface StarPatternOptions { /** Minimum degree to qualify as star hub */ minDegree: number; /** Star type to detect */ type: "in" | "out"; } /** * Statistical test result. */ export declare interface StatisticalTestResult { type: string; comparison: string; pValue: number; significant: boolean; statistic?: number; ci?: { lower: number; upper: number; }; } /** * Available statistical tests. */ export declare type StatisticalTestType = "paired-t" | "wilcoxon" | "bootstrap"; /** * Storey's q-value method (FDR-based with estimation of true nulls). * * More powerful than BH when many hypotheses are truly null. * Estimates π₀ (proportion of true null hypotheses) from data. * * @param pValues - Array of p-values from multiple tests * @param fdr - Target false discovery rate (default: 0.05) * @param lambda - Tuning parameter for π₀ estimation (default: 0.5) * @returns Q-values and which tests are significant * * @example * ```typescript * const pValues = [0.001, 0.02, 0.045, 0.08, 0.12, 0.35, 0.42, 0.55]; * const result = storeyQValues(pValues, 0.05, 0.5); * console.log(result.qValues); // Estimated q-values * console.log(result.significant); // Which tests are significant at FDR=0.05 * ``` */ export declare const storeyQValues: (pValues: number[], fdr?: number, lambda?: number) => { qValues: number[]; significant: boolean[]; pi0: number; }; /** * Find all strongly connected components using Tarjan's algorithm. * * A strongly connected component (SCC) is a maximal set of vertices where * every vertex is reachable from every other vertex in the set. * * Time Complexity: O(V + E) * Space Complexity: O(V) * @param graph - The directed graph to analyze * @returns Result containing array of SCCs */ export declare const stronglyConnectedComponents: (graph: Graph) => Result[], InvalidInputError>; /** Strongly regular graph property */ export declare type StronglyRegular = { kind: "strongly_regular"; k: number; lambda: number; mu: number; } | { kind: "not_strongly_regular"; } | { kind: "unconstrained"; }; /** Strong product G ⊠ H */ export declare type StrongProduct = { kind: "strong_product"; leftFactors: number; rightFactors: number; } | { kind: "not_strong_product"; } | { kind: "unconstrained"; }; /** * Structural Representativeness Metrics * * Compares sampled subgraphs against ground truth between-graphs * to measure how well expansion strategies preserve graph structure. */ /** * Result of structural representativeness comparison. */ export declare interface StructuralRepresentativenessResult { /** Coverage: |Sampled ∩ Ground Truth| / |Ground Truth| */ coverage: number; /** Precision: |Sampled ∩ Ground Truth| / |Sampled| */ precision: number; /** F1 score: 2 * (precision * coverage) / (precision + coverage) */ f1Score: number; /** KL divergence of degree distributions */ degreeKL: number; /** Jensen-Shannon divergence (symmetric) */ degreeJS: number; /** Spearman correlation of betweenness centrality rankings */ betweennessCorrelation: number; /** Fraction of ground truth communities with at least one sampled node */ communityCoverage: number; /** Number of nodes in intersection */ intersectionSize: number; /** Number of nodes in sampled but not in ground truth */ falsePositives: number; /** Number of nodes in ground truth but not in sampled */ falseNegatives: number; } /** * Filter specification for subgraph filtering */ declare interface SubgraphFilter { /** Node filter predicate */ nodePredicate?: (node: N) => boolean; /** Edge filter predicate */ edgePredicate?: (edge: E) => boolean; /** Filter by node attribute values */ nodeAttributes?: Record; /** Filter by edge types */ edgeTypes?: Set; /** Combine multiple filters with AND (default) or OR */ combineMode?: "and" | "or"; } /** * Submit a URL to Wayback Machine for archiving. * * Uses the Save Page Now API to create a new snapshot. * Returns the archived URL with id_ suffix for direct access, or null on failure. * * @param url * @param options * @example * ```ts * const result = await submitToArchive("https://example.com"); * if (result) { * console.log(result.archived); // https://web.archive.org/web/20260117.../https://example.com * } * ``` */ export declare const submitToArchive: (url: string, options?: WaybackOptions) => Promise; /** Temporal properties */ export declare type Temporal = { kind: "static"; } | { kind: "dynamic_structure"; } | { kind: "temporal_edges"; } | { kind: "temporal_vertices"; } | { kind: "time_ordered"; }; /** Tensor (direct) product G × H */ export declare type TensorProduct = { kind: "tensor_product"; leftFactors: number; rightFactors: number; } | { kind: "not_tensor_product"; } | { kind: "unconstrained"; }; /** * Edge in a generated test graph. */ declare interface TestEdge { source: string; target: string; weight?: number; type?: string; } /** * Node in a generated test graph. */ /** * Complete graph structure for testing. */ export declare interface TestGraph { nodes: TestNode[]; edges: TestEdge[]; spec: GraphSpec_2; } /** * Complete graph structure for testing. */ declare interface TestGraph_2 { nodes: TestNode[]; edges: TestEdge[]; spec: GraphSpec_2; } /** * Node in a generated test graph. */ declare interface TestNode { id: string; type?: string; data?: Record; partition?: "left" | "right"; } /** * Node pair for testing path ranking algorithms. */ declare interface TestNodePair { /** Source node ID (as it appears in the graph) */ source: string; /** Target node ID (as it appears in the graph) */ target: string; /** Optional description of this pair (e.g., "central characters", "peripheral nodes") */ description?: string; } /** Threshold graph property (split + cograph) */ export declare type Threshold = { kind: "threshold"; } | { kind: "non_threshold"; } | { kind: "unconstrained"; }; /** * Convert positioned nodes to a node position map for react-force-graph * @param layoutResult */ export declare const toNodePositionMap: (layoutResult: HierarchicalLayoutResult) => Map; /** Topological minor-free: excludes specific subdivisions */ export declare type TopologicalMinorFree = { kind: "topological_minor_free"; forbiddenMinors: string[]; } | { kind: "not_topological_minor_free"; } | { kind: "unconstrained"; }; /** * Topological sort using DFS-based reverse postorder. * * Returns a linear ordering of vertices such that for every directed edge (u, v), * u comes before v in the ordering. Only works on Directed Acyclic Graphs (DAGs). * * Time Complexity: O(V + E) * Space Complexity: O(V) * @param graph - The directed graph to sort * @returns Result containing ordered nodes or cycle error */ export declare const topologicalSort: (graph: Graph) => Result; /** Toroidal graph property (grid on torus) */ export declare type Toroidal = { kind: "toroidal"; rows: number; cols: number; } | { kind: "not_toroidal"; } | { kind: "unconstrained"; }; /** * Graph Products and Related Structures * * Graph products, minor-free graphs, and specialized graph structures. */ /** Toughness: minimum k such that removing k vertices disconnects */ export declare type Toughness = { kind: "toughness"; value: number; } | { kind: "unconstrained"; }; /** Tournament property (complete oriented graph) */ export declare type Tournament = { kind: "tournament"; } | { kind: "not_tournament"; } | { kind: "unconstrained"; }; /** Hamiltonian path property */ export declare type Traceable = { kind: "traceable"; } | { kind: "non_traceable"; } | { kind: "unconstrained"; }; /** * Information-theoretic path ranking using mutual information. * * Ranks paths between two nodes based on the geometric mean of mutual * information along their edges, with an optional length penalty. * * Supports: * - **Traversal modes**: Directed or undirected traversal (independent of graph structure) * - **Weight modes**: None, divide by mean weight, or multiplicative penalty * - **Length penalty**: Exponential penalty for longer paths * * @module pathfinding/path-ranking */ /** * Traversal mode determines how edges are traversed during path finding. * * This is INDEPENDENT of the graph's inherent directionality: * - **directed**: Only traverse edges in their natural direction * - On directed graph: Follow edge direction strictly * - On undirected graph: Treat as ordered sequence * - **undirected**: Traverse edges in both directions * - On directed graph: Can go against edge direction * - On undirected graph: Bidirectional (default behaviour) */ export declare type TraversalMode = "directed" | "undirected"; export declare interface TraversalResult { /** Nodes in visitation order (level-by-level for BFS) */ visitOrder: N[]; /** Parent mapping for path reconstruction (child → parent) */ parents: Map; } export declare const tree: TreeSpec; /** Tree specification */ export declare type TreeSpec = GraphSpec_2 & Readonly<{ directionality: { kind: "undirected"; }; cycles: { kind: "acyclic"; }; connectivity: { kind: "connected"; }; edgeMultiplicity: { kind: "simple"; }; selfLoops: { kind: "disallowed"; }; }>; /** Treewidth property (how tree-like the graph is) */ export declare type Treewidth = { kind: "treewidth"; width: number; } | { kind: "unconstrained"; }; /** * Triangle motif (3-clique) in undirected graph. * Represents three mutually connected nodes. */ export declare interface Triangle { /** Three nodes forming the triangle */ nodes: [N, N, N]; } /** * Configuration for triple/knowledge graph loading */ export declare interface TripleConfig { /** Delimiter between fields (default: tab) */ delimiter?: string | RegExp; /** Whether to skip lines starting with # (default: true) */ skipComments?: boolean; /** Number of header lines to skip (default: 0) */ headerLines?: number; /** Column index for head entity (default: 0) */ headColumn?: number; /** Column index for relation (default: 1) */ relationColumn?: number; /** Column index for tail entity (default: 2) */ tailColumn?: number; } /** Edge uncertainty */ export declare type Uncertainty = { kind: "deterministic"; } | { kind: "probabilistic"; } | { kind: "fuzzy"; }; export declare const unique: (xs: readonly T[]) => T[]; /** * Unit disk graph property * Graph formed by unit disks in the plane */ export declare type UnitDisk = { kind: "unit_disk"; unitRadius?: number; spaceSize?: number; } | { kind: "not_unit_disk"; } | { kind: "unconstrained"; }; /** * Update ClusterMetrics with per-community density values. * * Modifies community objects to include their individual density scores. * @template N - Node type * @template E - Edge type * @param graph - Input graph * @param communities - Array of communities (modified in place) * @example * ```typescript * const communities: Community[] = [...]; * updateCommunityDensities(graph, communities); * // Now each community has updated 'density' field * ``` */ export declare const updateCommunityDensities: (graph: Graph, communities: Community[]) => void; export declare interface UrlFormatOptions { /** Include id_ suffix for raw content without Wayback toolbar (default: true) */ raw?: boolean; } /** * Validate algebraic connectivity (Fiedler value, λ₂ of Laplacian). * Algebraic connectivity measures how well-connected the graph is. * Higher values indicate better connectivity. * @param graph */ export declare const validateAlgebraicConnectivity: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate arc-transitive (symmetric) graph property. * Arc-transitive graphs are both vertex-transitive AND edge-transitive. * @param graph */ export declare const validateArcTransitive: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate ATFree property. * No asteroidal triple of vertices * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateATFree: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate that a loaded benchmark matches expected properties. * * @param benchmark - Loaded benchmark * @param tolerance - Allowed percentage difference (default 5%) * @returns Validation result with any warnings */ export declare const validateBenchmark: (benchmark: LoadedBenchmark, tolerance?: number) => { valid: boolean; warnings: string[]; }; /** * Validates whether a graph is bipartite using BFS-based coloring. * * A graph is bipartite if its vertices can be divided into two disjoint sets * such that every edge connects a vertex in one set to a vertex in the other. * Equivalently, the graph contains no odd-length cycles. * * @param graph - The graph to validate * @returns PropertyValidationResult with validation details */ export declare const validateBipartite: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate BullFree property. * Contains no induced bull graph * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateBullFree: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate C5Free property. * Contains no induced cycle on 5 vertices * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateC5Free: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate cage graph classification. * Cage graphs have minimal vertices for given (girth, degree). * These are extremely rare - we check metadata rather than actual structure. * @param graph */ export declare const validateCage: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate Cartesian product classification. * Cartesian product G □ H combines two graphs. * We check metadata rather than actual product structure. * @param graph */ export declare const validateCartesianProduct: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates chordal graph property. * Chordal graphs have no induced cycles > 3 (all cycles have chords). * @param graph */ export declare const validateChordal: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate CircularArc property. * Intersection graph of arcs on a circle * @param graph * @param _adjustments */ export declare const validateCircularArc: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate circumference property. * Circumference is the length of the longest cycle. * @param graph */ export declare const validateCircumference: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates claw-free property. * Claw-free = no induced K_{1,3} (star with 3 leaves). * * @param graph - The graph to validate * @returns PropertyValidationResult with validation details */ export declare const validateClawFree: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates cograph property (P4-free). * Cographs contain no induced path on 4 vertices (P4). * * @param graph - The graph to validate * @returns PropertyValidationResult with validation details */ export declare const validateCograph: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates comparability graph property. * Comparability graphs = transitively orientable graphs (from partial orders). * @param graph */ export declare const validateComparability: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph connectivity matches spec. * Uses BFS to check if all nodes are reachable from the first node. * * @param graph - Test graph to validate * @returns Validation result for connectivity property */ export declare const validateConnectivity: (graph: TestGraph) => PropertyValidationResult_2; /** * Validate graph cyclicity matches spec. * Uses DFS to detect cycles in directed graphs. * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments for constrained graphs * @returns Validation result for cycles property */ export declare const validateCycles: (graph: TestGraph, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validates graph density and completeness properties. * * A complete graph has density = 1.0 (all possible edges exist). * Density = (2 * |E|) / (|V| * (|V| - 1)) for undirected graphs. * * @param graph - The graph to validate * @param adjustments - Optional validation adjustments for constrained graphs * @returns PropertyValidationResult with validation details */ export declare const validateDensityAndCompleteness: (graph: TestGraph_2, adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate diameter property. * Diameter is the longest shortest path between any two vertices. * @param graph */ export declare const validateDiameter: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph directionality matches spec. * Checks that edge structure corresponds to directed vs undirected specification. * * @param graph - Test graph to validate * @returns Validation result for directionality property */ export declare const validateDirectionality: (graph: TestGraph) => PropertyValidationResult_2; /** * Validate DistanceHereditary property. * Distances preserved in all connected induced subgraphs * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateDistanceHereditary: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate domination number (γ). * Domination number is the minimum vertices such that every vertex is either * in the dominating set or adjacent to a vertex in the set. * @param graph */ export declare const validateDominationNumber: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph edge multiplicity matches spec. * Checks for parallel edges between the same pair of nodes. * * @param graph - Test graph to validate * @returns Validation result for edge multiplicity property */ export declare const validateEdgeMultiplicity: (graph: TestGraph) => PropertyValidationResult_2; /** * Validate edge-transitive graph property. * Edge-transitive graphs have automorphisms mapping any edge to any other. * @param graph */ export declare const validateEdgeTransitive: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate Eulerian graph properties. * Eulerian graphs have all vertices with even degree (Eulerian circuit exists). * Semi-Eulerian graphs have exactly 2 vertices with odd degree (Eulerian trail exists). * @param graph */ export declare const validateEulerian: (graph: TestGraph_2) => { property: string; expected: string; actual: string; valid: boolean; message?: string; }; /** * Validate flow network properties. * * A flow network must satisfy: * 1. Directed graph with source and sink nodes * 2. Non-negative edge capacities (weights) * 3. Every node lies on some path from source to sink * 4. No edges enter the source * 5. No edges leave the sink * * @param graph - The graph to validate * @returns PropertyValidationResult with flow network validation */ export declare const validateFlowNetwork: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate GemFree property. * Contains no induced gem graph * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateGemFree: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate girth property. * Girth is the length of the shortest cycle. * @param graph */ export declare const validateGirth: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate Hamiltonian graph property. * Hamiltonian graphs contain a cycle visiting every vertex exactly once. * @param graph */ export declare const validateHamiltonian: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate hereditary class property. * Hereditary classes are closed under taking induced subgraphs. * @param graph */ export declare const validateHereditaryClass: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate HHFree property. * No induced house or hole (cycle of length >= 5) * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateHHFree: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate independence number (α). * Independence number is the size of the largest independent set (no two vertices adjacent). * @param graph */ export declare const validateIndependenceNumber: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph integrity. * Integrity measures resilience based on vertex removal. * Minimizes (removed vertices + largest remaining component). * @param graph */ export declare const validateIntegrity: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates interval graph property. * Interval graphs = intersection graphs of intervals on real line. * @param graph */ export declare const validateInterval: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate k-colorable property of a graph. * A graph is k-colorable if its vertices can be colored with k colors * such that no two adjacent vertices share the same color. * * This function uses a greedy coloring algorithm as an upper bound, * which gives us an approximation of the chromatic number χ(G). * If greedy uses > k colors, the graph is definitely not k-colorable. * If greedy uses ≤ k colors, we verify the coloring is valid. * * @param graph - The test graph to validate * @returns PropertyValidationResult with k-colorable validation */ export declare const validateKColorable: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate k-edge-connected property. * A graph is k-edge-connected if it has at least k+1 vertices and * cannot be disconnected by removing fewer than k edges. * * Note: Full validation requires checking all edge cut sets, * which is expensive. For our purposes, we verify: * 1. At least k+1 vertices * 2. Minimum degree ≥ k (necessary and sufficient for many graphs) * 3. Graph is connected * @param graph */ export declare const validateKEdgeConnected: (graph: TestGraph_2) => PropertyValidationResult_3; /** * Validate k-vertex-connected property. * A graph is k-vertex-connected if it has at least k+1 vertices and * cannot be disconnected by removing fewer than k vertices. * * Note: Full validation requires checking all (n choose k) vertex subsets, * which is expensive. For our purposes, we verify: * 1. At least k+1 vertices * 2. Minimum degree ≥ k (necessary condition) * 3. Graph is connected * @param graph */ export declare const validateKVertexConnected: (graph: TestGraph_2) => PropertyValidationResult_3; /** * Validate lexicographic product classification. * Lexicographic product G ∘ H combines two graphs. * We check metadata rather than actual product structure. * @param graph */ export declare const validateLexicographicProduct: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate line graph property. * Line graph L(G) represents adjacency of edges in base graph G. * @param graph */ export declare const validateLine: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate minor-free graph classification. * Minor-free graphs exclude specific graph minors (Kuratowski-Wagner theorem). * We check metadata rather than actual minor-free structure. * @param graph */ export declare const validateMinorFree: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates modular graph property (community structure). * Modular graphs have high modularity score Q. * @param graph */ export declare const validateModular: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate Modular property. * Every module is trivial * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateModularClass: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate Moore graph classification. * Moore graphs achieve maximum vertices for given (diameter, degree). * These are extremely rare - we check metadata rather than actual structure. * @param graph */ export declare const validateMooreGraph: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate P5Free property. * Contains no induced path on 5 vertices * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateP5Free: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validates perfect graph property. * Perfect graphs = ω(H) = χ(H) for all induced subgraphs H. * @param graph */ export declare const validatePerfect: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates permutation graph property. * Permutation graphs = graphs from permutation π with edge (i,j) iff (i-j)(π(i)-π(j)) < 0. * @param graph */ export declare const validatePermutation: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate planar graph property. * Planar graphs can be drawn in the plane without edge crossings. * @param graph */ export declare const validatePlanar: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate ProbeChordal property. * Vertices partitioned into probes and non-probes, can add edges among non-probes to make chordal * @param graph * @param _adjustments */ export declare const validateProbeChordal: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate ProbeInterval property. * Can add edges among non-probes to form interval graph * @param graph * @param _adjustments */ export declare const validateProbeInterval: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate ProperCircularArc property. * Circular arc graph with no arc containment * @param graph * @param _adjustments */ export declare const validateProperCircularArc: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate Ptolemaic property. * Distance hereditary and chordal * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validatePtolemaic: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate QuasiLine property. * No induced gem, no co-gem * * @param graph - Test graph to validate * @param _adjustments - Optional validation adjustments * @returns PropertyValidationResult for validation details */ export declare const validateQuasiLine: (graph: TestGraph_2, _adjustments?: Partial>) => PropertyValidationResult_2; /** * Validate radius property. * Radius is the minimum eccentricity among all vertices. * @param graph */ export declare const validateRadius: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate Ramanujan graph classification. * Ramanujan graphs are optimal expanders with spectral gap property. * We check metadata and spectral properties. * @param graph */ export declare const validateRamanujan: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate regular graph properties (cubic or k-regular). * A k-regular graph has all vertices with degree exactly k. * Cubic graphs are 3-regular. * @param graph */ export declare const validateRegularGraph: (graph: TestGraph_2) => { property: string; expected: string; actual: string; valid: boolean; message?: string; }; /** * Validates scale-free graph property. * Scale-free graphs have power-law degree distribution P(k) ~ k^(-γ). * @param graph */ export declare const validateScaleFree: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph schema homogeneity matches spec. * Checks whether nodes and edges have uniform types. * * @param graph - Test graph to validate * @returns Validation result for schema property */ export declare const validateSchema: (graph: TestGraph) => PropertyValidationResult_2; /** * Validate self-complementary property. * Self-complementary graph is isomorphic to its complement. * @param graph */ export declare const validateSelfComplementary: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph self-loop property matches spec. * Checks for edges where source equals target. * * @param graph - Test graph to validate * @returns Validation result for self-loops property */ export declare const validateSelfLoops: (graph: TestGraph) => PropertyValidationResult_2; /** * Validates small-world graph property. * Small-world graphs have high clustering coefficient + short average path length. * @param graph */ export declare const validateSmallWorld: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate spectral radius (largest eigenvalue). * Spectral radius relates to graph expansion and mixing rate. * For adjacency matrix, it bounds the maximum degree. * @param graph */ export declare const validateSpectralRadius: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph spectrum (full set of eigenvalues). * Uses spectral radius approximation for validation. * @param graph */ export declare const validateSpectrum: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates split graph property. * Split graph = vertices can be partitioned into clique K and independent set I. * * @param graph - The graph to validate * @returns PropertyValidationResult with validation details */ export declare const validateSplit: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate strongly regular graph property. * Strongly regular graphs have parameters (n, k, λ, μ). * @param graph */ export declare const validateStronglyRegular: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate strong product classification. * Strong product G ⊠ H combines two graphs. * We check metadata rather than actual product structure. * @param graph */ export declare const validateStrongProduct: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate tensor (direct) product classification. * Tensor product G × H combines two graphs. * We check metadata rather than actual product structure. * @param graph */ export declare const validateTensorProduct: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate threshold graph property. * Threshold graphs are both split and cograph. * @param graph */ export declare const validateThreshold: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate topological minor-free graph classification. * Topological minor-free graphs exclude specific subdivisions. * We check metadata rather than actual structure. * @param graph */ export declare const validateTopologicalMinorFree: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph toughness. * Toughness measures minimum ratio of removed vertices to resulting components. * Higher values indicate more robust graphs. * @param graph */ export declare const validateToughness: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validates tournament graph properties. * * A tournament is a complete directed graph where for every pair of vertices * (u, v), exactly one of (u, v) or (v, u) is an edge. Every tournament has * a Hamiltonian path. * * Properties checked: * 1. Completeness: For every pair of distinct vertices, exactly one directed edge exists * 2. No self-loops * 3. No parallel edges in opposite directions * * @param graph - The graph to validate * @returns PropertyValidationResult with validation details */ export declare const validateTournament: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate traceable graph property. * Traceable graphs contain a Hamiltonian path (visiting all vertices exactly once). * @param graph */ export declare const validateTraceable: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate that a graph has treewidth ≤ specified bound. * * Treewidth measures how "tree-like" a graph is: * - Trees and forests have treewidth 0 * - Series-parallel graphs have treewidth ≤ 2 * - k-trees have treewidth exactly k * * This function uses an approximation algorithm based on: * 1. Finding a elimination ordering * 2. Computing the maximum clique size in the filled graph * 3. Treewidth = max_clique_size - 1 * * @param graph - Test graph to validate * @returns PropertyValidationResult with treewidth validation */ export declare const validateTreewidth: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate unit disk graph property. * Unit disk graphs are defined by geometric constraints (points within radius). * @param graph */ export declare const validateUnitDisk: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate vertex cover number (τ). * Vertex cover number is the minimum vertices covering all edges. * @param graph */ export declare const validateVertexCover: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate vertex-transitive graph property. * Vertex-transitive graphs have automorphism group acting transitively on vertices. * @param graph */ export declare const validateVertexTransitive: (graph: TestGraph_2) => PropertyValidationResult_2; /** * Validate graph weighting matches spec. * Checks that all edges have appropriate weight values. * * @param graph - Test graph to validate * @returns Validation result for weighting property */ export declare const validateWeighting: (graph: TestGraph) => PropertyValidationResult_2; /** * Advanced Graph Properties * * Extended property axes for future graph generation capabilities. */ /** Vertex set cardinality */ export declare type VertexCardinality = { kind: "finite"; n?: number; } | { kind: "countably_infinite"; } | { kind: "uncountably_infinite"; }; /** Vertex cover number (τ): minimum vertices covering all edges */ export declare type VertexCover = { kind: "vertex_cover"; value: number; } | { kind: "unconstrained"; }; /** Vertex metadata */ export declare type VertexData = { kind: "unlabelled"; } | { kind: "labelled"; } | { kind: "attributed"; }; /** Vertex identity */ export declare type VertexIdentity = { kind: "distinguishable"; } | { kind: "indistinguishable"; }; /** Vertex ordering */ export declare type VertexOrdering = { kind: "unordered"; } | { kind: "total_order"; } | { kind: "partial_order"; }; /** Vertex-transitive property (automorphisms can map any vertex to any other) */ export declare type VertexTransitive = { kind: "vertex_transitive"; } | { kind: "not_vertex_transitive"; } | { kind: "unconstrained"; }; export declare interface WaybackOptions extends UrlFormatOptions { maxRetries?: number; userAgent?: string; } /** No hole or antihole of length >= 5 */ declare type WeaklyChordal = { kind: "weakly_chordal"; } | { kind: "has_hole_or_antihole"; } | { kind: "unconstrained"; }; /** * Rank paths by sum of edge weights. * For weighted graphs only. * * @param paths - Paths to rank * @param weightFn - Function to extract weight from edge * @param weightFunction * @returns Paths sorted by total weight (descending) */ export declare const weightBasedRanker: (paths: Path[], weightFunction: (edge: E) => number) => RankedPath[]; export declare const weightedDirectedNetwork: WeightedDirectedNetworkSpec; /** Weighted directed network */ export declare type WeightedDirectedNetworkSpec = GraphSpec_2 & Readonly<{ directionality: { kind: "directed"; }; weighting: { kind: "weighted_numeric"; }; }>; /** * Weight function that extracts weight from an edge and optionally considers source/target nodes. * * This allows flexible weight calculation based on: * - Edge attributes: `(edge) => edge.customCost` * - Node attributes: `(edge, source, target) => source.elevation - target.elevation` * - Combined: `(edge, source, target) => edge.distance * target.difficulty` * @param edge - The edge being traversed * @param sourceNode - The source node of the edge * @param targetNode - The target node of the edge * @returns The numeric weight for this edge (must be non-negative for Dijkstra) * @example * ```typescript * // Use custom edge attribute * const edgeCostFn: WeightFunction = (edge) => edge.cost; * * // Use node elevation difference * const elevationFn: WeightFunction = (edge, source, target) => * Math.abs(source.elevation - target.elevation); * * // Combine edge distance with target difficulty * const complexFn: WeightFunction = (edge, source, target) => * edge.distance * (target.difficulty ?? 1); * ``` */ export declare type WeightFunction = (edge: E, sourceNode: N, targetNode: N) => number; /** Edge weighting property */ export declare type Weighting = { kind: "unweighted"; } | { kind: "weighted_numeric"; } | { kind: "weighted_vector"; } | { kind: "valued_symbolic"; }; /** * Weight mode determines how edge weights affect path scoring. * * - **none**: Ignore edge weights (default) * - **divide**: Divide MI score by arithmetic mean of edge weights * Score = geometric_mean(MI) / arithmetic_mean(weights) * - **multiplicative**: Apply multiplicative penalty from weights * Score = geometric_mean(MI) × exp(-mean(log(weights))) */ export declare type WeightMode = "none" | "divide" | "multiplicative"; /** Wheel graph property (cycle + central hub connected to all) */ export declare type Wheel = { kind: "wheel"; } | { kind: "not_wheel"; } | { kind: "unconstrained"; }; /** * Wilcoxon signed-rank test (non-parametric alternative to paired t-test). * * Tests whether the distribution of differences is symmetric about zero. * Does NOT assume normal distribution, making it more robust for small samples. * * @param method1Results - Results from method 1 across experiments * @param method2Results - Results from method 2 across experiments * @param alpha - Significance level (default: 0.05) * @returns p-value, test statistic (W), and significance * * @example * ```typescript * const miScores = [0.85, 0.82, 0.88, 0.90, 0.87]; * const baselineScores = [0.65, 0.70, 0.68, 0.72, 0.69]; * const result = wilcoxonSignedRank(miScores, baselineScores); * console.log(result.pValue); // e.g., 0.031 (significant at α=0.05) * ``` */ export declare const wilcoxonSignedRank: (method1Results: number[], method2Results: number[], alpha?: number) => { pValue: number; statistic: number; significant: boolean; }; export { }