The Network Solver (Experimental)

Transitive Closure

Subsections:

Transitive Closure of a Simple Directed Graph

The transitive closure of a graph $G$ is a graph $G^ T = (N,A^ T)$ such that for all $i,j \in N$ there is a link $(i,j) \in A^ T$ if and only if there exists a path from $i$ to $j$ in $G$ .

The transitive closure of a graph can help you efficiently answer questions about reachability. Suppose you want to answer the question of whether you can get from node $i$ to node $j$ in the original graph $G$ . Given the transitive closure $G^ T$ of $G$ , you can simply check for the existence of link $(i,j)$ to answer the question. Transitive closure has many applications, including speeding up the processing of structured query languages, which are often used in databases.

In the network solver, you can invoke the transitive closure algorithm by using the TRANSITIVE_CLOSURE option.

The results for the transitive closure algorithm are written to the set that is specified in the CLOSURE= suboption in the OUT= option.

The algorithm that the network solver uses to compute transitive closure is a sparse version of the Floyd-Warshall algorithm (Cormen, Leiserson, and Rivest 1990). This algorithm runs in time $O(|N|^3)$ and therefore might not scale to very large graphs.

Transitive Closure of a Simple Directed Graph

This example illustrates the use of the transitive closure algorithm on the simple directed graph $G$ that is shown in Figure 8.59.

Figure 8.59: A Simple Directed Graph $G$

The directed graph $G$ can be represented by the links data set LinkSetIn as follows:

data LinkSetIn;
   input from $ to $ @@;
   datalines;
B C  B D  C B  D A  D C
;

The following statements calculate the transitive closure and output the results in the data set TransClosure:

proc optmodel;
   set<str,str> LINKS;
   read data LinkSetIn into LINKS=[from to];
   set<str,str> CAN_REACH;

   solve with NETWORK /
      links = ( include = LINKS )
      transc
      out = ( closure = CAN_REACH )
   ;

   put CAN_REACH;
   create data TransClosure from [from to]=CAN_REACH;
quit;

The data set TransClosure contains the transitive closure of $G$ and is shown in Figure 8.60.

Figure 8.60: Transitive Closure of a Simple Directed Graph

Transitive Closure

from	to
B	C
B	D
D	A
D	C
C	C
D	D
B	B
B	A
C	A
A	A

The transitive closure of $G$ is shown graphically in Figure 8.61.

Figure 8.61: Transitive Closure of $G$

For a more detailed example, see Example 8.6.