### Min Cost Flow API Source: https://github.com/vages/min-cost-flow/blob/master/README.md API documentation for min-cost flow algorithms. ```APIDOC minCostFlowForNumberNodes(graph, desiredFlow) - Computes the minimum cost flow for a given graph and desired flow amount. - Parameters: - graph: Array> - The graph represented as an edge list. - desiredFlow: number - The maximum flow to achieve. Defaults to Infinity. - Returns: Array> - The updated network with flow information. - Assumptions: - Nodes are sequentially numbered integers from 0 to n-1. - Node 0 is the source, node n-1 is the sink. - Only one edge exists between any two nodes in a given direction. cheapestPaths(adjacency, capacity, cost) - Calculates the cheapest paths from the source to all other nodes using the Bellman-Ford algorithm. - Parameters: - adjacency: Array> - Adjacency list representation of the graph. - capacity: Array> - n*n array representing edge capacities. - cost: Array> - n*n array representing edge costs per unit of flow. - Returns: Object - An object containing: - leastCosts: number[] - Array where leastCosts[x] is the minimum cost to reach node x. - predecessors: number[] - Array where predecessors[x] is the best predecessor of node x. - Related Functions: - minCostFlowForNumberNodes ``` -------------------------------- ### cheapestPaths Function Source: https://github.com/vages/min-cost-flow/blob/master/README.md Calculates the cheapest paths in a graph given adjacency, capacity, and cost. Returns an object containing the cheapest paths. ```javascript cheapestPaths(adjacency, capacity, cost) ⇒ Object ``` -------------------------------- ### minimumWeightBipartiteMatch Function Source: https://github.com/vages/min-cost-flow/blob/master/README.md Solves the minimum weight bipartite matching problem. It takes an array of edges and returns an array of BipartiteEdge. ```javascript minimumWeightBipartiteMatch(edges) ⇒ Array. ``` -------------------------------- ### Minimum Weight Bipartite Match Source: https://github.com/vages/min-cost-flow/blob/master/README.md Calculates the minimum weight bipartite match for a given graph by converting the problem into a minimum-cost flow problem. ```javascript /** * Finds a minimum weight bipartite match for a graph. * Converts the problem to a minimum-cost flow problem. * * @param {Array} edges - The entire weighted graph represented as weighted edges * @returns {Array} The edges that are part of the minimum bipartite match */ function minimumWeightBipartiteMatch(edges) { // Implementation details... } ``` -------------------------------- ### Minimum Weight Bipartite Matching Source: https://github.com/vages/min-cost-flow/blob/master/README.md Finds a minimum weight bipartite match for a given set of edges. This function converts the bipartite matching problem into a minimum-cost flow problem to find the optimal solution. ```javascript /** * Finds a minimum weight bipartite match for a graph. * Converts the problem to a minimum-cost flow problem. * * @param {Array} edges The edges of the bipartite graph. * @returns {Array} The edges forming the minimum weight match. */ function minimumWeightBipartiteMatch(edges) { // Implementation details... } ``` -------------------------------- ### Graph Stringification Utilities Source: https://github.com/vages/min-cost-flow/blob/master/README.md Provides functions to convert graphs between string-based node names and numerical indices. Assumes specific conventions for source and sink nodes. ```javascript /** * Takes a graph with edges going to and from nodes with string names and transforms it into a graph with numbered edges, * following the convention that the source node is the first node and the sink node the last. * It assumes that the source node's name is SOURCE and the sink node's name is SINK. * * @param {Array>} graph - A graph in the form of an edge list * @param {Object} options - An object with two (optional) keys: source and sink. If a value is supplied at this key, the function will assume that the source/sink node's name is equal to the supplied value. * @returns {Array} A two element tuple whose first element is the destringified graph and whose second element is the node names listed in the order in which they were named, so that the graph can be restringified by getting nodeNames[n] for any node in the destringified graph. */ function destringifyGraph(graph, options) { // Implementation details... } /** * Restringifies a graph that has been destringified by destringifyGraph * * @param {Array>} graph - The graph as an edge list * @param {Array} nodeNames - The names of each node, so that the name of the node numbered x can be found at nodeNames[x] * @returns {Array>} The restringified graph */ function restringifyGraph(graph, nodeNames) { // Implementation details... } ``` -------------------------------- ### Bellman-Ford Shortest Path Algorithm Source: https://github.com/vages/min-cost-flow/blob/master/README.md Implements the Bellman-Ford algorithm to find the cheapest paths from a source node to all other nodes in a network. It also determines the best predecessor for each node. This is a key component used in the minimum-cost flow calculations. ```javascript /** * Calculates the cheapest path from the source to every other node using the Bellman-Ford algorithm. * * @param {Array>} adjacency The adjacency list representing the graph. * @param {Array>} capacity The capacity matrix for the edges. * @param {Array>} cost The cost matrix for the edges. * @returns {Object} An object containing shortest path distances and predecessors. */ function cheapestPaths(adjacency, capacity, cost) { // Implementation details... } ``` -------------------------------- ### cheapestPaths (Bellman-Ford) Source: https://github.com/vages/min-cost-flow/blob/master/README.md Calculates the cheapest paths from a source node to all other nodes in a network using the Bellman-Ford algorithm. It also determines the best predecessor for each node, which is crucial for reconstructing the paths. This is a core component of the min-cost flow algorithm. ```javascript function cheapestPaths(adjacency, capacity, cost) { // Implementation details... return { leastCosts, predecessors }; } ``` -------------------------------- ### destringifyGraph Function Source: https://github.com/vages/min-cost-flow/blob/master/README.md Converts a stringified graph representation into a usable format. It takes the graph and options, returning an array. ```javascript destringifyGraph(graph, options) ⇒ Array ``` -------------------------------- ### minCostFlow Function Source: https://github.com/vages/min-cost-flow/blob/master/README.md Solves minimum-cost flow problems. It takes a graph and options as input and returns an array of required edges with string identifiers. ```javascript minCostFlow(graph, options) ⇒ Array.>> ``` -------------------------------- ### Core Min-Cost Flow Algorithm Source: https://github.com/vages/min-cost-flow/blob/master/README.md The underlying implementation of the successive shortest paths algorithm for minimum-cost flow. It operates on graphs with sequentially numbered nodes, assuming node 0 as the source and node n-1 as the sink. Similar to `minCostFlow`, it assumes no parallel edges between nodes in the same direction. ```javascript /** * The underlying implementation of the successive shortest paths algorithm. * * Assumptions: * - Nodes are sequentially numbered integers from 0 to n-1. * - Node 0 is the source, node n-1 is the sink. * - Only one edge goes between any two nodes – in either direction. * * @param {Array} graph The graph with numbered nodes. * @param {number} desiredFlow The desired amount of flow. * @returns {Array>} The resulting flow edges. */ function minCostFlowForNumberNodes(graph, desiredFlow) { // Implementation details... } ``` -------------------------------- ### minCostFlowForNumberNodes Source: https://github.com/vages/min-cost-flow/blob/master/README.md Implements the successive shortest paths algorithm for min-cost flow. It assumes nodes are numbered 0 to n-1, with 0 as the source and n-1 as the sink. The algorithm stops when the desired flow is reached or no more augmenting paths can be found. ```javascript function minCostFlowForNumberNodes(graph, desiredFlow) { // Implementation details... return updatedGraph; } ``` -------------------------------- ### Min-Cost Flow Calculation Source: https://github.com/vages/min-cost-flow/blob/master/README.md Solves a minimum-cost flow problem using the successive shortest paths algorithm. This function acts as a wrapper, handling graph destringification, calling the core algorithm, and then restringifying the results. It assumes a graph structure where only one edge exists between any two nodes in a given direction. ```javascript /** * Solves a minimum-cost flow problem using the successive shortest paths algorithm. * Assumes that only one edge goes between any two nodes – in either direction. * The function is a wrapper that destringifies the graph, calls minCostFlowForNumberNodes on it and restringifies the result. * * @param {Array>} graph The graph represented as an edge list. * @param {MinCostFlowOptions} options An object with source (string), sink (string), and desiredFlow (number). * @returns {Array>>} The resulting flow edges. */ function minCostFlow(graph, options) { // Implementation details... } ``` -------------------------------- ### Graph Stringification Utilities Source: https://github.com/vages/min-cost-flow/blob/master/README.md Provides functions to convert between string-based node identifiers and numerical identifiers for graph representations. `destringifyGraph` transforms a graph with string node names (assuming 'SOURCE' and 'SINK') into a numerically indexed graph, while `restringifyGraph` reverses this process. ```javascript /** * Transforms a graph with string node names into a graph with numbered edges. * Assumes the source node's name is 'SOURCE' and the sink node's name is 'SINK'. * * @param {Array>} graph The graph with string node names. * @param {object} options Options for destringification. * @returns {Array} The destringified graph. */ function destringifyGraph(graph, options) { // Implementation details... } /** * Restringifies a graph that has been destringified. * * @param {Array} graph The destringified graph. * @param {Array} nodeNames The original node names. * @returns {Array>} The restringified graph. */ function restringifyGraph(graph, nodeNames) { // Implementation details... } ``` -------------------------------- ### restringifyGraph Function Source: https://github.com/vages/min-cost-flow/blob/master/README.md Converts a graph into a stringified format. It takes the graph and node names, returning an array of edges with string identifiers. ```javascript restringifyGraph(graph, nodeNames) ⇒ Array.> ``` -------------------------------- ### minCostFlowForNumberNodes Function Source: https://github.com/vages/min-cost-flow/blob/master/README.md Solves minimum-cost flow problems for graphs with number nodes. It takes a graph and desired flow, returning an array of required edges. ```javascript minCostFlowForNumberNodes(graph, desiredFlow) ⇒ Array.> ``` -------------------------------- ### TypeScript Edge Type for Cost-Flow Networks Source: https://github.com/vages/min-cost-flow/blob/master/README.md Defines the structure for an edge in a cost-flow network, including source, destination, capacity, cost, and optional flow. This type is essential for formulating and solving minimum-cost flow problems. ```typescript export type Edge = { from: T; to: T; capacity: number; cost: number; flow?: number; }; ``` === COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.