A cut is a partition of the nodes of a graph into two disjoint subsets. The cut-set is the set of links whose from and to nodes are in different subsets of the partition. A minimum cut of an undirected graph is a cut whose cut-set has the smallest link metric, which is measured as follows: For an unweighted graph, the link metric is the number of links in the cut-set. For a weighted graph, the link metric is the sum of the link weights in the cut-set.
In PROC OPTGRAPH, you can invoke the minimum-cut algorithm by using the MINCUT statement. The options for this statement are described in the section MINCUT Statement. This algorithm can be used only on undirected graphs.
If the value of the MAXNUMCUTS= option is greater than 1, then the algorithm can return more than one set of cuts. The resulting
cuts can be described in terms of partitions of the nodes of the graph or the links in the cut-sets. The node partition is
specified by the mincut_
i variable, for each cut i, in the data set that is specified in the OUT_NODES= option in the PROC OPTGRAPH statement. Each node is assigned the value
0 or 1, which defines the side of the partition to which it belongs. The cut-set is defined in the output data set that is
specified in the OUT= option in the MINCUT statement. This data set lists the links and their weights for each cut.
The minimum-cut algorithm reports status information in a macro variable called _OPTGRAPH_MINCUT_. See the section Macro Variable _OPTGRAPH_MINCUT_ for more information about this macro variable.
PROC OPTGRAPH uses the Stoer-Wagner algorithm (Stoer and Wagner 1997) to compute the minimum cuts. This algorithm runs in time .
As a simple example, consider the weighted undirected graph in Figure 1.84.
Figure 1.84: A Simple Undirected Graph
The links data set can be represented as follows:
data LinkSetIn; input from to weight @@; datalines; 1 2 2 1 5 3 2 3 3 2 5 2 2 6 2 3 4 4 3 7 2 4 7 2 4 8 2 5 6 3 6 7 1 7 8 3 ;
The following statements calculate minimum cuts in the graph and output the results in the data set MinCut
:
proc optgraph loglevel = moderate out_nodes = NodeSetOut data_links = LinkSetIn; mincut out = MinCut maxnumcuts = 3; run; %put &_OPTGRAPH_; %put &_OPTGRAPH_MINCUT_;
The progress of the procedure is shown in Figure 1.85.
Figure 1.85: PROC OPTGRAPH Log for Minimum Cut
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Running OPTGRAPH version 14.1. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: The OPTGRAPH procedure is executing in single-machine mode. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Reading the links data set. |
NOTE: There were 12 observations read from the data set WORK.LINKSETIN. |
NOTE: Data input used 0.01 (cpu: 0.02) seconds. |
NOTE: Building the input graph storage used 0.00 (cpu: 0.00) seconds. |
NOTE: The input graph storage is using 0.3 MBs of memory. |
NOTE: The number of nodes in the input graph is 8. |
NOTE: The number of links in the input graph is 12. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Processing the minimum-cut problem. |
NOTE: The minimum-cut algorithm found 3 cuts. |
NOTE: The cut 1 has weight 4. |
NOTE: The cut 2 has weight 5. |
NOTE: The cut 3 has weight 5. |
NOTE: Processing the minimum-cut problem used 0.00 (cpu: 0.00) seconds. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Creating nodes data set output. |
NOTE: Creating minimum-cut data set output. |
NOTE: Data output used 0.00 (cpu: 0.00) seconds. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: The data set WORK.NODESETOUT has 8 observations and 4 variables. |
NOTE: The data set WORK.MINCUT has 6 observations and 4 variables. |
STATUS=OK MINCUT=OPTIMAL |
STATUS=OPTIMAL OBJECTIVE=4 CPU_TIME=0.00 REAL_TIME=0.00 |
The data set NodeSetOut
now contains the partition of the nodes for each cut, shown in Figure 1.86.
Figure 1.86: Minimum Cut Node Partition
The data set MinCut
contains the links in the cut-sets for each cut. This data set is shown in Figure 1.87, which also shows each cut separately.
Figure 1.87: Minimum Cut Sets