import { GraphExpander } from '../../interfaces/graph-expander';
/**
 * Result from degree-prioritised expansion.
 */
export 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<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: 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<string, number>;
}
/**
 * Statistics collected during expansion.
 */
export 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<string, 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<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;
    /** Track which frontier owns each node for O(1) intersection checking */
    private readonly nodeToFrontierIndex;
    /** Track path signatures for O(1) deduplication */
    private readonly pathSignatures;
    /**
     * Create a new degree-prioritised 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).
     * This is the ONLY termination condition—no arbitrary limits.
     *
     * @returns Expansion results including paths and sampled subgraph
     */
    run(): Promise<DegreePrioritisedExpansionResult>;
    /**
     * Check if any frontier has unexpanded nodes.
     * @internal
     */
    private hasNonEmptyFrontier;
    /**
     * Select the frontier with the lowest-degree node at its front.
     * Returns -1 if all frontiers are empty.
     * @internal
     */
    private selectLowestDegreeFrontier;
    /**
     * Peek at the priority of the front item without removing it.
     * @param queue
     * @internal
     */
    private peekPriority;
    /**
     * Reconstruct path from meeting point between two frontiers.
     * @param stateA
     * @param stateB
     * @param meetingNode
     * @internal
     */
    private reconstructPath;
    /**
     * Create a unique signature for a path to enable O(1) deduplication.
     * Signature is bidirectional (A-B same as B-A) and includes the actual
     * node sequence to distinguish different paths with the same length.
     * @param fromSeed
     * @param toSeed
     * @param nodes
     * @internal
     */
    private createPathSignature;
    /**
     * Record degree in distribution histogram.
     * @param degree
     * @internal
     */
    private recordDegree;
    /**
     * Get histogram bucket for a degree value.
     * @param degree
     * @internal
     */
    private getDegreeBucket;
}
//# sourceMappingURL=degree-prioritised-expansion.d.ts.map