min-cost-flow

• Minimum-cost flow problems
• Solving assignment problems using minimum-cost flow
• Usage
• Types
• Functions
• minCostFlow(graph, options) ⇒ Array.<Required.<Edge.<string>>>
• minCostFlowForNumberNodes(graph, desiredFlow) ⇒ Array.<Required.<Edge>>
• cheapestPaths(adjacency, capacity, cost) ⇒ Object
• destringifyGraph(graph, options) ⇒ Array
• restringifyGraph(graph, nodeNames) ⇒ Array.<Edge.<string>>
• minimumWeightBipartiteMatch(edges) ⇒ Array.<BipartiteEdge>

A package that solves minimum-cost flow problems 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:

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

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:

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, 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.

Usage

See the tests 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

export type Edge<T = number | string> = {
  from: T;
  to: T;
  capacity: number;
  cost: number;
  flow?: number;
};

Functions

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

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>>

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

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

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>>

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>

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 |