import { GraphExpander } from '../../interfaces/graph-expander.js';
import { DegreePrioritisedExpansionResult } from './degree-prioritised-expansion.js';
/**
 * Configuration for MFASF algorithm.
 */
export interface MFASFConfig {
    /**
     * Minimum number of paths to discover before considering phase 3 termination.
     * @default 3
     */
    minPaths?: number;
    /**
     * Diversity threshold τ for phase 3 termination.
     * Diversity = |unique nodes in paths| / |total path nodes|
     * @default 0.5
     */
    diversityThreshold?: number;
    /**
     * Salience feedback weight λ for phase 2 priority.
     * Higher values give more weight to salience feedback.
     * @default 1.0
     */
    salienceFeedbackWeight?: number;
    /**
     * Rolling window size for salience plateau detection.
     * @default 5
     */
    plateauWindowSize?: number;
    /**
     * Threshold for salience plateau detection (relative change).
     * If salience improves by less than this ratio, consider plateaued.
     * @default 0.01
     */
    plateauThreshold?: number;
}
/**
 * Multi-Frontier Adaptive Salience-Feedback (MFASF)
 *
 * **Novel Contribution**: Three-phase adaptive expansion that dynamically adjusts
 * priority based on salience feedback from discovered paths, achieving higher
 * mean path salience than static prioritization strategies.
 *
 * **Key Innovation**: Unlike static prioritization (degree-only, salience-only),
 * MFASF adapts its exploration strategy based on real-time feedback from path
 * quality. The algorithm transitions through three phases:
 *
 * **Phase 1: Path Potential Discovery**
 * - Priority: π_MFASF_1(v) = deg(v) / (1 + path_potential(v))
 * - path_potential(v) = count of v's neighbours visited by OTHER frontiers
 * - Goal: Discover diverse connecting paths between seeds
 * - Duration: Until M paths discovered (M = minPaths config)
 *
 * **Phase 2: Salience Feedback Expansion**
 * - Priority: π_MFASF_2(v) = π_MFASF_1(v) × (1 + λ × salience_feedback(v))
 * - salience_feedback(v) = estimated MI based on similarity to high-salience paths
 * - Goal: Exploit discovered high-quality paths to find more
 * - Duration: Until salience plateau detected
 *
 * **Phase 3: Termination**
 * - Conditions: salience plateau reached AND diversity > τ AND |P| ≥ K
 * - salience plateau: mean salience not improving significantly over window
 * - diversity: ratio of unique nodes to total path nodes
 * - Goal: Ensure sufficient quality and diversity before termination
 *
 * **Expected Behavior**:
 * - Higher mean path salience than degree-prioritised expansion
 * - Better exploration efficiency (fewer nodes per salient path)
 * - Adaptive exploration balances exploitation and exploration
 *
 * **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 MultiFrontierAdaptiveExpansion<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;
    /** Current phase (1, 2, or 3) */
    private currentPhase;
    /** Salience feedback scores for nodes */
    private readonly salienceFeedback;
    /** Rolling window of mean salience values for plateau detection */
    private readonly salienceHistory;
    /** Cache of neighbor sets for path potential computation */
    private readonly neighborCache;
    /** Configuration with defaults applied */
    private readonly config;
    /**
     * Create a new multi-frontier adaptive expansion.
     *
     * @param expander - Graph expander providing neighbour access
     * @param seeds - Array of seed node IDs (N ≥ 1)
     * @param config - Optional configuration overrides
     * @throws Error if no seeds provided
     */
    constructor(expander: GraphExpander<T>, seeds: readonly string[], config?: MFASFConfig);
    /**
     * Calculate Phase 1 priority: π_MFASF_1(v) = deg(v) / (1 + path_potential(v))
     *
     * @param nodeId - Node to calculate priority for
     * @returns Priority value (lower = higher priority)
     * @internal
     */
    private calculatePhase1Priority;
    /**
     * Calculate Phase 2 priority: π_MFASF_2(v) = π_MFASF_1(v) × (1 + λ × salience_feedback(v))
     *
     * @param nodeId - Node to calculate priority for
     * @returns Priority value (lower = higher priority)
     * @internal
     */
    private calculatePhase2Priority;
    /**
     * Calculate priority based on current phase.
     *
     * @param nodeId - Node to calculate priority for
     * @returns Priority value
     * @internal
     */
    private calculateCurrentPriority;
    /**
     * Compute path potential for a node: count of neighbours visited by OTHER frontiers.
     *
     * @param nodeId - Node to compute potential for
     * @returns Path potential count
     * @internal
     */
    private computePathPotential;
    /**
     * Update salience feedback based on newly discovered path.
     *
     * For each node, computes similarity to path nodes and updates feedback score.
     *
     * @param pathNodes - Nodes in the discovered path
     * @param pathSalience - Estimated salience of the path
     * @internal
     */
    private updateSalienceFeedback;
    /**
     * Get neighbours for a node, caching for efficiency.
     *
     * @param nodeId - Node to get neighbours for
     * @returns Set of neighbour node IDs
     * @internal
     */
    private getOrCacheNeighbors;
    /**
     * Estimate salience for a path based on node degrees.
     *
     * Uses degree-based heuristic: paths through lower-degree nodes are typically
     * more salient (higher MI) because they represent more specific connections.
     *
     * @param pathNodes - Nodes in the path
     * @returns Estimated salience in [0, 1]
     * @internal
     */
    private estimatePathSalience;
    /**
     * Check if salience has plateaued (not improving significantly).
     *
     * @returns true if plateau detected
     * @internal
     */
    private isSaliencePlateaued;
    /**
     * Compute path diversity: ratio of unique nodes to total path nodes.
     *
     * @returns Diversity ratio in [0, 1]
     * @internal
     */
    private computePathDiversity;
    /**
     * Check phase transition and termination conditions.
     *
     * @returns true if expansion should terminate
     * @internal
     */
    private checkPhaseTransition;
    /**
     * Rebuild all frontier priorities after phase transition.
     *
     * @internal
     */
    private rebuildFrontierPriorities;
    /**
     * Run the expansion to completion.
     *
     * Transitions through three phases and terminates when phase 3 conditions met
     * or all frontiers are exhausted.
     *
     * @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-priority node at its front.
     * Returns -1 if all frontiers are empty.
     * @internal
     */
    private selectLowestPriorityFrontier;
    /**
     * Reconstruct path from meeting point between two frontiers.
     * @param stateA
     * @param stateB
     * @param meetingNode
     * @internal
     */
    private reconstructPath;
    /**
     * Create a unique signature for a path.
     * @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=multi-frontier-adaptive-expansion.d.ts.map