min-cost-flow
TypeScript icon, indicating that this package has built-in type declarations

2.1.0 • Public • Published

view on npm

min-cost-flow

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

An illustration of a minimum-cost flow problem using shipping between some norwegian cities

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 as a minimum-cost flow problem 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.

Students optimally assigned to their wishes

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

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:

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

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

Readme

Keywords

none

Package Sidebar

Install

npm i min-cost-flow

Weekly Downloads

542

Version

2.1.0

License

MIT

Unpacked Size

634 kB

Total Files

21

Last publish

Collaborators

  • vages