Amesos Package Browser (Single Doxygen Collection) Development
amesos_btf_strongcomp.c
Go to the documentation of this file.
00001 /* ========================================================================== */
00002 /* === BTF_STRONGCOMP ======================================================= */
00003 /* ========================================================================== */
00004 
00005 /* Finds the strongly connected components of a graph, or equivalently, permutes
00006  * the matrix into upper block triangular form.  See btf.h for more details.
00007  * Input matrix and Q are not checked on input.
00008  *
00009  * Copyright (c) 2004-2007.  Tim Davis, University of Florida,
00010  * with support from Sandia National Laboratories.  All Rights Reserved.
00011  */
00012 
00013 #include "amesos_btf_decl.h"
00014 #include "amesos_btf_internal.h"
00015 
00016 #define UNVISITED (-2)      /* Flag [j] = UNVISITED if node j not visited yet */
00017 #define UNASSIGNED (-1)     /* Flag [j] = UNASSIGNED if node j has been visited,
00018            * but not yet assigned to a strongly-connected
00019            * component (aka block).  Flag [j] = k (k in the
00020            * range 0 to nblocks-1) if node j has been visited
00021            * (and completed, with its postwork done) and
00022            * assigned to component k. */
00023 
00024 /* This file contains two versions of the depth-first-search, a recursive one
00025  * and a non-recursive one.  By default, the non-recursive one is used. */
00026 
00027 #ifndef RECURSIVE
00028 
00029 /* ========================================================================== */
00030 /* === dfs: non-recursive version (default) ================================= */
00031 /* ========================================================================== */
00032 
00033 /* Perform a depth-first-search of a graph, stored in an adjacency-list form.
00034  * The row indices of column j (equivalently, the out-adjacency list of node j)
00035  * are stored in Ai [Ap[j] ... Ap[j+1]-1].  Self-edge (diagonal entries) are
00036  * ignored.  Ap[0] must be zero, and thus nz = Ap[n] is the number of entries
00037  * in the matrix (or edges in the graph).  The row indices in each column need
00038  * not be in any particular order.  If an input column permutation is given,
00039  * node j (in the permuted matrix A*Q) is located in
00040  * Ai [Ap[Q[j]] ... Ap[Q[j]+1]-1].  This Q can be the same as the Match array
00041  * output from the maxtrans routine, for a square matrix that is structurally
00042  * full rank.
00043  *
00044  * The algorithm is from the paper by Robert E. Tarjan, "Depth-first search and
00045  * linear graph algorithms," SIAM Journal on Computing, vol. 1, no. 2,
00046  * pp. 146-160, 1972.  The time taken by strongcomp is O(nnz(A)).
00047  *
00048  * See also MC13A/B in the Harwell subroutine library (Iain S. Duff and John
00049  * K. Reid, "Algorithm 529: permutations to block triangular form," ACM Trans.
00050  * on Mathematical Software, vol. 4, no. 2, pp. 189-192, 1978, and "An
00051  * implementation of Tarjan's algorithm for the block triangular form of a
00052  * matrix," same journal, pp. 137-147.  This code is implements the same
00053  * algorithm as MC13A/B, except that the data structures are very different.
00054  * Also, unlike MC13A/B, the output permutation preserves the natural ordering
00055  * within each block.
00056  */
00057 
00058 static void amesos_dfs
00059 (
00060     /* inputs, not modified on output: */
00061     Int j,    /* start the DFS at node j */
00062     Int Ap [ ],   /* size n+1, column pointers for the matrix A */
00063     Int Ai [ ],   /* row indices, size nz = Ap [n] */
00064     Int Q [ ],    /* input column permutation */
00065 
00066     /* inputs, modified on output (each array is of size n): */
00067     Int Time [ ], /* Time [j] = "time" that node j was first visited */
00068     Int Flag [ ], /* Flag [j]: see above */
00069     Int Low [ ],  /* Low [j]: see definition below */
00070     Int *p_nblocks, /* number of blocks (aka strongly-connected-comp.)*/
00071     Int *p_timestamp, /* current "time" */
00072 
00073     /* workspace, not defined on input or output: */
00074     Int Cstack [ ], /* size n, output stack to hold nodes of components */
00075     Int Jstack [ ], /* size n, stack for the variable j */
00076     Int Pstack [ ]  /* size n, stack for the variable p */
00077 )
00078 {
00079     /* ---------------------------------------------------------------------- */
00080     /* local variables, and initializations */
00081     /* ---------------------------------------------------------------------- */
00082 
00083     /* local variables, but "global" to all DFS levels: */
00084     Int chead ;     /* top of Cstack */
00085     Int jhead ;     /* top of Jstack and Pstack */
00086 
00087     /* variables that are purely local to any one DFS level: */
00088     Int i ;     /* edge (j,i) considered; i can be next node to traverse */
00089     Int parent ;    /* parent of node j in the DFS tree */
00090     Int pend ;      /* one past the end of the adjacency list for node j */
00091     Int jj ;      /* column j of A*Q is column jj of the input matrix A */
00092 
00093     /* variables that need to be pushed then popped from the stack: */
00094     Int p ;     /* current index into the adj. list for node j */
00095     /* the variables j and p are stacked in Jstack and Pstack */
00096 
00097     /* local copies of variables in the calling routine */
00098     Int nblocks   = *p_nblocks ;
00099     Int timestamp = *p_timestamp ;
00100 
00101     /* ---------------------------------------------------------------------- */
00102     /* start a DFS at node j (same as the recursive call dfs (EMPTY, j)) */
00103     /* ---------------------------------------------------------------------- */
00104 
00105     chead = 0 ;       /* component stack is empty */
00106     jhead = 0 ;       /* Jstack and Pstack are empty */
00107     Jstack [0] = j ;      /* put the first node j on the Jstack */
00108     ASSERT (Flag [j] == UNVISITED) ;
00109 
00110     while (jhead >= 0)
00111     {
00112   j = Jstack [jhead] ;      /* grab the node j from the top of Jstack */
00113 
00114   /* determine which column jj of the A is column j of A*Q */
00115   jj = (Q == (Int *) NULL) ? (j) : (BTF_UNFLIP (Q [j])) ;
00116   pend = Ap [jj+1] ;      /* j's row index list ends at Ai [pend-1] */
00117 
00118   if (Flag [j] == UNVISITED)
00119   {
00120 
00121       /* -------------------------------------------------------------- */
00122       /* prework at node j */
00123       /* -------------------------------------------------------------- */
00124 
00125       /* node j is being visited for the first time */
00126       Cstack [++chead] = j ;      /* push j onto the stack */
00127       timestamp++ ;       /* get a timestamp */
00128       Time [j] = timestamp ;      /* give the timestamp to node j */
00129       Low [j] = timestamp ;
00130       Flag [j] = UNASSIGNED ;     /* flag node j as visited */
00131 
00132       /* -------------------------------------------------------------- */
00133       /* set Pstack [jhead] to the first entry in column j to scan */
00134       /* -------------------------------------------------------------- */
00135 
00136       Pstack [jhead] = Ap [jj] ;
00137   }
00138 
00139   /* ------------------------------------------------------------------ */
00140   /* DFS rooted at node j (start it, or continue where left off) */
00141   /* ------------------------------------------------------------------ */
00142 
00143   for (p = Pstack [jhead] ; p < pend ; p++)
00144   {
00145       i = Ai [p] ;    /* examine the edge from node j to node i */
00146       if (Flag [i] == UNVISITED)
00147       {
00148     /* Node i has not been visited - start a DFS at node i.
00149      * Keep track of where we left off in the scan of adjacency list
00150      * of node j so we can restart j where we left off. */
00151     Pstack [jhead] = p + 1 ;
00152     /* Push i onto the stack and immediately break
00153      * so we can recurse on node i. */
00154     Jstack [++jhead] = i ;
00155     ASSERT (Time [i] == EMPTY) ;
00156     ASSERT (Low [i] == EMPTY) ;
00157     /* break here to do what the recursive call dfs (j,i) does */
00158     break ;
00159       }
00160       else if (Flag [i] == UNASSIGNED)
00161       {
00162     /* Node i has been visited, but still unassigned to a block
00163      * this is a back or cross edge if Time [i] < Time [j].
00164      * Note that i might equal j, in which case this code does
00165      * nothing. */
00166     ASSERT (Time [i] > 0) ;
00167     ASSERT (Low [i] > 0) ;
00168     Low [j] = MIN (Low [j], Time [i]) ;
00169       }
00170   }
00171 
00172   if (p == pend)
00173   {
00174       /* If all adjacent nodes of j are already visited, pop j from
00175        * Jstack and do the post work for node j.  This also pops p
00176        * from the Pstack. */
00177       jhead-- ;
00178 
00179       /* -------------------------------------------------------------- */
00180       /* postwork at node j */
00181       /* -------------------------------------------------------------- */
00182 
00183       /* determine if node j is the head of a component */
00184       if (Low [j] == Time [j])
00185       {
00186     /* pop all nodes in this SCC from Cstack */
00187     while (TRUE)
00188     {
00189         ASSERT (chead >= 0) ; /* stack not empty (j in it) */
00190         i = Cstack [chead--] ;  /* pop a node from the Cstack */
00191         ASSERT (i >= 0) ;
00192         ASSERT (Flag [i] == UNASSIGNED) ;
00193         Flag [i] = nblocks ;  /* assign i to current block */
00194         if (i == j) break ;   /* current block ends at j */
00195     }
00196     nblocks++ ; /* one more block has been found */
00197       }
00198       /* update Low [parent], if the parent exists */
00199       if (jhead >= 0)
00200       {
00201     parent = Jstack [jhead] ;
00202     Low [parent] = MIN (Low [parent], Low [j]) ;
00203       }
00204   }
00205     }
00206 
00207     /* ---------------------------------------------------------------------- */
00208     /* cleanup: update timestamp and nblocks */
00209     /* ---------------------------------------------------------------------- */
00210 
00211     *p_timestamp = timestamp ;
00212     *p_nblocks   = nblocks ;
00213 }
00214 
00215 #else
00216 
00217 /* ========================================================================== */
00218 /* === dfs: recursive version (only for illustration) ======================= */
00219 /* ========================================================================== */
00220 
00221 /* The following is a recursive version of dfs, which computes identical results
00222  * as the non-recursive dfs.  It is included here because it is easier to read.
00223  * Compare the comments in the code below with the identical comments in the
00224  * non-recursive code above, and that will help you see the correlation between
00225  * the two routines.
00226  *
00227  * This routine can cause stack overflow, and is thus not recommended for heavy
00228  * usage, particularly for large matrices.  To help in delaying stack overflow,
00229  * global variables are used, reducing the amount of information each call to
00230  * dfs places on the call/return stack (the integers i, j, p, parent, and the
00231  * return address).  Note that this means the recursive code is not thread-safe.
00232  * To try this version, compile the code with -DRECURSIVE or include the
00233  * following line at the top of this file:
00234 
00235 #define RECURSIVE
00236 
00237  */
00238 
00239 static Int  /* for recursive illustration only, not for production use */
00240     chead, timestamp, nblocks, n, *Ap, *Ai, *Flag, *Cstack, *Time, *Low,
00241     *P, *R, *Q ;
00242 
00243 static void amesos_dfs
00244 (
00245     Int parent,   /* came from parent node */
00246     Int j   /* at node j in the DFS */
00247 )
00248 {
00249     Int p ;     /* current index into the adj. list for node j */
00250     Int i ;     /* edge (j,i) considered; i can be next node to traverse */
00251     Int jj ;      /* column j of A*Q is column jj of the input matrix A */
00252 
00253     /* ---------------------------------------------------------------------- */
00254     /* prework at node j */
00255     /* ---------------------------------------------------------------------- */
00256 
00257     /* node j is being visited for the first time */
00258     Cstack [++chead] = j ;      /* push j onto the stack */
00259     timestamp++ ;       /* get a timestamp */
00260     Time [j] = timestamp ;      /* give the timestamp to node j */
00261     Low [j] = timestamp ;
00262     Flag [j] = UNASSIGNED ;     /* flag node j as visited */
00263 
00264     /* ---------------------------------------------------------------------- */
00265     /* DFS rooted at node j */
00266     /* ---------------------------------------------------------------------- */
00267 
00268     /* determine which column jj of the A is column j of A*Q */
00269     jj = (Q == (Int *) NULL) ? (j) : (BTF_UNFLIP (Q [j])) ;
00270     for (p = Ap [jj] ; p < Ap [jj+1] ; p++)
00271     {
00272   i = Ai [p] ;    /* examine the edge from node j to node i */
00273   if (Flag [i] == UNVISITED)
00274   {
00275       /* Node i has not been visited - start a DFS at node i. */
00276       amesos_dfs (j, i) ;
00277   }
00278   else if (Flag [i] == UNASSIGNED)
00279   {
00280       /* Node i has been visited, but still unassigned to a block
00281        * this is a back or cross edge if Time [i] < Time [j].
00282        * Note that i might equal j, in which case this code does
00283        * nothing. */
00284       Low [j] = MIN (Low [j], Time [i]) ;
00285   }
00286     }
00287 
00288     /* ---------------------------------------------------------------------- */
00289     /* postwork at node j */
00290     /* ---------------------------------------------------------------------- */
00291 
00292     /* determine if node j is the head of a component */
00293     if (Low [j] == Time [j])
00294     {
00295   /* pop all nodes in this strongly connected component from Cstack */
00296   while (TRUE)
00297   {
00298       i = Cstack [chead--] ;  /* pop a node from the Cstack */
00299       Flag [i] = nblocks ;  /* assign node i to current block */
00300       if (i == j) break ;   /* current block ends at node j */
00301   }
00302   nblocks++ ; /* one more block has been found */
00303     }
00304     /* update Low [parent] */
00305     if (parent != EMPTY)
00306     {
00307   /* Note that this could be done with Low[j] = MIN(Low[j],Low[i]) just
00308    * after the dfs (j,i) statement above, and then parent would not have
00309    * to be an input argument.  Putting it here places all the postwork
00310    * for node j in one place, thus making the non-recursive DFS easier. */
00311   Low [parent] = MIN (Low [parent], Low [j]) ;
00312     }
00313 }
00314 
00315 #endif
00316 
00317 /* ========================================================================== */
00318 /* === btf_strongcomp ======================================================= */
00319 /* ========================================================================== */
00320 
00321 #ifndef RECURSIVE
00322 
00323 Int BTF(strongcomp) /* return # of strongly connected components */
00324 (
00325     /* input, not modified: */
00326     Int n,      /* A is n-by-n in compressed column form */
00327     Int Ap [ ],     /* size n+1 */
00328     Int Ai [ ],     /* size nz = Ap [n] */
00329 
00330     /* optional input, modified (if present) on output: */
00331     Int Q [ ],      /* size n, input column permutation.  The permutation Q can
00332          * include a flag which indicates an unmatched row.
00333          * jold = BTF_UNFLIP (Q [jnew]) is the permutation;
00334          * this function ingnores these flags.  On output, it is
00335          * modified according to the permutation P. */
00336 
00337     /* output, not defined on input: */
00338     Int P [ ],      /* size n.  P [k] = j if row and column j are kth row/col
00339          * in permuted matrix. */
00340     Int R [ ],      /* size n+1.  kth block is in rows/cols R[k] ... R[k+1]-1
00341          * of the permuted matrix. */
00342 
00343     /* workspace, not defined on input or output: */
00344     Int Work [ ]    /* size 4n */
00345 )
00346 
00347 #else
00348 
00349 Int BTF(strongcomp) /* recursive version - same as above except for Work size */
00350 (
00351     Int n_in,
00352     Int Ap_in [ ],
00353     Int Ai_in [ ],
00354     Int Q_in [ ],
00355     Int P_in [ ],
00356     Int R_in [ ],
00357     Int Work [ ]    /* size 2n */
00358 )
00359 
00360 #endif
00361 
00362 {
00363     Int j, k, b ;
00364 
00365 #ifndef RECURSIVE
00366     Int timestamp, nblocks, *Flag, *Cstack, *Time, *Low, *Jstack, *Pstack ;
00367 #else
00368     n = n_in ;
00369     Ap = Ap_in ;
00370     Ai = Ai_in ;
00371     Q = Q_in ;
00372     P = P_in ;
00373     R = R_in ;
00374     chead = EMPTY ;
00375 #endif
00376 
00377     /* ---------------------------------------------------------------------- */
00378     /* get and initialize workspace */
00379     /* ---------------------------------------------------------------------- */
00380 
00381     /* timestamp is incremented each time a new node is visited.
00382      *
00383      * Time [j] is the timestamp given to node j.
00384      *
00385      * Low [j] is the lowest timestamp of any node reachable from j via either
00386      * a path to any descendent of j in the DFS tree, or via a single edge to
00387      * an either an ancestor (a back edge) or another node that's neither an
00388      * ancestor nor a descendant (a cross edge).  If Low [j] is equal to
00389      * the timestamp of node j (Time [j]), then node j is the "head" of a
00390      * strongly connected component (SCC).  That is, it is the first node
00391      * visited in its strongly connected component, and the DFS subtree rooted
00392      * at node j spans all the nodes of the strongly connected component.
00393      *
00394      * The term "block" and "component" are used interchangebly in this code;
00395      * "block" being a matrix term and "component" being a graph term for the
00396      * same thing.
00397      *
00398      * When a node is visited, it is placed on the Cstack (for "component"
00399      * stack).  When node j is found to be an SCC head, all the nodes from the
00400      * top of the stack to node j itself form the nodes in the SCC.  This Cstack
00401      * is used for both the recursive and non-recursive versions.
00402      */
00403 
00404     Time   = Work ; Work += n ;
00405     Flag   = Work ; Work += n ;
00406     Low    = P ;    /* use output array P as workspace for Low */
00407     Cstack = R ;    /* use output array R as workspace for Cstack */
00408 
00409 #ifndef RECURSIVE
00410     /* stack for non-recursive dfs */
00411     Jstack = Work ; Work += n ;     /* stack for j */
00412     Pstack = Work ;       /* stack for p */
00413 #endif
00414 
00415     for (j = 0 ; j < n ; j++)
00416     {
00417   Flag [j] = UNVISITED ;
00418   Low [j] = EMPTY ;
00419   Time [j] = EMPTY ;
00420 #ifndef NDEBUG
00421   Cstack [j] = EMPTY ;
00422 #ifndef RECURSIVE
00423   Jstack [j] = EMPTY ;
00424   Pstack [j] = EMPTY ;
00425 #endif
00426 #endif
00427     }
00428 
00429     timestamp = 0 ; /* each node given a timestamp when it is visited */
00430     nblocks = 0 ; /* number of blocks found so far */
00431 
00432     /* ---------------------------------------------------------------------- */
00433     /* find the connected components via a depth-first-search */
00434     /* ---------------------------------------------------------------------- */
00435 
00436     for (j = 0 ; j < n ; j++)
00437     {
00438   /* node j is unvisited or assigned to a block. Cstack is empty. */
00439   ASSERT (Flag [j] == UNVISITED || (Flag [j] >= 0 && Flag [j] < nblocks));
00440   if (Flag [j] == UNVISITED)
00441   {
00442 #ifndef RECURSIVE
00443       /* non-recursive dfs (default) */
00444       amesos_dfs (j, Ap, Ai, Q, Time, Flag, Low, &nblocks, &timestamp,
00445         Cstack, Jstack, Pstack) ;
00446 #else
00447       /* recursive dfs (for illustration only) */
00448       ASSERT (chead == EMPTY) ;
00449       amesos_dfs (EMPTY, j) ;
00450       ASSERT (chead == EMPTY) ;
00451 #endif
00452   }
00453     }
00454     ASSERT (timestamp == n) ;
00455 
00456     /* ---------------------------------------------------------------------- */
00457     /* construct the block boundary array, R */
00458     /* ---------------------------------------------------------------------- */
00459 
00460     for (b = 0 ; b < nblocks ; b++)
00461     {
00462   R [b] = 0 ;
00463     }
00464     for (j = 0 ; j < n ; j++)
00465     {
00466   /* node j has been assigned to block b = Flag [j] */
00467   ASSERT (Time [j] > 0 && Time [j] <= n) ;
00468   ASSERT (Low [j] > 0 && Low [j] <= n) ;
00469   ASSERT (Flag [j] >= 0 && Flag [j] < nblocks) ;
00470   R [Flag [j]]++ ;
00471     }
00472     /* R [b] is now the number of nodes in block b.  Compute cumulative sum
00473      * of R, using Time [0 ... nblocks-1] as workspace. */
00474     Time [0] = 0 ;
00475     for (b = 1 ; b < nblocks ; b++)
00476     {
00477   Time [b] = Time [b-1] + R [b-1] ;
00478     }
00479     for (b = 0 ; b < nblocks ; b++)
00480     {
00481   R [b] = Time [b] ;
00482     }
00483     R [nblocks] = n ;
00484 
00485     /* ---------------------------------------------------------------------- */
00486     /* construct the permutation, preserving the natural order */
00487     /* ---------------------------------------------------------------------- */
00488 
00489 #ifndef NDEBUG
00490     for (k = 0 ; k < n ; k++)
00491     {
00492   P [k] = EMPTY ;
00493     }
00494 #endif
00495 
00496     for (j = 0 ; j < n ; j++)
00497     {
00498   /* place column j in the permutation */
00499   P [Time [Flag [j]]++] = j ;
00500     }
00501 
00502 #ifndef NDEBUG
00503     for (k = 0 ; k < n ; k++)
00504     {
00505   ASSERT (P [k] != EMPTY) ;
00506     }
00507 #endif
00508 
00509     /* Now block b consists of the nodes k1 to k2-1 in the permuted matrix,
00510      * where k1 = R [b] and k2 = R [b+1].  Row and column j of the original
00511      * matrix becomes row and column P [k] of the permuted matrix.  The set of
00512      * of rows/columns (nodes) in block b is given by P [k1 ... k2-1], and this
00513      * set is sorted in ascending order.  Thus, if the matrix consists of just
00514      * one block, P is the identity permutation. */
00515 
00516     /* ---------------------------------------------------------------------- */
00517     /* if Q is present on input, set Q = Q*P' */
00518     /* ---------------------------------------------------------------------- */
00519 
00520     if (Q != (Int *) NULL)
00521     {
00522   /* We found a symmetric permutation P for the matrix A*Q.  The overall
00523    * permutation is thus P*(A*Q)*P'.  Set Q=Q*P' so that the final
00524    * permutation is P*A*Q.  Use Time as workspace.  Note that this
00525    * preserves the negative values of Q if the matrix is structurally
00526    * singular. */
00527   for (k = 0 ; k < n ; k++)
00528   {
00529       Time [k] = Q [P [k]] ;
00530   }
00531   for (k = 0 ; k < n ; k++)
00532   {
00533       Q [k] = Time [k] ;
00534   }
00535     }
00536 
00537     /* ---------------------------------------------------------------------- */
00538     /* how to traverse the permuted matrix */
00539     /* ---------------------------------------------------------------------- */
00540 
00541     /* If Q is not present, the following code can be used to traverse the
00542      * permuted matrix P*A*P'
00543      *
00544      *      // compute the inverse of P
00545      *      for (knew = 0 ; knew < n ; knew++)
00546      *      {
00547      *    // row and column kold in the old matrix is row/column knew
00548      *    // in the permuted matrix P*A*P'
00549      *    kold = P [knew] ;
00550      *    Pinv [kold] = knew ;
00551      *      }
00552      *      for (b = 0 ; b < nblocks ; b++)
00553      *      {
00554      *    // traverse block b of the permuted matrix P*A*P'
00555      *    k1 = R [b] ;
00556      *    k2 = R [b+1] ;
00557      *    nk = k2 - k1 ;
00558      *    for (jnew = k1 ; jnew < k2 ; jnew++)
00559      *    {
00560      *        jold = P [jnew] ;
00561      *        for (p = Ap [jold] ; p < Ap [jold+1] ; p++)
00562      *        {
00563      *      iold = Ai [p] ;
00564      *      inew = Pinv [iold] ;
00565      *      // Entry in the old matrix is A (iold, jold), and its
00566      *      // position in the new matrix P*A*P' is (inew, jnew).
00567      *      // Let B be the bth diagonal block of the permuted
00568      *      // matrix.  If inew >= k1, then this entry is in row/
00569      *      // column (inew-k1, jnew-k1) of the nk-by-nk matrix B.
00570      *      // Otherwise, the entry is in the upper block triangular
00571      *      // part, not in any diagonal block.
00572      *        }
00573      *    }
00574      *      }
00575      *
00576      * If Q is present replace the above statement
00577      *    jold = P [jnew] ;
00578      * with
00579      *    jold = Q [jnew] ;
00580      * or
00581      *    jold = BTF_UNFLIP (Q [jnew]) ;
00582      *
00583      * then entry A (iold,jold) in the old (unpermuted) matrix is at (inew,jnew)
00584      * in the permuted matrix P*A*Q.  Everything else remains the same as the
00585      * above (simply replace P*A*P' with P*A*Q in the above comments).
00586      */
00587 
00588     /* ---------------------------------------------------------------------- */
00589     /* return # of blocks / # of strongly connected components */
00590     /* ---------------------------------------------------------------------- */
00591 
00592     return (nblocks) ;
00593 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines