import { GraphExpander } from '../../interfaces/graph-expander';
import { DegreePrioritisedExpansionResult } from './degree-prioritised-expansion';
/**
 * Entropy-Guided Expansion (EGE)
 *
 * **Thesis Alignment**: This is an experimental variant of the seed-bounded
 * sampling algorithm that uses local neighbourhood entropy to guide expansion
 * instead of simple degree prioritisation.
 *
 * **Design Motivation**:
 * - DegreePrioritisedExpansion: Defers hubs using degree alone
 * - EntropyGuidedExpansion: Incorporates neighbourhood diversity via entropy
 *
 * Use this implementation when:
 * - Neighbourhood diversity should influence exploration order
 * - Homogeneous neighbourhoods (low entropy) should be explored first
 * - Heterogeneous neighbourhoods (high entropy) should be deferred
 *
 * **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. **Entropy-based prioritisation**: Priority π_EGE(v) = (1 / (H_local(v) + ε)) × log(deg(v) + 1)
 *    where H_local(v) is Shannon entropy of neighbour type distribution.
 * 4. **Hub deferral maintained**: log(deg + 1) term preserves degree-based ordering.
 *
 * **Algorithm**:
 * ```
 * 1. Initialize N frontiers, one per seed
 * 2. While any frontier is non-empty:
 *    a. Select the frontier with the lowest entropy-weighted 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)
 * ```
 *
 * **Priority Function**:
 * π_EGE(v) = (1 / (H_local(v) + ε)) × log(deg(v) + 1)
 *
 * Where:
 * - H_local(v) = -Σ p(τ) log p(τ) (Shannon entropy of neighbour types)
 * - p(τ) = proportion of neighbours with relationship type τ
 * - ε = 0.001 (prevents division by zero)
 * - deg(v) = total degree of node v
 *
 * **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 EntropyGuidedExpansion(expander, ['seedA', 'seedB']);
 * const result = await expansion.run();
 * console.log(`Found ${result.paths.length} paths`);
 * console.log(`Sampled ${result.sampledNodes.size} nodes`);
 * ```
 *
 * @see DegreePrioritisedExpansion - Base implementation using degree alone
 */
export declare class EntropyGuidedExpansion<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;
    /** Epsilon value to prevent division by zero in entropy calculation */
    private static readonly EPSILON;
    /**
     * Create a new entropy-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[]);
    /**
     * Compute local entropy H_local(v) for a node based on neighbour type distribution.
     *
     * H_local(v) = -Σ p(τ) log₂ p(τ)
     *
     * Where p(τ) is the proportion of neighbours with relationship type τ.
     *
     * @param nodeId - Node to compute entropy for
     * @returns Shannon entropy of neighbour type distribution
     * @internal
     */
    private computeLocalEntropy;
    /**
     * Calculate entropy-guided priority for a node.
     *
     * π_EGE(v) = (1 / (H_local(v) + ε)) × log(deg(v) + 1)
     *
     * Lower priority = explored first (min-heap behaviour).
     *
     * @param nodeId - Node to calculate priority for
     * @returns Priority value (lower = higher priority)
     * @internal
     */
    private calculateEntropyPriority;
    /**
     * Calculate entropy-guided priority for a node (async version).
     *
     * @param nodeId - Node to calculate priority for
     * @returns Priority value (lower = higher priority)
     * @internal
     */
    private calculateEntropyPriorityAsync;
    /**
     * 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 entropy-weighted node at its front.
     * Returns -1 if all frontiers are empty.
     * @internal
     */
    private selectLowestEntropyFrontier;
    /**
     * 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=entropy-guided-expansion.d.ts.map