minCut - WeAreCAS

Description

The minCut action calculates the minimum cut of a graph. A cut is a partition of the nodes of a graph into two disjoint subsets. A cut set is the set of links whose from and to nodes are in different subsets of the partition. A minimum cut is a cut whose cut set has the minimum total link weight.

optNetwork.minCut { deterministic=TRUE | FALSE, direction="DIRECTED" | "UNDIRECTED", display={...}, distributed=TRUE | FALSE, graph=integer, indexOffset=integer, links={...}, linksVar={...}, logFreqTime=integer, logLevel="AGGRESSIVE" | "BASIC" | "MODERATE" | "NONE", maxCuts=integer, maxWeight=double, multiLinks=TRUE | FALSE, nodes={...}, nodesVar={...}, nThreads=integer, outCutSets={...}, outGraphList={...}, outLinks={...}, outNodes={...}, outPartitions={...}, outputTables={...}, selfLinks=TRUE | FALSE, sink="string" | double | 64-bit-integer, source="string" | double | 64-bit-integer, standardizedLabels=TRUE | FALSE, standardizedLabelsOut=TRUE | FALSE };

Settings

Parameter	Description
deterministic	when set to True, ensures that each invocation (with the same machine configuration and parameter settings) produces the same final result.
direction	specifies whether to consider the input graph as directed or undirected.
display	specifies a list of results tables to send to the client for display.
distributed	when set to True, uses a distributed graph.
graph	specifies the in-memory graph to use.
indexOffset	specifies the index offset for identifiers in the log and results output data tables.
links	specifies the input data table that contains the graph link information.
linksVar	specifies the data variable names for the links table.
logFreqTime	controls the frequency n (in seconds) for displaying iteration logs for some algorithms, where n can be any integer greater than or equal to 1.
logLevel	controls the amount of information that is displayed in the SAS log.
maxCuts	specifies the maximum number of cuts for the algorithm to return.
maxWeight	specifies the maximum weight of the cuts to be returned by the algorithm.
multiLinks	when set to True, includes multilinks when an input graph is read.
nodes	specifies the input data table that contains the graph node information.
nodesVar	specifies the data variable names for the nodes table.
nThreads	specifies the maximum number of threads to use for multithreaded processing.
outCutSets	specifies the output data table to contain minimum cut sets.
outGraphList	specifies the output data table to contain summary information about in-memory graphs.
outLinks	specifies the output data table to contain the graph link information.
outNodes	specifies the output data table to contain the graph node information.
outPartitions	specifies the output data table to contain minimum cut partitions.
outputTables	lists the names of results tables to save as CAS tables on the server.
selfLinks	when set to True, includes self-links when an input graph is read.
sink	specifies the sink node of the minimum cut.
source	specifies the source node of the minimum cut.
standardizedLabels	when set to True, specifies that the input graph data are in a standardized format.
standardizedLabelsOut	when set to True, requests that the output graph data include standardized format.

Data Preparation View data prep sheet

Minimum Cut for a Directed Graph

This section illustrates the use of the minimum-cut algorithm on the directed graph G shown in Figure 163.

Copied!

1	DATA mycas.LinkSetIn;
2	INPUT from $ to $ weight @@;
3	DATALINES;
4	A B 10 A C 10 B C 2 B D 4 B E 8 C E 9
5	D E 6 D F 4 D G 8 E F 4 F G 2
6	;

Examples

This section illustrates the use of the minimum-cut algorithm on the directed graph G shown in Figure 163.

SAS® / CAS Code Code awaiting community validation

Copied!

1	PROC CAS;
2	ACTION optNetwork.minCut /
3	direction = "directed"
4	links = {name = "LinkSetIn"}
5	SOURCE = "A"
6	sink = "G"
7	outCutSets = {name="CutSets", replace=true}
8	outPartitions = {name="Partitions", replace=true};
9	RUN;
10	PRINT cas.TABLE.fetch{TABLE="CutSets"}.Fetch;
11	RUN;
12	PRINT cas.TABLE.fetch{TABLE="Partitions"}.Fetch;
13	RUN;
14	QUIT;

Result :
The action produces a result table `CutSets` showing the links in the minimum cut and another table `Partitions` showing the nodes in each partition. The minimum cut weight is 7.

FAQ

What is the primary purpose of the minCut action in the optNetwork action set?

What are the key input parameters required to define a minimum cut problem?

How can I limit the number of cuts returned by the algorithm?

Is it possible to filter the returned cuts based on their weight?

Which output tables does the minCut action produce to store the results?

Can the minCut action handle both directed and undirected graphs?