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 excludes are set, all edges in the graph except those provided in the 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 excludes are set, all nodes in the graph except those provided in the 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.