import { GraphExpander } from '../../interfaces/graph-expander';
import { DegreePrioritisedExpansionResult } from './degree-prioritised-expansion';
/**
 * Configuration options for path-preserving expansion.
 */
export interface PathPreservingExpansionConfig {
    /**
     * Target number of paths to discover per pair of seeds.
     * When reached, the algorithm may terminate early.
     * Default: undefined (run to frontier exhaustion).
     */
    targetPathsPerPair?: number;
}
/**
 * Path-Preserving Multi-Frontier Expansion (PPME)
 *
 * **Thesis Alignment**: This is an advanced variant of degree-prioritised expansion
 * from Chapter 4 that explicitly penalizes nodes appearing in multiple frontiers to
 * preserve path diversity. It uses a modified priority function:
 *
 * π_PPME(v) = deg(v) / (1 + path_potential(v))
 *
 * where path_potential(v) counts how many of v's neighbours have been visited by
 * OTHER frontiers. This deferring strategy avoids converging on the same high-
 * connectivity nodes and produces more structurally diverse paths.
 *
 * **Design Motivation**:
 * In degree-prioritised expansion, multiple frontiers may converge on the same
 * high-degree nodes, producing paths that share significant overlap. PPME addresses
 * this by dynamically reducing the priority of nodes whose neighbours have already
 * been claimed by other frontiers, encouraging each frontier to explore distinct
 * regions of the graph.
 *
 * **Key Properties**:
 * 1. **Path diversity**: Frontiers naturally diverge by avoiding already-claimed regions
 * 2. **Parameter-free core**: Like degree-prioritised, no arbitrary cutoffs (optional
 *    targetPathsPerPair for early termination)
 * 3. **N-seed generalisation**: Works for N ≥ 1 with identical code path
 * 4. **Dynamic prioritisation**: Priority updates based on real-time frontier state
 *
 * **Algorithm**:
 * ```
 * 1. Initialize N frontiers, one per seed
 * 2. While any frontier is non-empty:
 *    a. Recompute priorities for frontier heads using π_PPME formula
 *    b. Select the frontier with the lowest-priority node at its front
 *    c. Pop that node and expand its neighbours
 *    d. For each new neighbour, check intersection with all other frontiers
 *    e. If intersection found, record path between the two seeds
 *    f. (Optional) Terminate early if targetPathsPerPair reached
 * 3. Return sampled subgraph (union of all visited nodes)
 * ```
 *
 * **Complexity**: O(E log V + V·D) where E = edges explored, V = vertices, D = avg degree
 * (additional D factor for path potential computation)
 *
 * @template T - Type of node data returned by expander
 * @example
 * ```typescript
 * const expansion = new PathPreservingExpansion(
 *   expander,
 *   ['seedA', 'seedB', 'seedC'],
 *   { targetPathsPerPair: 5 }
 * );
 * const result = await expansion.run();
 * console.log(`Found ${result.paths.length} diverse paths`);
 * console.log(`Sampled ${result.sampledNodes.size} nodes`);
 * ```
 *
 * @see DegreePrioritisedExpansion - Base algorithm without path-preservation penalty
 * @see BidirectionalBFS - Parameterised version for N=2 with resource constraints
 */
export declare class PathPreservingExpansion<T> {
    private readonly expander;
    private readonly seeds;
    private readonly config;
    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;
    /** Count of paths discovered per seed pair */
    private readonly pathCounts;
    /**
     * Create a new path-preserving expansion.
     *
     * @param expander - Graph expander providing neighbour access
     * @param seeds - Array of seed node IDs (N ≥ 1)
     * @param config - Optional configuration for early termination
     * @throws Error if no seeds provided
     */
    constructor(expander: GraphExpander<T>, seeds: readonly string[], config?: PathPreservingExpansionConfig);
    /**
     * Run the expansion to completion.
     *
     * Terminates when:
     * - All frontiers are exhausted (no unexpanded nodes remain), OR
     * - targetPathsPerPair reached for all seed pairs (if configured)
     *
     * @returns Expansion results including paths and sampled subgraph
     */
    run(): Promise<DegreePrioritisedExpansionResult>;
    /**
     * Calculate PPME priority for a node.
     *
     * π_PPME(v) = deg(v) / (1 + path_potential(v))
     *
     * where path_potential(v) is the count of v's neighbours that have been
     * visited by OTHER frontiers (not the current one).
     *
     * @param nodeId - Node to calculate priority for
     * @param currentFrontierIndex - Index of the frontier considering this node
     * @internal
     */
    private calculatePPMEPriority;
    /**
     * Compute path potential for a node: count of neighbours visited by OTHER frontiers.
     *
     * @param nodeId - Node to compute potential for
     * @param currentFrontierIndex - Index of the frontier considering this node
     * @internal
     */
    private computePathPotential;
    /**
     * Estimate graph distance between two nodes (simplified for path potential).
     * Returns 1 if nodes are likely neighbours, 0 otherwise.
     *
     * @param nodeA
     * @param nodeB
     * @internal
     */
    private estimateDistance;
    /**
     * Check if any frontier has unexpanded nodes.
     * @internal
     */
    private hasNonEmptyFrontier;
    /**
     * Check if early termination criteria are met.
     * @internal
     */
    private shouldTerminateEarly;
    /**
     * Get a canonical key for a seed pair (order-independent).
     * @param indexA
     * @param indexB
     * @internal
     */
    private getSeedPairKey;
    /**
     * Select the frontier with the lowest-PPME-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=path-preserving-expansion.d.ts.map