import { GraphExpander } from '../../interfaces/graph-expander';
/**
 * Result from cross-seed-affinity expansion.
 */
export interface CrossSeedAffinityResult {
    /** Discovered paths (only populated when N >= 2 seeds) */
    paths: Array<{
        fromSeed: number;
        toSeed: number;
        nodes: string[];
    }>;
    /** Union of all nodes visited by all frontiers */
    sampledNodes: Set<string>;
    /** Set of edges visited during expansion */
    sampledEdges: Set<string>;
    /** Per-frontier visited sets (for diagnostics) */
    visitedPerFrontier: Array<Set<string>>;
    /** Statistics about the expansion */
    stats: CrossSeedAffinityStats;
    /** Maps node ID to the iteration when it was first discovered */
    nodeDiscoveryIteration: Map<string, number>;
}
/**
 * Statistics collected during cross-seed-affinity expansion.
 */
export interface CrossSeedAffinityStats {
    /** Total nodes expanded (popped from frontiers) */
    nodesExpanded: number;
    /** Total edges traversed */
    edgesTraversed: number;
    /** Iterations (single node expansions) performed */
    iterations: number;
    /** Breakdown of nodes by degree ranges */
    degreeDistribution: Map<string, number>;
    /** Distribution of frontier visit counts */
    frontierVisitDistribution: Map<number, number>;
}
/**
 * Cross-Seed-Affinity Bidirectional Expansion
 *
 * Baseline algorithm that prioritises nodes based on their cross-frontier
 * visibility. Nodes visited by multiple frontiers receive lower priority
 * (deferred expansion) relative to their degree, testing whether avoiding
 * "convergence zones" improves path diversity.
 *
 * **Priority Formula**:
 * π(v) = deg(v) / (1 + frontierCount(v))
 *
 * where frontierCount(v) is the number of frontiers that have visited node v.
 *
 * **Key Properties**:
 * - Prioritises low-degree nodes (like degree-prioritised)
 * - Further deprioritises nodes in multiple frontiers' visited sets
 * - Avoids convergence zones where frontiers would naturally meet
 * - Tests hypothesis: "Does deferring shared nodes improve diversity?"
 *
 * **Experimental Purpose**:
 * If cross-seed-affinity achieves better path diversity than simple
 * degree-prioritised expansion, this suggests frontier interaction awareness
 * is important. If not, simple degree ordering suffices.
 *
 * @template T - Type of node data returned by expander
 */
export declare class CrossSeedAffinityExpansion<T> {
    private readonly expander;
    private readonly seeds;
    private readonly frontiers;
    private readonly paths;
    private readonly sampledEdges;
    private readonly frontierVisitCounts;
    private stats;
    private readonly nodeDiscoveryIteration;
    /**
     * Create a new cross-seed-affinity 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).
     *
     * @returns Expansion results including paths and sampled subgraph
     */
    run(): Promise<CrossSeedAffinityResult>;
    /**
     * Compute cross-seed-affinity priority for a node.
     * Priority: π(v) = deg(v) / (1 + frontierCount(v))
     *
     * Lower degree = higher base priority (like degree-prioritised).
     * Nodes in more frontiers get penalised (lower effective priority).
     *
     * @param nodeId - Node to compute priority for
     * @returns Priority value (higher = should expand sooner)
     * @internal
     */
    private computeCrossSeedAffinityPriority;
    /**
     * Check if any frontier has unexpanded nodes.
     * @internal
     */
    private hasNonEmptyFrontier;
    /**
     * Select the next frontier with items (round-robin).
     * Returns -1 if all frontiers are empty.
     * @internal
     */
    private selectNextFrontier;
    /**
     * Reconstruct path from meeting point between two frontiers.
     * @param stateA
     * @param stateB
     * @param meetingNode
     * @internal
     */
    private reconstructPath;
    /**
     * Check if an equivalent path already exists.
     * @param fromSeed
     * @param toSeed
     * @param nodes
     * @internal
     */
    private pathExists;
    /**
     * Record degree in distribution histogram.
     * @param degree
     * @internal
     */
    private recordDegree;
    /**
     * Get histogram bucket for a degree value.
     * @param degree
     * @internal
     */
    private getDegreeBucket;
}
//# sourceMappingURL=cross-seed-affinity.d.ts.map