import { GraphExpander } from '../../interfaces/graph-expander.js';
import { DegreePrioritisedExpansionResult } from './degree-prioritised-expansion.js';
/**
 * Retrospective Salience-Guided Expansion (RSGE)
 *
 * **Novel Contribution**: Self-correcting two-phase expansion that starts with
 * degree prioritisation and adaptively shifts to salience-aware expansion once
 * paths are discovered.
 *
 * **Key Innovation**: Unlike static prioritisation strategies (degree-only or
 * salience-only), RSGE dynamically adapts its expansion strategy based on the
 * quality of discovered paths. If early paths are low-salience, the algorithm
 * automatically diversifies exploration to find higher-quality paths.
 *
 * **Two-Phase Priority Function**:
 * - **Phase 1 (no paths yet)**: π(v) = deg(v) [ascending]
 *   - Pure degree prioritisation, identical to DegreePrioritisedExpansion
 *   - Defers high-degree nodes until paths are discovered
 * - **Phase 2 (paths exist)**: π(v) = deg(v) × (1 - estimated_MI(v)) [ascending]
 *   - Reduces priority (increases value) for nodes likely to be on high-MI paths
 *   - Nodes with estimated_MI near 1.0 get lowest priority values (expanded first)
 *   - Nodes with estimated_MI near 0.0 get priority near deg(v) (expanded later)
 *
 * **Rolling MI Estimation**:
 * - Uses Jaccard similarity between node neighbours and discovered path nodes
 * - Jaccard(v, P) = |neighbors(v) ∩ nodes(P)| / |neighbors(v) ∪ nodes(P)|
 * - Estimated MI(v) = max over all discovered paths of Jaccard(v, P)
 * - Higher Jaccard = node likely appears in similar high-quality paths
 *
 * **Self-Correcting Mechanism**:
 * - If early paths are low-salience (low Jaccard scores for their nodes), the
 *   algorithm diversifies by exploring nodes with low Jaccard similarity
 * - If early paths are high-salience, the algorithm continues exploring similar
 *   nodes to find more high-quality paths
 *
 * **Expected Behavior**:
 * - Higher salience coverage than pure degree prioritisation
 * - More efficient than salience-prioritised expansion (requires no pre-computation)
 * - Adaptive exploration balances hub avoidance with path quality
 *
 * **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 RetrospectiveSalienceExpansion<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 = salience-aware */
    private saliencePhaseActive;
    /**
     * Create a new retrospective salience-guided 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>;
    /**
     * 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 (salience-aware).
     *
     * 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=retrospective-salience-expansion.d.ts.map