The OPTGRAPH Procedure

Consider again the small network of computers described in the section Betweenness and Closeness Centrality for Computer Network Topology. Suppose that this network has not yet been formed, but for structural reasons the connections between the machines shown in Figure 1.142 are the only possible links. In designing the network, the goal is to make sure that each machine in the office can reach every other machine. To accomplish this goal, Ethernet lines must be constructed and run between the machines. The construction costs for each possible link are based approximately on distance and are shown in Figure 1.151. Besides distance, the costs also reflect some restrictions due to physical boundaries. To connect all the machines in the office at minimal cost, you need to find a minimum spanning tree on the network of possible links.

Figure 1.151: Potential Office Computer Network

Define the link data set as follows:

data LinkSetInCompNet;
   input from $ to $ weight @@;
   datalines;
A B 1.0  A C 1.0  A D 1.5  B C 2.0  B D 4.0
B E 3.0  C D 3.0  C F 3.0  C H 4.0  D E 1.5
D F 3.0  D G 4.0  E F 1.0  E G 1.0  F G 2.0
F H 4.0  H I 1.0  I J 1.0
;

The following statements find a minimum spanning tree:

proc optgraph
   data_links = LinkSetInCompNet;
   minspantree
      out     = MinSpanTree;
run;

Output 1.12.1 shows the resulting data set MinSpanTree, which is displayed graphically in Figure 1.152 with the minimal cost links shown in green.

Figure 1.152: Minimum Spanning Tree for Office Computer Network