[ library(all_min_cuts) | Reference Manual | Alphabetic Index ]
all_min_cuts_list(+Graph, +CapacityArg, +SourceSinkList, +Limit, -MinCutEdgesList)
Curet et al, algorithm for generating all minimum-cost cuts, to be used for multiple source-sink pairs on the same graph since unnecessary repeat of initializations can be avoided
- 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)
- SourceSinkList
- list source and sink nodes (integers), form SourceNode-SinkNode
- Limit
- max number of min cuts to output (integer), if 0 then output all possible mincuts
- MinCutEdgesList
- list where for each Source-Sink pair there is 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 variant of the cutset generator should be used when one is interested in generating cutsets for multiple source-sink pairs in the same graph, as it avoids multiple initialisation of the data structures leading to an overall improved performance.
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