# min-cost-flow > Solves minimum-cost flow problems using the successive shortest paths algorithm Latest version **2.1.0** (published 2020-12-15) · MIT license · 0 weekly downloads ## Install ```sh npm install min-cost-flow pnpm add min-cost-flow yarn add min-cost-flow bun add min-cost-flow ``` ## Health **Score 15/100 (F)** — status: abandoned. Positive: no vulnerabilities. Warnings: low downloads; no types; no esm support. Negative: abandoned; low maintenance score. ## Facts | | | |---|---| | Version | 2.1.0 | | Published | 2020-12-15 | | First published | 2020-10-26 | | Weekly downloads | 0 | | License | MIT | | TypeScript types | none | | Module format | CommonJS | | Dependencies | 1 | | Unpacked size | 619.6 KB | | Known vulnerabilities | 0 | | Install scripts | no | | GitHub stars | 5 | | Author | Eirik Vågeskar | | Maintainers | vages | ## Links - npm: https://www.npmjs.com/package/min-cost-flow - Repository: https://github.com/Vages/min-cost-flow - Homepage: https://github.com/Vages/min-cost-flow#readme - Issues: https://github.com/Vages/min-cost-flow/issues - npm.io page: https://npm.io/package/min-cost-flow ## Dependencies (1) - [heap](https://npm.io/package/heap.md) ^0.2.6 ## Recent versions - 2.1.0 (latest) — 2020-12-15 - 2.0.1 — 2020-10-27 - 2.0.0 — 2020-10-27 - 1.0.3 — 2020-10-27 - 1.0.2 — 2020-10-27 - 1.0.1 — 2020-10-26 - 1.0.0 — 2020-10-26 ## README [![view on npm](http://img.shields.io/npm/v/min-cost-flow.svg)](https://www.npmjs.org/package/min-cost-flow) # min-cost-flow - [Minimum-cost flow problems](#minimum-cost-flow-problems) - [Solving assignment problems using minimum-cost flow](#solving-assignment-problems-using-minimum-cost-flow) - [Usage](#usage) - [Types](#types) - [Functions](#functions) - [minCostFlow(graph, options) ⇒ Array.<Required.<Edge.<string>>>](#mincostflowgraph-options-%E2%87%92-arrayltrequiredltedgeltstringgtgtgt) - [minCostFlowForNumberNodes(graph, desiredFlow) ⇒ Array.<Required.<Edge>>](#mincostflowfornumbernodesgraph-desiredflow-%E2%87%92-arrayltrequiredltedgegtgt) - [cheapestPaths(adjacency, capacity, cost) ⇒ Object](#cheapestpathsadjacency-capacity-cost-%E2%87%92-object) - [destringifyGraph(graph, options) ⇒ Array](#destringifygraphgraph-options-%E2%87%92-array) - [restringifyGraph(graph, nodeNames) ⇒ Array.<Edge.<string>>](#restringifygraphgraph-nodenames-%E2%87%92-arrayltedgeltstringgtgt) - [minimumWeightBipartiteMatch(edges) ⇒ Array.<BipartiteEdge>](#minimumweightbipartitematchedges-%E2%87%92-arrayltbipartiteedgegt) A package that solves [minimum-cost flow problems](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem) using the Successive Shortest Paths algorithm. ## Minimum-cost flow problems Minimum-cost flow problems are all about sending given number of units (or as many units as possible) through a [_flow network_](https://en.wikipedia.org/wiki/Flow_network): > In graph theory, a **flow network** (also known as a **transportation network**) is a directed graph where each edge > has a **capacity** and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the > edge. … A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, > unless it is a **source**, which has only outgoing flow, or **sink**, which has only incoming flow. A network can be > used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical > circuit, or anything similar in which something travels through a network of nodes. In a **_cost_ flow network**, we add the requirement all edges have a cost associated with sending one unit of flow through it. If an edge's cost is 4, sending 1 unit costs 4, sending 2 units costs 8, and so on. Below is an illustration of the solution to a flow problem in a network of Norwegian cities. - The network has a total flow of 2 units, limited by the edge from `trondheim` to `SINK`. - The cheapest route from from `SOURCE` to `trondheim` goes through `drammen`, but is limited by the edge from `SOURCE` to `drammen`. Therefore, one unit has to pass through the more expensive route via `oslo`. Bergen is even - Edge color explanation - Red indicates max flow (flow is equal to capacity) - Blue indicates some flow, but not maximum - Black edges have no flow ![An illustration of a minimum-cost flow problem using shipping between some norwegian cities](docs/city-flow.svg) ## Solving assignment problems using minimum-cost flow For those employed outside of plumbing, shipping and electronics, minimum-cost flow will probably be most useful as a way to match people to a limited number of resources in a way that gives the greatest overall satisfaction. This is known as the [_assignment problem_](https://en.wikipedia.org/wiki/Assignment_problem): > Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked > up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a > particular customer will depend on the time taken for the taxi to reach the pickup point. This is a _balanced_ > assignment problem. Its solution is whichever combination of taxis and customers results in the least total cost. > > Now, suppose that there are four taxis available, but still only three customers. This is an _unbalanced_ assignment > problem. An assignment problem such as this can be considered a graph problem, more specifically _minimum-weight bipartite matching_ problem (bipartite meaning that the nodes in the graph fall into two separate groups with all edges going between those two groups, and no edges within the groups). A minimum-weight bipartite matching problem can easily be solved by converting it to a minimum-cost flow problem. Below, you will find an illustration of the taxi example as the graph `G`. The nodes in group `A` are the taxis, and the nodes in group `B` are customers. `G` is bipartite, because it would be silly to have a taxi pick up a taxi. An edge goes from a taxi to a customer if there's any chance that the taxi can reach the customer, and the edge's weight is equal to the number of minutes before the taxi reaches the customer. The goal is to pick up all customers and achieve the lowest overall weight. Let us say that the overall weight is lowest if the first, third and fourth taxis pick up the first, second and third customer respectively. To the right of `G`, you will find the graph `G'`, which shows how the assignment problem should be converted to a minimum-cost flow-problem by treating the edges' weights as costs. ![Minimum weight bipartite matching as a minimum-cost flow problem](https://upload.wikimedia.org/wikipedia/commons/thumb/4/48/Minimum_weight_bipartite_matching.pdf/page1-1599px-Minimum_weight_bipartite_matching.pdf.jpg) _[Minimum weight bipartite matching](https://en.wikipedia.org/wiki/File:Minimum_weight_bipartite_matching.pdf), CC-BY 3.0 Arash.nouri_ To take another example, let's say you have a class with three students: Xanthippe, Yazoo and Zamboni. For their school's work week, there are four jobs to choose from, and the students get to rank them in order of preference. | | Accountant | Bicycle repairhuman | Construction worker | Dental assistant | | --------- | ---------- | ------------------- | ------------------- | ---------------- | | Xanthippe | 4 | 2 | 1 | 3 | | Yazoo | 3 | 1 | 2 | 4 | | Zamboni | 2 | 4 | 3 | 1 | Let's say that a student's disappointment with getting a job is proportional to the rank they gave the job, e.g. Xanthippe will be four times more disappointed with working as an accountant than as a construction worker. The problem then becomes one of minimum weight bipartite matching: Match the students with jobs so that the disappointment is the lowest. This can be solved by formulating the problem as a cost flow network. The picture below shows how the problem of assigning these students has been converted to a cost flow network along with its solution (which is a disappointment to the accounting bureau, but a relief to the students, who all got their first choice). - As with the taxi problem, the only - If an edge is labelled, its cost is equal to its label, otherwise it's 0. - All edges have a capacity equal to 1. - If an edge is red, its flow is 1, otherwise it's 0. ![Students optimally assigned to their wishes](docs/students.svg) ## Usage See [the tests](test/index.test.ts) for examples of networks and how to solve them. ## Types This package exports one type, which contains all the data necessary to formulate a cost-flow ```typescript export type Edge = { from: T; to: T; capacity: number; cost: number; flow?: number; }; ``` ## Functions
minCostFlow(graph, options) ⇒ Array.<Required.<Edge.<string>>>

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. In other words: no double edges in the same direction, and no back edges.

The function is a wrapper that destringifies the graph, calls minCostFlowForNumberNodes on it and restringifies the result.

minCostFlowForNumberNodes(graph, desiredFlow) ⇒ Array.<Required.<Edge>>

The underlying implementation of the successive shortest paths algorithm, nabbed from https://cp-algorithms.com/graph/min_cost_flow.html

Assumptions:

  • The nodes are sequentially numbered integers from 0 to (but not including) n.
  • Node 0 is the source, node n-1 is the sink.
  • Only one edge goes between any two nodes – in either direction. In other words: no double edges in the same direction, and no back edges.
cheapestPaths(adjacency, capacity, cost) ⇒ Object

The Bellman-Ford shortest path algorithm as shown in https://cp-algorithms.com/graph/min_cost_flow.html. Calculates the chepaest path from the source to every other node in the network as well as which node is the best predecessor of every node.

destringifyGraph(graph, options) ⇒ Array

Takes a graph with edges 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.

restringifyGraph(graph, nodeNames) ⇒ Array.<Edge.<string>>

Restringifies a graph that has been destringified by destringifyGraph

minimumWeightBipartiteMatch(edges) ⇒ Array.<BipartiteEdge>

Finds a minimum weight bipartite match for a graph.

Converts the problem to a minimum-cost flow problem.

## minCostFlow(graph, options) ⇒ Array.<Required.<Edge.<string>>>

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. In other words: no double edges in the same direction, and no back edges.

The function is a wrapper that destringifies the graph, calls minCostFlowForNumberNodes on it and restringifies the result.

**Kind**: global function | Param | Type | Description | | ------- | ---------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | graph | Array.<Edge.<string>> |

The graph represented as an edge list

| | options | MinCostFlowOptions |

An object with three keys: source (string), sink (string) and desiredFlow (number). Source is "SOURCE" by default, sink is "SINK" by default and desiredFlow is Infinity by default (indicating a desire for maximum flow).

| ## minCostFlowForNumberNodes(graph, desiredFlow) ⇒ Array.<Required.<Edge>>

The underlying implementation of the successive shortest paths algorithm, nabbed from https://cp-algorithms.com/graph/min_cost_flow.html

Assumptions:

**Kind**: global function **Returns**: Array.<Required.<Edge>> -

The network updated to provide as much flow up to the limit specified by desiredFlow

| Param | Type | Description | | ----------- | ---------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------- | | graph | Array.<Edge.<number>> |

The graph represented as an edge list

| | desiredFlow | number |

The maximum flow you want; the algorithm stops when it reaches this number. Default is Infinity, indicating a desire for maximum flow.

| ## cheapestPaths(adjacency, capacity, cost) ⇒ Object

The Bellman-Ford shortest path algorithm as shown in https://cp-algorithms.com/graph/min_cost_flow.html. Calculates the chepaest path from the source to every other node in the network as well as which node is the best predecessor of every node.

**Kind**: global function **Returns**: Object -

An object with type {leastCosts: number[], predecessors: number[]}. The element at index x in each of these arrays contains the least cost of going to and the best predecessors for node x respectively.

| Param | Type | Description | | --------- | ----------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | adjacency | Array.<Array.<number>> |

. I.e., if adjacency[0] === [1, 4, 6], nodes 1, 4 and 6 are adjacent to 0.

| | capacity | Array.<Array.<number>> |

A two dimensional array (size n\*n, where n is the number of nodes) describing the capacity going from each node to any other. capacity[x][y] describes the capacity from node x to node y.

| | cost | Array.<Array.<number>> |

A two dimensional array (size n\*n, where n is the number of nodes) describing the cost of transporting one unit of flow from each node to any other. cost[x][y] describes the cost from node x to node y.

| ## destringifyGraph(graph, options) ⇒ Array

Takes a graph with edges 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.

**Kind**: global function **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.

| Param | Type | Description | | ------- | ---------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | graph | Array.<Edge.<string>> |

A graph in the form of an edge list

| | options | Object |

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.

| ## restringifyGraph(graph, nodeNames) ⇒ Array.<Edge.<string>>

Restringifies a graph that has been destringified by destringifyGraph

**Kind**: global function **Returns**: Array.<Edge.<string>> -

The restringified graph

| Param | Type | Description | | --------- | ---------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------- | | graph | Array.<Edge.<number>> |

The graph as an edge list

| | nodeNames | Array.<string> |

The names of each node, so that the name of the node numbered x can be found at nodeNames[x]

| ## minimumWeightBipartiteMatch(edges) ⇒ Array.<BipartiteEdge>

Finds a minimum weight bipartite match for a graph.

Converts the problem to a minimum-cost flow problem.

**Kind**: global function **Returns**: Array.<BipartiteEdge> -

The edges that are part of the minimum bipartite match

| Param | Type | Description | | ----- | ---------------------------------------- | -------------------------------------------------------------- | | edges | Array.<BipartiteEdge> |

The entire weighted graph represented as weighted edges

| --- _Source: https://npm.io/package/min-cost-flow · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._