Remarks
The minimum-cost flow problem is an optimization problem to find the cheapest possible way of sending a certain amount of flow through a network with capacities and costs.
There are three main ways of using this class, depending on how the problem to solve is stated. All variants require the maximumCapacities and costs.
- There can be minimumCapacities for edges as well as the maximumCapacities. In this variant supply is considered for defining supply/demand for nodes in the network, while source and sink are ignored.
- A source and sink node can be provided, in which case supply is ignored.
- As a third option, multiple nodes can have specific values for supply and demand configured via supply.
Other Flow Algorithms
yFiles for HTML supports another algorithm related to network flow:
- MaximumFlow – solves a maximum flow problem where the largest possible flow through a network should be determined
Examples
// prepare the minimum cost flow algorithm
const algorithm = new MinimumCostFlow({
maximumCapacities,
supply,
costs,
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual flow
for (const edge of graph.edges) {
graph.addLabel(edge, String(result.flow.get(edge)))
}See Also
Developer's Guide
API
- minimumCostFlow
Members
Constructors
Properties
Gets or sets a mapping for edge costs.
See Also
Developer's Guide
Gets or sets a mapping for maximum capacities of edges.
See Also
Developer's Guide
Gets or sets a mapping for the minimum capacities of edges.
See Also
Developer's Guide
Gets or sets a single sink node.
If none is provided, the overall flow is calculated. In this case it is mandatory to provide a valid supply mapping.
If multiple are provided, the first valid sink node is used.
See Also
Developer's Guide
Gets or sets a single source node.
If none is provided, the overall flow is calculated. In this case, it is mandatory to provide a valid supply mapping.
If multiple are provided, the first valid source node is used.
See Also
Developer's Guide
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
If nothing is set, all edges of the graph will be processed.
If only the ItemCollection<TItem>.excludes are set, all edges in the graph except those provided in the ItemCollection<TItem>.excludes are processed.
Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// prepare the minimum cost flow algorithm
const algorithm = new MinimumCostFlow({
maximumCapacities,
supply,
costs,
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual flow
for (const edge of graph.edges) {
graph.addLabel(edge, String(result.flow.get(edge)))
}Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
If nothing is set, all nodes of the graph will be processed.
If only the ItemCollection<TItem>.excludes are set, all nodes in the graph except those provided in the ItemCollection<TItem>.excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// prepare the minimum cost flow algorithm
const algorithm = new MinimumCostFlow({
maximumCapacities,
supply,
costs,
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node: INode): boolean =>
node.style instanceof ShapeNodeStyle &&
node.style.shape === ShapeNodeShape.ELLIPSE,
// but ignore the first node, regardless of its shape
excludes: graph.nodes.first()!,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual flow
for (const edge of graph.edges) {
graph.addLabel(edge, String(result.flow.get(edge)))
}Gets or sets a mapping which provides the supply (or demand, if negative) for each node.
Nodes with a positive supply effectively act as additional sources, while nodes with a negative supply (demand) effectively act as additional sinks. However, both can appear anywhere in the network.
This value is ignored if both a source and sink node but no minimumCapacities are provided.
If no source or sink or neither of them are provided it is mandatory to provide a valid supply map.
See Also
Developer's Guide
Methods
Solves the minimum-cost flow problem.
Parameters
- graph: IGraph
- The input graph to run the algorithm on.
Return Value
- MinimumCostFlowResult
- A MinimumCostFlowResult containing the flow for each edge and the total cost.
Throws
- Exception ({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.