The OPTGRAPH Procedure

Graph Input Data

This section describes how to input a graph for analysis by PROC OPTGRAPH. Let $G = (N,A)$ define a graph with a set N of nodes and a set A of links.

Consider the directed graph shown in Figure 1.8.

Figure 1.8: A Simple Directed Graph

A Simple Directed Graph


Notice that each node and link has associated attributes: a node label and a link weight.

Node Input Data

The DATA_NODES= option in the PROC OPTGRAPH statement defines the data set that contains the list of nodes in the graph. This data set is used to define clusters (subgraphs) or to assign node weights.

The nodes data set is expected to contain some combination of the following possible variables:

  • node: the node label (this variable can be numeric or character)

  • cluster: the node cluster identifier (this variable must be numeric)

  • weight: the node weight (this variable must be numeric)

  • weight2: the auxiliary node weight (this variable must be numeric)

The variable cluster is used to define clusters (subgraphs) for decomposing the input graph into subgraphs for processing. This is useful for the algorithms specified in the CENTRALITY, REACH, and SUMMARY statements. The use of the variable cluster is explained in more detail in the section Processing by Cluster.

You can specify any values that you want for the data set variable names. If you use nonstandard names, you must identify the variables by using the DATA_NODES_VAR statement, as described in the section DATA_NODES_VAR Statement.

The data set that is specified in the DATA_LINKS= option defines the set of nodes that are incident to some link. If the graph contains a node that has no links (called a singleton node), then this node must be defined in the DATA_NODES data set. The following is an example of a graph with three links but four nodes, including a singleton node D:

data NodeSetIn;
   input label $ @@;
   datalines;
A B C D
;

data LinkSetInS;
   input from $ to $ weight;
   datalines;
A B 1
A C 2
B C 1
;

If you specify duplicate entries in the node data set, PROC OPTGRAPH takes the first occurrence of the node and ignores the others. A warning is printed to the log.

Node Subset Input Data

For some algorithms, you might want to process only a subset of the nodes that appear in the input graph. You can accomplish this by using the DATA_NODES_SUB= option in the PROC OPTGRAPH statement. You can use the node subset data set in conjunction with the SHORTPATH or REACH statement. (See the sections Shortest Path and Reach (Ego) Network, respectively.) The node subset data set is expected to contain some combination of the following variables:

  • node: the node label (this variable can be numeric or character)

  • source: whether to process this node as a source node in shortest path algorithms (this variable must be numeric)

  • sink: whether to process this node as a sink node in shortest path algorithms (this variable must be numeric)

  • reach: for the reach algorithm, the index of the source subgraph for processing (this variable must be numeric)

Table 1.53 shows how PROC OPTGRAPH processes nodes for each algorithm type. The missing indicator (.) can also be used in place of 0 to designate that a node is not to be processed.

Table 1.53: Determining How to Process a Node

Algorithm Type

Variable Designations

Example Shown In:

Shortest path

A value of 0 for the source variable designates that the node is not to be processed as a source; a value of 1 designates that the node is to be processed as a source. The same values can be used for the sink variable to designate whether the node is to be processed as a sink.

The section Shortest Path

Reach

A value of 0 for the reach variable designates that the node is not to be processed. A value greater than 0 defines a marker for the source subgraph to which this node belongs. All nodes with the same marker are processed together as source nodes.

The section Reach (Ego) Network


A representative example of a node subset data set that might be used with the graph in Figure 1.8 is as follows:

data NodeSubSetIn;
   input node $ reach source sink;
   datalines;
A 1 1 .
F 2 . 1
E 2 1 .
;

The data set NodeSubSetIn indicates that you want to process the following:

  • the reach network from the subgraph defined by node A

  • the reach network from the subgraph defined by nodes F and E

  • the shortest paths for the source-sink pairs in $\{ A,E\}  \times \{ F\} $

Standardized Labels

For large scale graphs, the processing stage that reads the nodes and links into memory can be time consuming. Under the following assumptions, you can use the STANDARDIZED_LABELS option in the PROC OPTGRAPH statement to greatly speed up this stage:

  1. The link data set variables from and to are numeric type

  2. The node and node subset data set variable node is numeric type

  3. The node labels start from 0 and are consecutive nonnegative integers.

Consider the following links data set that uses numeric labels:

data LinkSetIn;
   input from to weight;
   datalines;
0 1 1
3 0 2
1 5 1
;

Using default settings, the following statements echo back link and node data sets that contain three links and four nodes, respectively.

proc optgraph
   data_links = LinkSetIn
   out_nodes  = NodeSetOut
   out_links  = LinkSetOut;
run;

The log is shown in Figure 1.13.

Figure 1.13: PROC OPTGRAPH Log: A Simple Undirected Graph

NOTE: ------------------------------------------------------------------------------------------
NOTE: Running OPTGRAPH version 14.1.                                                            
NOTE: ------------------------------------------------------------------------------------------
NOTE: The OPTGRAPH procedure is executing in single-machine mode.                               
NOTE: ------------------------------------------------------------------------------------------
NOTE: Data input used 0.01 (cpu: 0.00) seconds.                                                 
NOTE: The number of nodes in the input graph is 4.                                              
NOTE: The number of links in the input graph is 3.                                              
NOTE: ------------------------------------------------------------------------------------------
NOTE: Data output used 0.00 (cpu: 0.00) seconds.                                                
NOTE: ------------------------------------------------------------------------------------------
NOTE: The data set WORK.NODESETOUT has 4 observations and 1 variables.                          
NOTE: The data set WORK.LINKSETOUT has 3 observations and 3 variables.                          



The data set NodeSetOut, shown in Figure 1.14, contains the unique numeric node labels, $\{ 0,1,3,5\} $.

Figure 1.14: Node Data Set of a Simple Directed Graph

Obs node
1 0
2 1
3 3
4 5



Using standardized labels, the same input data set defines a graph with six (not four) nodes.

proc optgraph
   standardized_labels
   data_links = LinkSetIn
   out_nodes  = NodeSetOut
   out_links  = LinkSetOut;
run;

The log that results from using standardized labels is shown in Figure 1.15.

Figure 1.15: PROC OPTGRAPH Log: A Simple Undirected Graph Using Standardized Labels

NOTE: ------------------------------------------------------------------------------------------
NOTE: Running OPTGRAPH version 14.1.                                                            
NOTE: ------------------------------------------------------------------------------------------
NOTE: The OPTGRAPH procedure is executing in single-machine mode.                               
NOTE: ------------------------------------------------------------------------------------------
NOTE: Data input used 0.00 (cpu: 0.00) seconds.                                                 
NOTE: The number of nodes in the input graph is 6.                                              
NOTE: The number of links in the input graph is 3.                                              
NOTE: The number of singleton nodes in the input graph is 2.                                    
NOTE: ------------------------------------------------------------------------------------------
NOTE: Data output used 0.00 (cpu: 0.00) seconds.                                                
NOTE: ------------------------------------------------------------------------------------------
NOTE: The data set WORK.NODESETOUT has 6 observations and 1 variables.                          
NOTE: The data set WORK.LINKSETOUT has 3 observations and 3 variables.                          



The data set NodeSetOut, shown in Figure 1.16, now contains all node labels from 0 to 5, based on the assumptions when using the STANDARDIZED_LABELS option.

Figure 1.16: Node Data Set of a Simple Directed Graph

Obs node
1 0
2 1
3 2
4 3
5 4
6 5



When using standardized labels, the DATA_NODES= input order (which can be arbitrary) is not preserved in the OUT_NODES= output data set. Instead, the order is ascending, starting from zero.