NETWORK Procedure

A topological ordering of a directed graph is a linear ordering of its nodes such that, for every directed link , node i comes before node j in the ordering. A topological ordering is commonly used to handle workflow dependencies. For example, consider scheduling a set of tasks that have dependencies. You can build a directed graph in which each node represents a task and each link represents the requirement that task i be completed before task j. A topological ordering of this graph would give you a valid sequence of tasks.

A topological ordering exists if and only if the graph contains no directed cycles.

In PROC NETWORK, you can calculate a topological ordering of the nodes of a directed acyclic input graph by using the TOPOLOGICALSORT statement.

The results of the topological sort algorithm are written to the output nodes data table that you specify in the OUTNODES= option in the PROC NETWORK statement. For each node in the nodes data table, the variable top_order identifies the order in the topological ordering.

The algorithm that PROC NETWORK uses to calculate a topological sort is a variant of the depth-first search algorithm (Tarjan 1972). This algorithm runs in time and therefore should scale to very large graphs.

Topological Ordering of a Directed Graph

This section illustrates the use of the topological sort on the directed graph G shown in Figure 212.

Figure 212: Directed Graph G

The directed graph G can be represented by the following links data table, mylib.LinkSetInTopSort:

data mylib.LinkSetInTopSort;
  input from $ to $ @@;
  datalines;
A B  A C  A D  E B  D F
E F  C B  B G  G H  D H
;

The following statements calculate a topological ordering for G and output the results in the data table mylib.NodeSetOut:

proc network
   direction = directed
   links     = mylib.LinkSetInTopSort
   outNodes  = mylib.NodeSetOut;
   topologicalSort;
run;

The output data table mylib.NodeSetOut contains a topological ordering of the input graph, as shown in Figure 213.

Figure 213: Topological Ordering of a Directed Graph

node	top_order
E	1
A	2
D	3
F	4
C	5
B	6
G	7
H	8