/**
 * Graph Optimization — Max-Flow/Min-Cut, A* Search, Hungarian Assignment
 *
 * Complements the existing traversal/shortest-path/centrality graph
 * functions (`typed/graph.ts`, `graph/traversal-centrality.ts`) with
 * classic combinatorial-optimization algorithms:
 *
 * - `maxFlow` / `minCut`: Edmonds-Karp max-flow (BFS shortest-augmenting-path
 *   on the residual graph) and the corresponding min-cut via the
 *   max-flow-min-cut theorem.
 * - `astar`: heuristic-guided shortest path on a weighted adjacency matrix;
 *   reduces to Dijkstra when the heuristic is the zero function.
 * - `hungarian`: Kuhn-Munkres optimal assignment minimizing total cost on a
 *   square cost matrix.
 *
 * Input format: adjacency/capacity/cost matrices as `number[][]`, matching
 * the convention used elsewhere in this directory.
 *
 * @packageDocumentation
 */
/** Result of `maxFlow`. */
export interface MaxFlowResult {
    /** Total maximum flow value from `source` to `sink`. */
    maxFlow: number;
    /** Flow matrix: `flow[i][j]` is the net flow sent along edge i -> j. */
    flow: number[][];
}
/**
 * Maximum flow from `source` to `sink` via the Edmonds-Karp algorithm
 * (Ford-Fulkerson with BFS shortest-augmenting-path selection).
 *
 * Time complexity: O(V*E^2) (O(V^5) on a dense adjacency matrix).
 *
 * @param capacity - Capacity matrix (directed reading; `capacity[i][j]` is
 *   the capacity of edge i -> j; 0 or negative means no edge)
 * @param source - Source node index
 * @param sink - Sink node index
 * @returns `{ maxFlow, flow }`
 *
 * @example
 * const cap = [[0,3,2,0],[0,0,1,2],[0,0,0,3],[0,0,0,0]];
 * maxFlow(cap, 0, 3).maxFlow // => 5
 */
export declare function maxFlow(capacity: number[][], source: number, sink: number): MaxFlowResult;
/** Result of `minCut`. */
export interface MinCutResult {
    /** Value of the minimum cut (equals the maximum flow value). */
    value: number;
    /** `[S, T]` partition: `S` reachable from `source` in the residual
     * graph after saturating max-flow, `T` the rest. */
    partition: [number[], number[]];
}
/**
 * Minimum s-t cut, computed via the max-flow-min-cut theorem: run
 * `maxFlow`, then BFS the residual graph from `source` — reachable nodes
 * form the source-side partition `S`, the rest form `T`.
 *
 * @param capacity - Capacity matrix (directed reading)
 * @param source - Source node index
 * @param sink - Sink node index
 * @returns `{ value, partition: [S, T] }`
 *
 * @example
 * const cap = [[0,3,2,0],[0,0,1,2],[0,0,0,3],[0,0,0,0]];
 * minCut(cap, 0, 3) // => { value: 5, partition: [[0, ...], [...]] }
 */
export declare function minCut(capacity: number[][], source: number, sink: number): MinCutResult;
/** Result of `astar`. */
export interface AStarResult {
    /** Node sequence from `start` to `goal` (empty if unreachable). */
    path: number[];
    /** Total path cost (Infinity if unreachable). */
    cost: number;
}
/**
 * A* shortest path on a weighted adjacency matrix, guided by `heuristic`
 * (an admissible estimate of the remaining cost to `goal`). With
 * `heuristic = () => 0` this reduces to Dijkstra's algorithm.
 *
 * A directed edge i -> j exists when `adj[i][j]` is finite and nonzero.
 *
 * @param adj - Adjacency matrix (directed reading; edge weights should be
 *   non-negative for optimality)
 * @param start - Source node index
 * @param goal - Target node index
 * @param heuristic - `(node) => estimated cost from node to goal`
 * @returns `{ path, cost }`; `{ path: [], cost: Infinity }` if unreachable
 *
 * @example
 * const adj = [[0,1,4],[1,0,1],[4,1,0]];
 * astar(adj, 0, 2, () => 0) // => { path: [0, 1, 2], cost: 2 }
 */
export declare function astar(adj: number[][], start: number, goal: number, heuristic: (node: number) => number): AStarResult;
/** Result of `hungarian`. */
export interface HungarianResult {
    /** `assignment[i]` is the column assigned to row i. */
    assignment: number[];
    /** Total cost of the optimal assignment. */
    cost: number;
}
/**
 * Optimal assignment minimizing total cost, via the Kuhn-Munkres
 * (Hungarian) algorithm on a square cost matrix. Uses the O(n^3)
 * Jonker-Volgenant-style potential/shortest-augmenting-path formulation
 * (1-indexed internally per the classical presentation).
 *
 * @param cost - Square cost matrix (`cost[i][j]` = cost of assigning row i
 *   to column j)
 * @returns `{ assignment, cost }`
 *
 * @example
 * hungarian([[4,1,3],[2,0,5],[3,2,2]])
 * // => { assignment: [1, 0, 2], cost: 5 } (scipy linear_sum_assignment)
 */
export declare function hungarian(cost: number[][]): HungarianResult;
//# sourceMappingURL=optimization.d.ts.map