import { GraphExpander } from '../../interfaces/graph-expander.js';
import { DegreePrioritisedExpansionResult } from './degree-prioritised-expansion.js';
/**
 * Configuration for Intelligent Delayed Termination.
 */
export 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;
}
/**
 * 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<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;
    /** 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<T>, 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<DegreePrioritisedExpansionResult>;
    /**
     * Detect if the active frontier has sufficient overlap with any other frontier.
     *
     * Uses Threshold Sharing strategy: Jaccard similarity >= overlapThreshold
     *
     * @param activeFrontier - The frontier that is expanding
     * @returns True if overlap detected with any frontier
     * @internal
     */
    private detectOverlap;
    /**
     * Calculate Jaccard similarity between two sets.
     *
     * J(A,B) = |A ∩ B| / |A ∪ B|
     *
     * @param setA - First set
     * @param setB - Second set
     * @returns Jaccard similarity coefficient [0, 1]
     * @internal
     */
    private calculateJaccardSimilarity;
    /**
     * Check if termination condition is met.
     *
     * @returns True if post-overlap iteration limit reached
     * @internal
     */
    private shouldTerminate;
    /**
     * Calculate priority for a node based on current phase.
     *
     * Phase 1: π(v) = deg(v)
     * Phase 2: π(v) = deg(v) × (1 - estimated_MI(v))
     *
     * Lower priority = higher importance (expanded first in min-heap).
     *
     * @param nodeId - Node to calculate priority for
     * @returns Priority value
     * @internal
     */
    private calculateNodePriority;
    /**
     * Transition from Phase 1 (degree-only) to Phase 2 (MI-guided).
     *
     * Recomputes priorities for all nodes in all frontiers based on the first
     * discovered path.
     *
     * @internal
     */
    private transitionToSaliencePhase;
    /**
     * Update MI estimates based on a newly discovered path.
     *
     * For each node in the graph, computes Jaccard similarity to the path nodes
     * and updates the estimated MI to the maximum Jaccard across all paths.
     *
     * @param pathNodes - Array of node IDs in the discovered path
     * @internal
     */
    private updateMIEstimates;
    /**
     * Compute Jaccard similarity between a node's neighbours and a set of path nodes.
     *
     * Jaccard(v, P) = |neighbors(v) ∩ nodes(P)| / |neighbors(v) ∪ nodes(P)|
     *
     * @param nodeId - Node to compute similarity for
     * @param pathNodes - Set of node IDs in the path
     * @returns Jaccard similarity in [0, 1]
     * @internal
     */
    private computeJaccardSimilarity;
    /**
     * Check if any frontier has unexpanded nodes.
     * @internal
     */
    private hasNonEmptyFrontier;
    /**
     * Select the frontier with the lowest-priority node at its front.
     * Returns -1 if all frontiers are empty.
     * @internal
     */
    private selectLowestPriorityFrontier;
    /**
     * 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).
     * @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=intelligent-delayed-termination.d.ts.map