import { Graph } from '../graph/graph';
import { Path } from '../types/algorithm-results';
import { GraphError } from '../types/errors';
import { Edge, Node } from '../types/graph';
import { Option } from '../types/option';
import { Result } from '../types/result';
import { MutualInformationCache, MutualInformationConfig } from './mutual-information';
/**
 * Information-theoretic path ranking using mutual information.
 *
 * Ranks paths between two nodes based on the geometric mean of mutual
 * information along their edges, with an optional length penalty.
 *
 * Supports:
 * - **Traversal modes**: Directed or undirected traversal (independent of graph structure)
 * - **Weight modes**: None, divide by mean weight, or multiplicative penalty
 * - **Length penalty**: Exponential penalty for longer paths
 *
 * @module pathfinding/path-ranking
 */
/**
 * Traversal mode determines how edges are traversed during path finding.
 *
 * This is INDEPENDENT of the graph's inherent directionality:
 * - **directed**: Only traverse edges in their natural direction
 *   - On directed graph: Follow edge direction strictly
 *   - On undirected graph: Treat as ordered sequence
 * - **undirected**: Traverse edges in both directions
 *   - On directed graph: Can go against edge direction
 *   - On undirected graph: Bidirectional (default behaviour)
 */
export type TraversalMode = "directed" | "undirected";
/**
 * Weight mode determines how edge weights affect path scoring.
 *
 * - **none**: Ignore edge weights (default)
 * - **divide**: Divide MI score by arithmetic mean of edge weights
 *   Score = geometric_mean(MI) / arithmetic_mean(weights)
 * - **multiplicative**: Apply multiplicative penalty from weights
 *   Score = geometric_mean(MI) × exp(-mean(log(weights)))
 */
export type WeightMode = "none" | "divide" | "multiplicative";
/**
 * A ranked path with its computed score.
 * @template N - Node type
 * @template E - Edge type
 */
export interface RankedPath<N extends Node, E extends Edge> {
    /** The path (nodes and edges) */
    path: Path<N, E>;
    /** Information-theoretic ranking score M(P) */
    score: number;
    /** Geometric mean of MI values along the path (before length penalty) */
    geometricMeanMI: number;
    /** Individual MI values for each edge in the path */
    edgeMIValues: number[];
    /** Length penalty factor exp(-λk), only present if lambda > 0 */
    lengthPenalty?: number;
    /** Weight factor applied to score, only present if weightMode != 'none' */
    weightFactor?: number;
}
/**
 * Configuration for path ranking.
 * @template N - Node type
 * @template E - Edge type
 */
export interface PathRankingConfig<N extends Node, E extends Edge = Edge> {
    /**
     * Traversal mode for path finding.
     * - 'directed': Only traverse edges in their natural direction
     * - 'undirected': Traverse edges in both directions (default)
     * @default 'undirected'
     */
    traversalMode?: TraversalMode;
    /**
     * Length penalty parameter λ.
     * - λ = 0: Path length irrelevant, purely information quality (default)
     * - λ > 0: Longer paths penalised exponentially
     * - λ → ∞: Reduces to shortest path selection
     * @default 0
     */
    lambda?: number;
    /**
     * Weight mode for incorporating edge weights.
     * - 'none': Ignore weights (default)
     * - 'divide': Divide score by mean weight
     * - 'multiplicative': Apply multiplicative weight penalty
     * @default 'none'
     */
    weightMode?: WeightMode;
    /**
     * Extract weight from an edge.
     * If not provided, uses edge.weight property (defaulting to 1).
     */
    weightExtractor?: (edge: E) => number;
    /**
     * Maximum number of paths to return.
     * @default 10
     */
    maxPaths?: number;
    /**
     * Maximum path length to consider.
     * Prevents exponential blowup in dense graphs.
     * Only used when shortestOnly is false.
     * @default Infinity
     */
    maxLength?: number;
    /**
     * Whether to only consider shortest paths.
     * - true (default): Only enumerate paths of minimum length (backwards compatible)
     * - false: Enumerate all paths up to maxLength, letting MI + λ determine ranking
     *
     * When false, the λ (lambda) parameter becomes meaningful:
     * - λ = 0: Pure MI quality, length irrelevant (may prefer longer paths)
     * - λ > 0: Trade-off between MI quality and path efficiency
     * - λ → ∞: Effectively reduces to shortest path selection
     *
     * @default true
     */
    shortestOnly?: boolean;
    /**
     * Pre-computed MI cache. If not provided, MI will be computed on-demand.
     * For ranking multiple path queries on the same graph, pre-compute once
     * and pass the cache here for better performance.
     */
    miCache?: MutualInformationCache;
    /**
     * Configuration for MI computation (only used if miCache not provided).
     */
    miConfig?: MutualInformationConfig<N, E>;
    /**
     * Small constant to avoid log(0).
     * @default 1e-10
     */
    epsilon?: number;
}
/**
 * Rank paths between two nodes using information-theoretic scoring.
 *
 * Finds all shortest paths between source and target, then ranks them
 * by the geometric mean of mutual information along their edges.
 *
 * **Formula**: M(P) = exp((1/k) × Σᵢ log I(uᵢ; vᵢ)) × exp(-λk)
 *
 * Time Complexity: O(V + E) for path finding + O(n × k) for scoring n paths of length k
 * Space Complexity: O(V + E) for BFS + O(E) for MI cache
 *
 * @template N - Node type
 * @template E - Edge type
 * @param graph - The graph to search
 * @param startId - Source node ID
 * @param endId - Target node ID
 * @param config - Optional configuration
 * @returns Result containing ranked paths or error
 *
 * @example
 * ```typescript
 * const graph = new Graph<MyNode, MyEdge>(false);
 * // ... add nodes and edges ...
 *
 * // Basic usage: rank all shortest paths
 * const result = rankPaths(graph, 'A', 'Z');
 * if (result.ok && result.value.some) {
 *   const ranked = result.value.value;
 *   console.log('Best path:', ranked[0].path.nodes.map(n => n.id).join(' -> '));
 *   console.log('Score:', ranked[0].score);
 * }
 *
 * // With custom MI computation
 * const result = rankPaths(graph, 'A', 'Z', {
 *   miConfig: {
 *     attributeExtractor: (node) => [node.value, node.weight]
 *   },
 *   lambda: 0.1,  // Slight penalty for longer paths
 *   maxPaths: 5
 * });
 * ```
 */
export declare const rankPaths: <N extends Node, E extends Edge>(graph: Graph<N, E>, startId: string, endId: string, config?: PathRankingConfig<N, E>) => Result<Option<RankedPath<N, E>[]>, GraphError>;
/**
 * Get the best (highest-ranked) path between two nodes.
 *
 * Convenience function that returns only the top-ranked path.
 *
 * @template N - Node type
 * @template E - Edge type
 * @param graph - The graph to search
 * @param startId - Source node ID
 * @param endId - Target node ID
 * @param config - Optional configuration
 * @returns Result containing best path or error
 *
 * @example
 * ```typescript
 * const result = getBestPath(graph, 'A', 'Z');
 * if (result.ok && result.value.some) {
 *   const best = result.value.value;
 *   console.log('Best path score:', best.score);
 * }
 * ```
 */
export declare const getBestPath: <N extends Node, E extends Edge>(graph: Graph<N, E>, startId: string, endId: string, config?: PathRankingConfig<N, E>) => Result<Option<RankedPath<N, E>>, GraphError>;
/**
 * Create a reusable path ranker with pre-computed MI cache.
 *
 * For ranking paths across multiple queries on the same graph,
 * this is more efficient than calling rankPaths repeatedly.
 *
 * @template N - Node type
 * @template E - Edge type
 * @param graph - The graph to analyse
 * @param config - Configuration for MI computation
 * @returns Object with ranking methods that reuse the MI cache
 *
 * @example
 * ```typescript
 * // Pre-compute once
 * const ranker = createPathRanker(graph, {
 *   attributeExtractor: (node) => [node.value]
 * });
 *
 * // Use for multiple queries (reuses MI cache)
 * const result1 = ranker.rank('A', 'B');
 * const result2 = ranker.rank('C', 'D');
 * const result3 = ranker.getBest('E', 'F');
 * ```
 */
export declare const createPathRanker: <N extends Node, E extends Edge>(graph: Graph<N, E>, config?: Omit<PathRankingConfig<N, E>, "miCache">) => {
    /**
     * Rank paths between two nodes.
     * @param startId
     * @param endId
     * @param overrides
     */
    rank: (startId: string, endId: string, overrides?: Partial<PathRankingConfig<N, E>>) => Result<Option<RankedPath<N, E>[]>, GraphError>;
    /**
     * Get the best path between two nodes.
     * @param startId
     * @param endId
     * @param overrides
     */
    getBest: (startId: string, endId: string, overrides?: Partial<PathRankingConfig<N, E>>) => Result<Option<RankedPath<N, E>>, GraphError>;
    /**
     * Access the underlying MI cache.
     */
    getMICache: () => MutualInformationCache;
};
//# sourceMappingURL=path-ranking.d.ts.map