Solves a minimum-cost flow problem.
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
@PRODUCT@ 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)))
}Type Details
- yFiles module
- view-layout-bridge
See Also
Constructors
Parameters
A map of options to pass to the method.
- minimumCapacities - ItemMapping<IEdge,number>
- A mapping for the minimum capacities of edges. This option either sets the value directly or recursively sets properties to the instance of the minimumCapacities property on the created object.
- maximumCapacities - ItemMapping<IEdge,number>
- A mapping for maximum capacities of edges. This option either sets the value directly or recursively sets properties to the instance of the maximumCapacities property on the created object.
- costs - ItemMapping<IEdge,number>
- A mapping for edge costs. This option either sets the value directly or recursively sets properties to the instance of the costs property on the created object.
- supply - ItemMapping<INode,number>
- A mapping which provides the supply (or demand, if negative) for each node. This option either sets the value directly or recursively sets properties to the instance of the supply property on the created object.
- source - ItemCollection<INode>
- A single source node. This option either sets the value directly or recursively sets properties to the instance of the source property on the created object.
- sink - ItemCollection<INode>
- A single sink node. This option either sets the value directly or recursively sets properties to the instance of the sink property on the created object.
- subgraphNodes - ItemCollection<INode>
- The collection of nodes which define a subset of the graph for the algorithms to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphNodes property on the created object.
- subgraphEdges - ItemCollection<IEdge>
- The collection of edges which define a subset of the graph for the algorithms to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphEdges property on the created object.
Properties
Gets or sets a mapping for edge costs.
Remarks
Gets or sets a mapping for maximum capacities of edges.
Remarks
Gets or sets a mapping for the minimum capacities of edges.
Gets or sets a single sink node.
Remarks
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.
Gets or sets a single source node.
Remarks
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.
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
Remarks
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.
Remarks
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.
Remarks
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.
Methods
Solves the minimum-cost flow problem.
Parameters
A map of options to pass to the method.
- graph - IGraph
- The input graph to run the algorithm on.
Returns
- ↪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.