Adjacency matrix maximal loops

In addition to identifying the maximal loops, it is necessary to order them into a sequence such that the equations of each maximal loop feed information only to the equations of maximal loops appearing thereafter in sequence. One scheme of precedence ordering of the maximal loops is accomplished by first forming an adjacency matrix of loops, P, in which the rows and columns correspond to the maximal loops (S3). The elements of the matrix P are either 1 or 0 according to the rule... 

Correspond to the Maximal Loops in the Adjacency Matrix and are Invariant of the Output Set. 200... 

One method of locating these maximal loops is to compute the reachability matrix, R (H1), which is the element by element Boolean union of all of the powers of the adjacency matrix up to the nth, where n is the number of rows of R. An element of the reachability matrix is defined as... 

We have shown thus far how the system of equations representing a process can be related to a linear diagraph and its associated Boolean adjacency matrix. In the Section IV, we show how the location of the maximal loops in this adjacency matrix leads to identification of the subsystems of equations that must be solved simultaneously. 

We now demonstrate how the subsystems of equations that must be solved simultaneoulsy correspond to the maximal loops found in the related adjacency matrix. Consider the following set of two equations each containing common variables ... 

Previously we have termed the largest loop of information flow a maximal loop, and indicated that it is not tied into other loops, by definition. One might wonder, because the choice of an output set is not unique, whether the maximal loops of information flow in one adjacency matrix will differ from those of another adjacency matrix, i.e., one formed from a different output set. It is shown in the following paragraphs that the maximal loops will be the same and therefore any output set will suffice for accomplishing the partitioning. 

One method of partitioning the system equations is to compute the maximal loops using powers of the adjacency matrix as discussed in Section II. Certain modifications to the methods of Section II are needed in order to reduce the computation time. The first modification is to obtain the product of the matrices using Boolean unions of rows instead of the multiplication technique previously demonstrated to obtain a power of an adjacency matrix. To show how the Boolean union of rows can replace the standard matrix multiplication, consider the definition of Boolean matrix multiplication, Eq. (2), which can be expanded to... 

Actually, only one matrix need be stored if the adjacency matrix is stored initially and thereafter multiplied by itself. Matrix elements are replaced by the resulting product elements as they are computed. The product matrix obtained in this manner for the fcth power may contain some nonzero elements which correspond to paths longer than k steps instead of strictly k step paths, but this will not affect the final matrix obtained corresponding to the nth power, since these paths would eventually be identified in any case. All of the modifications to the methods of Section II mentioned above simplify the calculations needed to obtain the reachability matrix. The procedure for identifying the maximal loops given in Section II remains the same. 

---