import { Graph } from '../graph/graph';
import { Edge, Node } from '../types/graph';
/**
 * Mutual information computation for graph edges.
 *
 * Provides multiple computation strategies that automatically adapt to graph properties:
 * 1. **Attribute-based**: When nodes have attributes, computes MI from attribute correlation
 * 2. **Node type-based**: For heterogeneous node types, computes MI from type co-occurrence rarity
 * 3. **Edge type-based**: For heterogeneous edge types, computes MI from edge type rarity
 * 4. **Structural**: Falls back to Jaccard similarity of neighbourhoods
 *
 * Additional modifiers that multiply the base MI:
 * - **Temporal**: Edge stability/recency modifier
 * - **Signed**: Positive/negative edge modifier
 * - **Probabilistic**: Edge probability modifier
 * - **Community**: Same-community boost modifier
 * - **Multiplex**: Aggregates MI across layers
 * - **Hypergraph**: Handles hyperedges connecting multiple nodes
 *
 * @module pathfinding/mutual-information
 */
/**
 * Configuration for mutual information computation.
 * @template N - Node type extending base Node
 * @template E - Edge type extending base Edge
 */
export interface MutualInformationConfig<N extends Node, E extends Edge = Edge> {
    /**
     * Extract numeric attributes from a node for MI computation.
     * If not provided, structural similarity is used.
     * @param node - The node to extract attributes from
     * @returns Array of numeric attribute values, or undefined if no attributes
     */
    attributeExtractor?: (node: N) => number[] | undefined;
    /**
     * Extract community/cluster identifier from a node.
     * Edges within the same community get boosted MI.
     * @param node - The node to extract community from
     * @returns Community identifier, or undefined if not clustered
     */
    communityExtractor?: (node: N) => string | number | undefined;
    /**
     * Extract layer identifier from an edge for multiplex graphs.
     * MI is aggregated across layers using geometric mean.
     * @param edge - The edge to extract layer from
     * @returns Layer identifier, or undefined if single-layer
     */
    layerExtractor?: (edge: E) => string | number | undefined;
    /**
     * Extract timestamp from an edge for temporal graphs.
     * More recent edges get higher MI via temporal decay.
     * @param edge - The edge to extract timestamp from
     * @returns Unix timestamp, or undefined if static
     */
    timestampExtractor?: (edge: E) => number | undefined;
    /**
     * Extract sign from an edge for signed graphs.
     * Negative edges get penalized MI.
     * @param edge - The edge to extract sign from
     * @returns Sign value (positive > 0, negative < 0), or undefined if unsigned
     */
    signExtractor?: (edge: E) => number | undefined;
    /**
     * Extract probability from an edge for probabilistic graphs.
     * MI is multiplied by edge probability.
     * @param edge - The edge to extract probability from
     * @returns Probability in [0, 1], or undefined if deterministic
     */
    probabilityExtractor?: (edge: E) => number | undefined;
    /**
     * Extract hyperedge node IDs for hypergraph edges.
     * Returns all nodes connected by this hyperedge (beyond source/target).
     * @param edge - The edge to extract hyperedge nodes from
     * @returns Array of additional node IDs, or undefined if simple edge
     */
    hyperedgeExtractor?: (edge: E) => string[] | undefined;
    /**
     * Whether to use edge types for MI computation in heterogeneous edge graphs.
     * @default false (auto-detected)
     */
    useEdgeTypes?: boolean;
    /**
     * Boost factor for edges within the same community.
     * MI is multiplied by (1 + communityBoost) for same-community edges.
     * @default 0.5
     */
    communityBoost?: number;
    /**
     * Penalty factor for negative edges in signed graphs.
     * Negative edges have MI multiplied by (1 - negativePenalty).
     * @default 0.5
     */
    negativePenalty?: number;
    /**
     * Decay rate for temporal MI modifier.
     * MI_temporal = exp(-temporalDecay * age) where age is time since referenceTime.
     * @default 0.001
     */
    temporalDecay?: number;
    /**
     * Reference time for temporal decay computation (Unix timestamp).
     * @default Date.now()
     */
    referenceTime?: number;
    /**
     * Small constant added to avoid log(0).
     * @default 1e-10
     */
    epsilon?: number;
    /**
     * Enable degree-based penalty to reduce MI for high-degree nodes (hubs).
     * Penalizes edges connected to nodes with many connections.
     * @default false
     */
    useDegreeBasedPenalty?: boolean;
    /**
     * Penalty factor for degree-based MI reduction.
     * MI_adjusted = MI_base × exp(-degreeBasedPenaltyFactor × (log(deg(u)+1) + log(deg(v)+1)))
     * Higher values = stronger penalty for high-degree nodes.
     * @default 0.5
     */
    degreeBasedPenaltyFactor?: number;
    /**
     * Enable IDF-style weighting to reduce MI for high-degree nodes.
     * Uses inverse document frequency formula from information retrieval.
     * MI_adjusted = MI_base × log(N/(deg(u)+1)) × log(N/(deg(v)+1))
     * @default false
     */
    useIDFWeighting?: boolean;
    /**
     * Enable edge type rarity penalty.
     * Penalizes common edge types (like "has_concept") and boosts rare ones.
     * MI_adjusted = MI_base × (-log(P(edge_type)))
     * @default false
     */
    useEdgeTypeRarity?: boolean;
}
/**
 * Pre-computed mutual information cache for a graph.
 * Stores MI values keyed by edge ID for O(1) lookup during path ranking.
 */
export interface MutualInformationCache {
    /**
     * Get the MI value for an edge.
     * @param edgeId - The edge identifier
     * @returns MI value, or undefined if not cached
     */
    get(edgeId: string): number | undefined;
    /**
     * Get all cached edge IDs.
     */
    keys(): IterableIterator<string>;
    /**
     * Number of cached entries.
     */
    readonly size: number;
}
/**
 * Pre-compute mutual information for all edges in a graph.
 *
 * Automatically selects the appropriate MI computation method based on
 * graph properties:
 * 1. If attributeExtractor is provided and returns values, use attribute-based MI
 * 2. If nodes have diverse types, use node type-based MI
 * 3. If useEdgeTypes is enabled or edges have diverse types, use edge type-based MI
 * 4. Otherwise, fall back to structural (Jaccard) MI
 *
 * Additional modifiers are applied multiplicatively:
 * - Temporal: Edge recency modifier
 * - Signed: Negative edge penalty modifier
 * - Probabilistic: Edge probability modifier
 * - Community: Same-community boost modifier
 * - Multiplex: Geometric mean across layers
 * - Hypergraph: Pairwise aggregation across hyperedge nodes
 *
 * Time Complexity: O(E × avg_degree) for structural MI, O(E) for attribute/type MI
 * Space Complexity: O(E) for the cache
 *
 * @template N - Node type
 * @template E - Edge type
 * @param graph - The graph to analyse
 * @param config - Optional configuration for MI computation
 * @returns Cache of pre-computed MI values keyed by edge ID
 *
 * @example
 * ```typescript
 * const graph = new Graph<MyNode, MyEdge>(true);
 * // ... add nodes and edges ...
 *
 * // With attribute extractor
 * const cache = precomputeMutualInformation(graph, {
 *   attributeExtractor: (node) => [node.value, node.weight]
 * });
 *
 * // With temporal decay
 * const cache = precomputeMutualInformation(graph, {
 *   timestampExtractor: (edge) => edge.timestamp,
 *   temporalDecay: 0.001,
 *   referenceTime: Date.now()
 * });
 *
 * // Without attributes (uses structural similarity)
 * const cache = precomputeMutualInformation(graph);
 *
 * // Get MI for an edge
 * const mi = cache.get('edge-1'); // number | undefined
 * ```
 */
export declare const precomputeMutualInformation: <N extends Node, E extends Edge>(graph: Graph<N, E>, config?: MutualInformationConfig<N, E>) => MutualInformationCache;
/**
 * Compute mutual information for a single edge.
 *
 * This is a convenience function for computing MI for individual edges
 * without pre-computing the entire graph. For ranking multiple paths,
 * use `precomputeMutualInformation` instead for better performance.
 *
 * Note: This function only supports attribute-based and structural MI.
 * For full modifier support (temporal, signed, probabilistic, etc.),
 * use `precomputeMutualInformation` which applies all modifiers.
 *
 * @template N - Node type
 * @template E - Edge type
 * @param graph - The graph containing the edge
 * @param edge - The edge to compute MI for
 * @param config - Optional configuration
 * @returns MI value for the edge
 */
export declare const computeEdgeMI: <N extends Node, E extends Edge>(graph: Graph<N, E>, edge: E, config?: MutualInformationConfig<N, E>) => number;
//# sourceMappingURL=mutual-information.d.ts.map