min-cost-flow v2.1.0

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.

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

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

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.

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 nodeNamesn for any node in the destringified graph.

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

Kind: global function
Returns: Array.<Edge.<string>> - The restringified graph

minimumWeightBipartiteMatch(edges) ⇒ Array.<BipartiteEdge>

Kind: global function
Returns: Array.<BipartiteEdge> - The edges that are part of the minimum bipartite match