import { GraphExpander } from '../../../interfaces/graph-expander';
import { OverlapBasedExpansionResult } from './overlap-result.js';
import { BetweenGraphStrategy } from './strategies/between-graph/between-graph-strategy.js';
import { N1HandlingStrategy } from './strategies/n1-handling/n1-handling-strategy.js';
import { OverlapDetectionStrategy } from './strategies/overlap-detection/overlap-detection-strategy.js';
import { TerminationStrategy } from './strategies/termination/termination-strategy.js';
/**
 * Configuration for OverlapBasedExpansion.
 */
export interface OverlapBasedExpansionConfig {
    /**
     * Strategy for detecting overlap between seed search regions.
     */
    overlapDetection: OverlapDetectionStrategy;
    /**
     * Strategy for determining when expansion should terminate.
     */
    termination: TerminationStrategy;
    /**
     * Strategy for handling N=1 (single seed) scenario.
     */
    n1Handling: N1HandlingStrategy;
    /**
     * Strategy for extracting the between-graph subgraph.
     */
    betweenGraph: BetweenGraphStrategy;
    /**
     * Maximum iterations before forced termination (safety limit).
     * Default: Infinity (no limit unless strategy terminates).
     */
    maxIterations?: number;
    /**
     * Total nodes in graph (for N=1 coverage calculation).
     * Optional - only used if n1Handling strategy requires it.
     */
    totalNodes?: number;
}
/**
 * Overlap-Based Expansion
 *
 * **Thesis Alignment**: Extends the seed-bounded sampling concept with overlap-based
 * termination instead of frontier exhaustion. This enables efficient sampling of the
 * "between-graph" (region connecting N seeds) while preserving sufficient structure
 * for Path Salience ranking.
 *
 * **Key Design Properties**:
 * 1. **Overlap-based termination**: Stops when seed search regions sufficiently overlap
 * 2. **Strategy pattern architecture**: Modular dimensions for experimental comparison
 * 3. **N-seed generalisation**: Handles N=1 (ego-network), N=2 (bidirectional), N≥3
 * 4. **Degree prioritisation**: Expands globally lowest-degree node across all frontiers
 *
 * **Algorithm**:
 * ```
 * 1. Initialize N frontiers, one per seed
 * 2. While termination condition not met:
 *    a. Select frontier with lowest-degree node at front
 *    b. Pop and expand neighbors
 *    c. Detect overlaps using strategy
 *    d. Check termination condition
 * 3. Extract between-graph subgraph using strategy
 * ```
 *
 * @template T - Type of node data returned by expander
 */
export declare class OverlapBasedExpansion<T> {
    private readonly expander;
    private readonly seeds;
    private readonly config;
    private readonly frontiers;
    private readonly paths;
    private readonly sampledEdges;
    private readonly overlapEvents;
    private stats;
    private iteration;
    /** Tracks when each node was first discovered (iteration number) */
    private readonly nodeDiscoveryIteration;
    /** Track which frontier owns each node for O(1) overlap detection */
    private readonly nodeToFrontierIndex;
    /** Track path signatures for O(1) deduplication */
    private readonly pathSignatures;
    /** Overlap matrix: "0-1" → Set of meeting nodes */
    private readonly overlapMatrix;
    /**
     * Create a new overlap-based expansion.
     *
     * @param expander - Graph expander providing neighbour access
     * @param seeds - Array of seed node IDs (N ≥ 1)
     * @param config - Strategy configuration
     * @throws Error if no seeds provided
     */
    constructor(expander: GraphExpander<T>, seeds: readonly string[], config: OverlapBasedExpansionConfig);
    /**
     * Run the expansion to termination.
     *
     * @returns Expansion results including between-graph subgraph
     */
    run(): Promise<OverlapBasedExpansionResult>;
    /**
     * Run expansion for N=1 (single seed) scenario.
     *
     * Uses n1Handling strategy to determine when to terminate.
     *
     * @private
     */
    private runN1;
    /**
     * Run expansion for N≥2 scenario with overlap detection.
     *
     * @private
     */
    private runNPlus;
    /**
     * Expand a single node (used in N=1 case).
     *
     * @param node - Node to expand
     * @param frontier - Frontier state
     * @param frontierIndex - Index of the frontier
     * @private
     */
    private expandNode;
    /**
     * Build the final result with between-graph subgraph extraction.
     *
     * @param terminationReason - Reason for termination
     * @private
     */
    private buildResult;
    /**
     * Check if any frontier has unexpanded nodes.
     * @private
     */
    private hasNonEmptyFrontier;
    /**
     * Select the frontier with the lowest-degree node at its front.
     * Returns -1 if all frontiers are empty.
     * @private
     */
    private selectLowestDegreeFrontier;
    /**
     * Peek at the priority of the front item without removing it.
     * @param queue
     * @private
     */
    private peekPriority;
    /**
     * Reconstruct path from meeting point between two frontiers.
     * @param stateA
     * @param stateB
     * @param meetingNode
     * @private
     */
    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
     * @private
     */
    private createPathSignature;
    /**
     * Get matrix key for overlap tracking (always sorted).
     * @param a
     * @param b
     * @private
     */
    private getMatrixKey;
    /**
     * Record degree in distribution histogram.
     * @param degree
     * @private
     */
    private recordDegree;
    /**
     * Get histogram bucket for a degree value.
     * @param degree
     * @private
     */
    private getDegreeBucket;
}
//# sourceMappingURL=overlap-based-expansion.d.ts.map