The minSpanTree action calculates the minimum spanning tree (MST) of a graph. An MST is a subgraph that connects all nodes together with the minimum possible total link weight, without forming any cycles. For directed graphs, it finds a minimum spanning arborescence, which is a directed tree rooted at a specified source node.
| 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. For MST, this is typically 'UNDIRECTED'. When 'DIRECTED' is used, a source node must be specified to find a minimum spanning arborescence. |
| display | Specifies a list of results tables to send to the client for display. |
| distributed | When set to True, uses a distributed graph algorithm. Set to false for single-machine processing. |
| graph | Specifies the in-memory graph to use for the calculation, if it has been previously loaded. |
| indexOffset | Specifies the index offset for identifiers in the log and results tables. For example, an offset of 1 would label entities starting from 1 instead of 0. |
| links | Specifies the input data table that contains the graph link information, including 'from', 'to', and 'weight' columns. |
| linksVar | Specifies the data variable names for the links table if they differ from the defaults (e.g., from, to, weight). |
| logLevel | Controls the amount of information displayed in the SAS log during action execution. |
| out | Specifies the output data table to contain the links that form the minimum spanning tree. |
| source | Specifies the source node for calculating a directed minimum spanning tree (arborescence). This parameter is required when direction is 'DIRECTED'. |
Create a CAS table named 'mycas.LinkSetIn' representing a graph. It contains 'from' and 'to' columns for nodes, and a 'weight' column for the cost or distance of each link.
| 1 | DATA mycas.LinkSetIn; |
| 2 | attrib from varchar(1) to varchar(1) weight numeric; |
| 3 | INFILE DATALINES dlm=' '; |
| 4 | INPUT from $ to $ weight; |
| 5 | DATALINES; |
| 6 | A B 10 |
| 7 | A C 4 |
| 8 | B C 2 |
| 9 | B D 5 |
| 10 | C D 8 |
| 11 | C E 6 |
| 12 | D E 1 |
| 13 | ; |
| 14 | RUN; |
This example finds the minimum spanning tree on an undirected graph. It identifies the subset of links that connects all nodes with the minimum total weight.
| 1 | PROC CAS; |
| 2 | ACTION optNetwork.minSpanTree / |
| 3 | links={name='LinkSetIn'} |
| 4 | out={name='MstOut', replace=true}; |
| 5 | RUN; |
| 6 | ACTION TABLE.fetch / TABLE='MstOut'; |
| 7 | RUN; |
| 8 | QUIT; |
This example calculates a directed minimum spanning tree (an arborescence) rooted at the source node 'A'. It finds the cheapest paths from 'A' to all other nodes, forming a tree structure.
| 1 | PROC CAS; |
| 2 | ACTION optNetwork.minSpanTree / |
| 3 | links={name='LinkSetIn'} |
| 4 | direction='DIRECTED' |
| 5 | SOURCE='A' |
| 6 | out={name='MstOutDirected', replace=true}; |
| 7 | RUN; |
| 8 | ACTION TABLE.fetch / TABLE='MstOutDirected'; |
| 9 | RUN; |
| 10 | QUIT; |