[ library(all_min_cuts) | Reference Manual | Alphabetic Index ]
all_min_cuts(+Graph, +CapacityArg, +SourceNode, +SinkNode, -MaxFlowValue, -MaxFlowEdges, -MinCuts, -MinCutEdges)
Curet et al, algorithm for generating all minimum-cost cuts
- Graph
- a graph structure, no parallel edges, e(Src,Dest,EdgeData)
- CapacityArg
- which argument of EdgeData to use as edge capacity (integer), (0 if EdgeData is a single number and -1 if every edge capacity is 1)
- SourceNode
- source node number (integer)
- SinkNode
- sink node number (integer)
- MaxFlowValue
- value of the maximum flow
- MaxFlowEdges
- list denoting edges with non-zero flow (form: Flow-Edge)
- MinCuts
- list of all minimum cost cutsets (each cutset is represented by a list of nodes belonging to the source-side of the cut)
- MinCutEdges
- list of all minimum cost cutsets (each cutset is represented by a list of edges that separate the source-side and the sink-side of the cut)
Description
This predicate provides all minimal cost cutsets for a max flow problem in a graph between a source and a sink node. It returns the maximal flow value, edges with non-zero flow in the optimal solution, and a list of all minimum cost cutsets corresponding to that flow value. The results are given both as node lists (nodes on the source side of the cut), and as edge lists (edges belonging to the cut), to simplify use of the predicate in situations where either of the output formats is preferred.
See Also
max_flow : max_flow / 5, max_flow : max_flow / 7, max_flow_eplex : max_flow_eplex / 5, max_flow_eplex : max_flow_eplex_dual / 5, max_flow_eplex : max_flow_eplex_dual / 7, all_min_cuts / 8, all_min_cuts / 9, all_min_cuts_list / 5, all_min_cuts_eplex : all_min_cuts_eplex / 7, all_min_cuts_eplex : all_min_cuts_eplex / 8