import { GraphExpander } from '../../interfaces/graph-expander';
/**
 * Result from standard BFS expansion - matches DegreePrioritisedExpansionResult.
 */
export 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<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: BfsExpansionStats;
    /**
     * Maps each sampled node to the iteration when it was first discovered.
     * Used for computing coverage efficiency metrics.
     */
    nodeDiscoveryIteration: Map<string, number>;
}
/**
 * Statistics collected during BFS expansion.
 */
export 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<string, number>;
}
/**
 * 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<T> {
    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;
    /**
     * Create a new standard BFS 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<StandardBfsResult>;
    /**
     * 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=standard-bfs.d.ts.map