Network Flows

Network flow algorithms operate on flow networks, which are graphs where all edges have a maximum capacity. These algorithms calculate a flow value for each edge, ensuring that the flow respects the capacity constraint and that the total incoming flow at a node equals the total outgoing flow. This balance must be maintained for all nodes except for the designated source and sink nodes.

Maximum Flow

The MaximumFlow class calculates the maximum possible flow between source and sink nodes. The sources have only outgoing flow, and the sinks have 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 the minimum costs that meets specific conditions, in addition to the maximumCapacities.

MinimumCostFlow offers the following condition variants:

A supply value for nodes that specifies the surplus between outgoing and incoming flow (or the demand if a negative supply value is used). minimumCapacities can also be specified for edges.
A source and a sink node are specified, and the cheapest maximum flow between these nodes is found.

Minimum Cost Flow graph shows the minimum cost flow through 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