home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _trans_a.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.7 KB  |  131 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _trans_acyclic.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/graph_alg.h>
  18.  
  19.  
  20. typedef list(node)* nodelist_ptr;
  21.  
  22. declare(node_array,list_item)
  23.  
  24. /*
  25. #include <LEDA/array.h>
  26.  
  27. declare(array,nodelist_ptr)
  28. declare(array,node)
  29. declare(array2,int)
  30. */
  31.  
  32.  
  33. void acyclic_transitive_closure(graph& G)
  34. { // computes transitive closure of acyclic graph G
  35.  
  36. edgelist E1;
  37. node v,w;
  38.  
  39. int i,j,k,h;
  40. int n = G.number_of_nodes();
  41.  
  42. TOPSORT1(G); 
  43.  
  44. node_array(bool)      marked(G);
  45. node_array(int)       top_ord(G);      // topologic order
  46.  
  47. // array(nodelist_ptr)   C(n+1);          // chains C[1], C[2], ...
  48.  
  49. nodelist_ptr*   C = new nodelist_ptr[n+1];
  50.  
  51. node_array(int)       chain(G);        // chain[v] = i  iff  v in C[i]
  52. node_array(list_item) chain_loc(G);    // chain_loc[v]   
  53.                                        //  = location of v in its chain
  54.  
  55. /*
  56. array(node)      N(n);            // N[i]     = node i (in topological order)
  57. array2(int)      reach(n,n);      // reach[h][i] = min { j ; N[j] in C[h] and
  58.                                   // there is a path from N[i] to N[j] }
  59. */
  60.  
  61. node* N     = new node[n];
  62.  
  63. int** reach = new int*[n];
  64. for(i=0; i<n; i++) reach[i] = new int[n];
  65.  
  66.                      
  67. i=0;
  68. forall_nodes(v,G) { marked[v]=1; top_ord[v] = i; N[i]=v; i++; }
  69.  
  70. //Kettenzerlegung C[0], C[1], ..., C[k]
  71.  
  72. k=0;
  73. C[0] = new list(node);
  74. forall_nodes(v,G) 
  75.  { node v0 = v;
  76.    if (marked[v0])
  77.     {  chain_loc[v0]=C[k]->append(v0);  
  78.        chain[v0]=k;
  79.        while (v0)
  80.        { forall_adj_nodes(w,v0) if (marked[w]) break; 
  81.          if (w) { marked[w]=0;
  82.                   chain[w]=k;
  83.                   chain_loc[w]=C[k]->append(w);
  84.                  }
  85.          v0=w;
  86.        }
  87.        k++;
  88.        C[k] = new list(node);
  89.     }
  90.   }
  91. k--;
  92.  
  93.  
  94. for(h=0; h<n; h++)
  95.   for(i=0; i<n; i++)
  96.     reach[h][i] = n+1;
  97.  
  98. Forall_nodes(v,G)       //decreasing order
  99. { i=top_ord[v];
  100.   forall_adj_nodes(w,v) //increasing order
  101.   { j=top_ord[w];
  102.     if (j <= reach[chain[w]][j])
  103.      for(h=0; h<=k; h++)
  104.        if (reach[h][j] < reach[h][i]) reach[h][i] = reach[h][j];
  105.   }
  106.   reach[chain[v]][i] = i;
  107. }
  108.  
  109.  
  110. G.del_all_edges();
  111.  
  112. forall_nodes(v,G)
  113. { for(i=0; i<=k; i++)
  114.     if ((j=reach[i][top_ord[v]]) < n+1)
  115.     { C[i]->set_iterator(C[i]->pred(chain_loc[N[j]]));
  116.       while (C[i]->next_element(w)) G.new_edge(v,w);
  117.      }
  118.  }
  119.  
  120. for(i=0; i<=k; i++) C[i]->clear();
  121.  
  122. for(i=0; i<n; i++) delete reach[i];
  123.  
  124. delete reach;
  125. delete C;
  126. delete N;
  127.  
  128. }
  129.  
  130.  
  131.