import { GraphExpander } from '../../interfaces/graph-expander';
/**
 * Result from delayed-termination expansion.
 */
export interface DelayedTerminationResult {
    /** 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: DelayedTerminationStats;
    /** Map from node ID to the iteration at which it was first discovered */
    nodeDiscoveryIteration: Map<string, number>;
}
/**
 * Statistics collected during delayed-termination expansion.
 */
export interface DelayedTerminationStats {
    /** 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>;
    /** Iteration at which first overlap was detected */
    firstOverlapIteration: number;
    /** Total additional iterations after first overlap */
    delayedIterations: number;
}
/**
 * Configuration for delayed termination.
 */
export interface DelayedTerminationConfig {
    /** Number of additional iterations after first overlap (default: 100) */
    delayIterations: number;
}
/**
 * Delayed-Termination Bidirectional BFS
 *
 * Extends overlap-based termination by continuing expansion for N additional
 * iterations after the first overlap is detected. This baseline tests whether
 * the degree-prioritised algorithm's benefits come from deferred termination
 * rather than the degree heuristic itself.
 *
 * **Key Properties**:
 * - FIFO expansion order (standard BFS)
 * - Detects first overlap between any two frontiers
 * - Continues for N additional iterations after overlap
 * - Tests hypothesis: "Does delayed termination alone improve diversity?"
 *
 * **Experimental Purpose**:
 * If delayed-termination BFS achieves similar path diversity to degree-prioritised
 * expansion, this suggests termination timing (not degree ordering) drives diversity.
 * If degree-prioritised still outperforms delayed BFS, the degree heuristic provides
 * value beyond simply deferring termination.
 *
 * @template T - Type of node data returned by expander
 */
export declare class DelayedTerminationExpansion<T> {
    private readonly expander;
    private readonly seeds;
    private readonly config;
    private readonly frontiers;
    private readonly paths;
    private readonly sampledEdges;
    private readonly nodeDiscoveryIteration;
    private stats;
    private firstOverlapIteration;
    private remainingDelayIterations;
    /**
     * Create a new delayed-termination expansion.
     *
     * @param expander - Graph expander providing neighbour access
     * @param seeds - Array of seed node IDs (N >= 1)
     * @param config - Configuration for delay iterations
     * @throws Error if no seeds provided
     */
    constructor(expander: GraphExpander<T>, seeds: readonly string[], config?: DelayedTerminationConfig);
    /**
     * Run the expansion to completion.
     *
     * Terminates when delay iterations are exhausted after first overlap,
     * or when all frontiers are exhausted (whichever comes first).
     *
     * @returns Expansion results including paths and sampled subgraph
     */
    run(): Promise<DelayedTerminationResult>;
    /**
     * 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=delayed-termination.d.ts.map