home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 5.ddi / MWHC.005 / J < prev    next >
Encoding:
Text File  |  1992-03-30  |  6.0 KB  |  246 lines
  1. /*
  2. This program analyzes a directed graph and "breaks" all loops in
  3. the graph.  The program marks a set of nodes in the graph such that
  4. if the ingoing edges to the nodes are deleted, the graph is acyclic.
  5. The technique is as follows:
  6.     For each strongly-connected component (SCC) of the graph,
  7.     mark the root (where the SCC was first entered).
  8.     This reduces the number of loop paths in the SCC,
  9.     breaking the SCC into a set of smaller SCCs.
  10.     Recursively find the SCCs of this reduced SCC, breaking
  11.     loops in the same way.    When finished, all loops in the original
  12.     SCC will be broken.  When each SCC is thus processed,
  13.     the graph will contain no loops.
  14. The algorithm was used as part of a scheme
  15. for generating ultra-fast LR parsers.
  16. It also is a good test for Pascal compilers.
  17.  
  18. The SCC algorithm was derived from one by Eve and Kurki-Suonio.
  19. See paper by DeRemer and Pennello in Oct. 1982 TOPLAS.
  20.  
  21. Author:  Tom Pennello of MetaWare Incorporated.
  22.  
  23. This version is in MetaWare High C.  The ()! syntax denotes a full
  24. function value -- the equivalent of the Pascal procedural parameter --
  25. that consists of the entry point AND the environment pointer.
  26.  
  27. I challenge any C programmer that feels up to it to re-program this in standard
  28. C.
  29. */
  30.  
  31. /* For this sample application, the node size is small. */
  32. /* The graph is represented in code.  See below     */
  33. #define Nullnode 0
  34. #define Maxnodes 100
  35. #define Maxnodesp1 101
  36. #define Firstnode 1
  37. #define Lastnode 8
  38.  
  39. #include <stdio.h>
  40.  
  41. typedef int Integer;
  42. typedef enum{False,True} Boolean;
  43.  
  44. typedef Integer /*Subrange!!:Nullnode..Maxnodesp1*/ Node;
  45. /* For translation into C we need to convert sets to arrays of booleans. */
  46. typedef Boolean Nodeset[Maxnodesp1+1];
  47. Nodeset Marked;
  48.  
  49. static void Eachscc(/* of relation R */
  50.       /* Pass in the relation on the nodes; yield each SCC found. */
  51.             void Eachnode(void Yield(Node)!)!,
  52.             void R(Node, void Yield(Node)!)!,
  53.             Boolean Yieldtrivialsccs, /* Yield SCCs of one node?         */
  54.             void Yield(Node Root,
  55.                    void Each(void Yield(Node)!)!)!)
  56.    {
  57. #  define Infinity Maxnodesp1
  58.    Integer /*Subrange!!:0..Maxnodesp1*/ N[Maxnodesp1+1];
  59.    Node Stack[Maxnodes+1];
  60.    Integer /*Subrange!!:0..Maxnodes*/ Sp;
  61.  
  62.    static void Search(Node V)
  63.       {
  64.       Boolean Vhaspathtoitself; Integer I,T;
  65.  
  66.       static void Eachmember(void Yield(Node)!)
  67.      {
  68.      Integer I;
  69.     /* yield each member of current SCC */
  70.      for (I = Sp; I >= T; I--)
  71.         Yield(Stack[I]);
  72.      } /*Eachmember*/
  73.       static void Body(Node W)
  74.      {
  75.      Search(W);
  76.      if (W == V)
  77.         Vhaspathtoitself = True;
  78.      if (N[W] < N[V])
  79.         N[V] = N[W];
  80.      } /*Body*/
  81.       if (N[V] == 0) {         /* stack the node */
  82.      Vhaspathtoitself = False;
  83.      Sp++;
  84.      Stack[Sp] = V; N[V] = Sp;
  85.      R(V,Body);
  86.      if (V == Stack[N[V]]) {/* V is root of an SCC */
  87.         T = N[V];
  88.         for (I = Sp; I >= T; I--)
  89.            N[Stack[I]] = Infinity;
  90.         if (Sp != T || /* single node; V R+ V ? */
  91.         Vhaspathtoitself && Yieldtrivialsccs)
  92.            Yield(V,Eachmember);
  93.         Sp = T-1;
  94.         }
  95.      }
  96.       } /*Search*/
  97.    static void Init(Node Q)
  98.       {
  99.       N[Q] = 0;
  100.       } /*Init*/
  101.    Eachnode(Init);
  102.    Sp = 0;
  103.    Eachnode(Search);
  104.    } /*Eachscc*/
  105.  
  106. /*
  107. The sample graph to be analyzed is as follows:
  108.  
  109.     1
  110.     V
  111.     2 <--- 3
  112.     |      A
  113.     V      |
  114.     +->4-->+
  115.     A  V   A
  116.     |  5   |
  117.     |  V   |
  118.     +<-6-->7-->+-->8-->+
  119.            A   V   A   V
  120.            +<--+   +<--+
  121.  
  122. Thus, there are eight nodes.
  123. Marking nodes 2, 4, 7, and 8 breaks all loops.
  124. */
  125.  
  126. static void Analyzegraph()
  127.    {
  128.    Integer Subsccs;
  129.    Integer Cnt;
  130.  
  131.    /* The graph is represented by these two procedures. */
  132.    static void Eachstate(void Yield(Node)!)
  133.       {
  134.       Node N;
  135.       for (N = Firstnode; N <= Lastnode; N++)
  136.      Yield(N);
  137.       } /*Eachstate*/
  138.    static void Successors(Node N, void Yield(Node)!)
  139.       {
  140.       switch (N) {
  141.      case 1:
  142.         Yield(2);
  143.         break;
  144.      case 2:
  145.         Yield(4);
  146.         break;
  147.      case 3:
  148.         Yield(2);
  149.         break;
  150.      case 4:
  151.         Yield(5);
  152.         break;
  153.      case 5:
  154.         Yield(6);
  155.         break;
  156.      case 6: {
  157.         Yield(7); Yield(4);
  158.         }
  159.         break;
  160.      case 7: {
  161.         Yield(7); Yield(3);
  162.         }
  163.         break;
  164.      case 8:
  165.         Yield(8);
  166.         break;
  167.      }
  168.       } /*Successors*/
  169.    static void P(Node Root, void Scc(void Yield(Node)!)!)
  170.       {
  171.       Nodeset Inscclessroot;
  172.       static void Successors2(Node N, void Yield(Node)!)
  173.      {
  174.      static void Body(Node N2)
  175.         {
  176.         if (Inscclessroot[N2])
  177.            Yield(N2);
  178.         } /*Body*/
  179.      Successors(N,Body);
  180.      } /*Successors2*/
  181.       static void Scclessroot(void Yield(Node)!)
  182.      {
  183.      static void Body(Node N) 
  184.         {
  185.         if (Inscclessroot[N])
  186.            Yield(N);
  187.         } /*Body*/
  188.      Scc(Body);
  189.      } /*Scclessroot*/
  190.       /* Break the SCC at the root, then recursively do leftover SCCs. */
  191.       /* We run EachSCC only on nodes & edges in SCC, less the root.    */
  192.       static void Body(Node N)
  193.      {
  194.      if (N != Root)
  195.         Inscclessroot[N] = True;
  196.      } /*Body*/
  197.       static void Receivescc(Node Root2, void Scc2(void (Node)!)!)
  198.      {
  199.      Subsccs++;
  200.      P(Root2,Scc2);
  201.      } /*Receivescc*/
  202.       static void P(Node N)
  203.      {
  204.      Inscclessroot[N] = False;
  205.      } /*P*/
  206.       Eachstate(P);
  207.       Scc(Body);
  208.       Marked[Root] = True;
  209.       printf("Marking node %d\n",Root);
  210.       Eachscc(Scclessroot,Successors2,True,Receivescc);
  211.       } /*P*/
  212.    static void Receivescc(Node Root, void Scc(void (Node)!)!)
  213.       {
  214.       static void Count(Node N)
  215.      {
  216.      Cnt++;
  217.      } /*Count*/
  218.       Subsccs = 0;
  219.       P(Root,Scc);
  220.       Cnt = 0; Scc(Count);
  221.       printf("SCC of %d nodes detected, having %d contained SCCs.\n",
  222.                  Cnt, Subsccs);
  223.       } /*Receivescc*/
  224.    static void Q(Node N)
  225.       {
  226.       Marked[N] = False;
  227.       } /*Q*/
  228.    Eachstate(Q);
  229.    Eachscc(Eachstate,Successors,True,Receivescc);
  230.    } /*Analyzegraph*/
  231.  
  232. void main() {
  233.    Analyzegraph();
  234.    }
  235. /*
  236. The correct output reads:
  237.  
  238. Marking node 2
  239. Marking node 7
  240. Marking node 6
  241. SCC of 6 nodes detected, having 2 contained SCCs.
  242. Marking node 8
  243. SCC of 1 nodes detected, having 0 contained SCCs.
  244.  
  245. */
  246.