import { GraphExpander } from '../../interfaces/graph-expander';
/**
 * Result from degree-surprise expansion.
 */
export interface DegreeSurpriseResult {
    /** 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<string>;
    /** Set of edges visited during expansion */
    sampledEdges: Set<string>;
    /** Per-frontier visited sets (for diagnostics) */
    visitedPerFrontier: Array<Set<string>>;
    /** Statistics about the expansion */
    stats: DegreeSurpriseStats;
    /** Map from node ID to the iteration when it was first discovered */
    nodeDiscoveryIteration: Map<string, number>;
}
/**
 * Statistics collected during degree-surprise expansion.
 */
export interface DegreeSurpriseStats {
    /** 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<string, number>;
}
/**
 * Degree-Surprise Bidirectional Expansion
 *
 * Baseline algorithm that prioritises nodes whose degree deviates most from
 * the local degree expectation of their neighbourhood. This tests whether
 * local structural anomalies provide better sampling than raw degree values.
 *
 * **Priority Formula**:
 * π(v) = |deg(v) - E[deg(N(v))]| / std[deg(N(v))]
 *
 * where N(v) are the neighbours of v, E[·] is expectation, std[·] is standard deviation.
 *
 * **Key Properties**:
 * - Prioritises nodes that are structural outliers in their local neighbourhood
 * - Low-degree nodes in high-degree regions get high priority (and vice versa)
 * - Requires computing local degree statistics for each frontier node
 * - Terminates when all frontiers exhausted
 *
 * **Experimental Purpose**:
 * Compare local structural anomaly detection (degree surprise) against
 * global degree ordering (degree-prioritised expansion). If degree-surprise
 * achieves similar path diversity, local context matters more than global degree.
 *
 * @template T - Type of node data returned by expander
 */
export declare class DegreeSurpriseExpansion<T> {
    private readonly expander;
    private readonly seeds;
    private readonly frontiers;
    private readonly paths;
    private readonly sampledEdges;
    private stats;
    private readonly nodeDiscoveryIteration;
    /**
     * Create a new degree-surprise expansion.
     *
     * @param expander - Graph expander providing neighbour access
     * @param seeds - Array of seed node IDs (N >= 1)
     * @throws Error if no seeds provided
     */
    constructor(expander: GraphExpander<T>, seeds: readonly string[]);
    /**
     * 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<DegreeSurpriseResult>;
    /**
     * Compute degree surprise for a node.
     * Priority: π(v) = |deg(v) - E[deg(N(v))]| / std[deg(N(v))]
     *
     * @param nodeId - Node to compute surprise for
     * @returns Surprise value (higher = more anomalous)
     * @internal
     */
    private computeDegreeSurprise;
    /**
     * Check if any frontier has unexpanded nodes.
     * @internal
     */
    private hasNonEmptyFrontier;
    /**
     * Select the next frontier with items (round-robin).
     * Returns -1 if all frontiers are empty.
     * @internal
     */
    private selectNextFrontier;
    /**
     * Reconstruct path from meeting point between two frontiers.
     * @param stateA
     * @param stateB
     * @param meetingNode
     * @internal
     */
    private reconstructPath;
    /**
     * Check if an equivalent path already exists.
     * @param fromSeed
     * @param toSeed
     * @param nodes
     * @internal
     */
    private pathExists;
    /**
     * Record degree in distribution histogram.
     * @param degree
     * @internal
     */
    private recordDegree;
    /**
     * Get histogram bucket for a degree value.
     * @param degree
     * @internal
     */
    private getDegreeBucket;
}
//# sourceMappingURL=degree-surprise.d.ts.map