/**
 * Generic graph traversal over arbitrary semirings.
 *
 * The core insight: shortest path, most-trusted path, cheapest path,
 * most reliable path, and reachability are ALL the same algorithm.
 * The semiring determines the answer.
 *
 * Bellman-Ford generalized: relax edges using ⊕ (choice) and ⊗ (composition).
 * Floyd-Warshall generalized: all-pairs transitive closure.
 *
 * These are the only two traversal algorithms the system needs.
 * Every routing query is a semiring instantiation of one of them.
 */
import type { WeightedDigraph } from "./graph.js";
/**
 * Single-source optimal paths via generalized Bellman-Ford.
 *
 * Returns a map from each reachable node to the optimal semiring value
 * of the best path from `source` to that node.
 *
 * - Over TrustSemiring: most trusted delegation chain from source
 * - Over CostSemiring:  cheapest pipeline from source
 * - Over BooleanSemiring: reachable set from source
 * - Over product semiring: all of the above simultaneously
 *
 * Complexity: O(V × E) — safe for graphs with negative-weight analogs
 * (semirings where ⊕ is not monotone). For monotone semirings
 * (trust, cost), could be optimized to Dijkstra-like O((V+E) log V).
 */
export declare function optimalPaths<T>(graph: WeightedDigraph<T>, source: string): Map<string, T>;
/**
 * Optimal path between two specific nodes.
 * Convenience wrapper around optimalPaths.
 */
export declare function optimalPath<T>(graph: WeightedDigraph<T>, source: string, target: string): T;
/**
 * All-pairs transitive closure via generalized Floyd-Warshall.
 *
 * Computes the optimal semiring value between every pair of nodes.
 * Returns a nested map: closure.get(from)?.get(to) → optimal value.
 *
 * Use cases:
 *   - Pre-compute all trust relationships in a network
 *   - Find all cheapest routes for capacity planning
 *   - Detect isolated subgraphs (boolean semiring)
 *
 * Complexity: O(V³). Use optimalPaths for single-source queries on large graphs.
 */
export declare function transitiveClosure<T>(graph: WeightedDigraph<T>): Map<string, Map<string, T>>;
/**
 * Reconstruct the actual optimal path (sequence of node IDs).
 *
 * Returns null if no path exists (value equals semiring zero).
 * Runs a modified Bellman-Ford that tracks predecessors.
 */
export declare function optimalPathTrace<T>(graph: WeightedDigraph<T>, source: string, target: string): {
    value: T;
    path: string[];
} | null;
//# sourceMappingURL=traversal.d.ts.map