Network Flows

Network Flow algorithms work on flow networks (graphs). This means all edges have a maximal capacity, and a flow value is calculated for each edge that respects this capacity and assures that the incoming flow at a node matches the outgoing flow except for specified source or sink nodes.

Maximum Flow

The MaximumFlow calculates the maximal valid flow between source and sink nodes where the sources have only outgoing and the sinks only incoming flow.

Maximum Flow graph shows a flow network where each edge is labeled with its flow to maximum flow ratio.

Calculate the maximum flow shows how to calculate the maximum flow between the source node (with no incoming edges) and the sink node (with no outgoing edges).

Calculate the maximum flow

// configure and run the MaximumFlow algorithm
const maximumFlowResult = new MaximumFlow({
  capacities: (edge) => getCapacity(edge),
  sources: (edge) => graph.inDegree(edge) === 0,
  sinks: (edge) => graph.outDegree(edge) === 0
}).run(graph)
// add edge labels with the flow/capacity ratio
const maximumFlowValue = maximumFlowResult.maximumFlow
maximumFlowResult.flow.forEach(({ key, value }) => {
  const edge = key
  const flow = value
  graph.addLabel(edge, flow + ' / ' + getCapacity(edge))
})
// configure and run the MaximumFlow algorithm
const maximumFlowResult = new MaximumFlow({
  capacities: (edge) => getCapacity(edge),
  sources: (edge) => graph.inDegree(edge) === 0,
  sinks: (edge) => graph.outDegree(edge) === 0
}).run(graph)
// add edge labels with the flow/capacity ratio
const maximumFlowValue = maximumFlowResult.maximumFlow
maximumFlowResult.flow.forEach(({ key, value }) => {
  const edge: IEdge = key
  const flow: number = value
  graph.addLabel(edge, flow + ' / ' + getCapacity(edge))
})

Minimum Cost Flow

The MinimumCostFlow calculates the flow with minimum costs that satisfies some further conditions besides the maximumCapacities.

MinimumCostFlow offers the following variants of conditions:

a supply value for nodes that specifies the surplus between outgoing and incoming flow (respectively the demand if a negative supply value is used). In addition, minimumCapacities may be specified for edges.
a source and a sink node is specified, and the cheapest maximum flow between these nodes is found.

Minimum Cost Flow graph shows the minimum cost flow throught the network where the demand of the sink is limited to -25.

analysis min cost flow — Minimum Cost Flow graph

Calculate the minimum cost flow shows how to calculate the cheapest maximum flow between the source node and the sink node with specified Supply values.

Calculate the minimum cost flow

// configure and run the MinimumCostFlow algorithm
const minimumCostFlowResult = new MinimumCostFlow({
  maximumCapacities: (edge) => getCapacity(edge),
  costs: (edge) => (graph.inDegree(edge) === 0 ? 30 : graph.outDegree(edge) === 0 ? -25 : 0),
  source: (edge) => graph.inDegree(edge) === 0,
  sink: (edge) => graph.outDegree(edge) === 0
}).run(graph)
// add edge labels with the flow/capacity ratio
const totalCosts = minimumCostFlowResult.totalCost
minimumCostFlowResult.flow.forEach(({ key, value }) => {
  const edge = key
  const flow = value
  graph.addLabel(edge, flow + ' / ' + getCapacity(edge))
})
// configure and run the MinimumCostFlow algorithm
const minimumCostFlowResult = new MinimumCostFlow({
  maximumCapacities: (edge) => getCapacity(edge),
  costs: (edge) => (graph.inDegree(edge) === 0 ? 30 : graph.outDegree(edge) === 0 ? -25 : 0),
  source: (edge) => graph.inDegree(edge) === 0,
  sink: (edge) => graph.outDegree(edge) === 0
}).run(graph)
// add edge labels with the flow/capacity ratio
const totalCosts = minimumCostFlowResult.totalCost
minimumCostFlowResult.flow.forEach(({ key, value }) => {
  const edge: IEdge = key
  const flow: number = value
  graph.addLabel(edge, flow + ' / ' + getCapacity(edge))
})

Trees Transitivity