home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _transcl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.1 KB  |  98 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _transclosure.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. /*******************************************************************************
  18. *                                                                              *
  19. *  TRANSITIVE_CLOSURE (transitive closure)                                     *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. /*
  28. #include <LEDA/array.h>
  29.  
  30. declare(array,node)
  31. */
  32.  
  33. typedef list(node)* nodelist_ptr;
  34.  
  35. declare2(GRAPH,nodelist_ptr,int)
  36.  
  37.  
  38. graph TRANSITIVE_CLOSURE(const graph& G0)
  39. {
  40.   node v,w;
  41.   edge e;
  42.   int i,j;
  43.  
  44.   graph G = G0;
  45.  
  46.   node_array(int) compnum(G);
  47.   int k = STRONG_COMPONENTS(G,compnum);
  48.  
  49. /* reduce graph G to graph G1 = (V',E') 
  50.    with V' = { V[0],V[1],...,V[k] } = set of scc's of G
  51.    and (V[i],V[j]) in E' iff there is an edge from V[i] to V[j] in G
  52.  
  53.    G1.inf(V[i]) = set of nodes v in G with v in scc i (i.e. compum[v] = i)
  54. */
  55.  
  56.   GRAPH(nodelist_ptr,int) G1;
  57.  
  58.   // array(node) V(k);
  59.  
  60.   node*  V = new node[k];
  61.  
  62.   loop(j,0,k-1) V[j] = G1.new_node(new list(node));
  63.  
  64.   forall_nodes(v,G) G1.inf(V[compnum[v]])->append(v);
  65.   
  66.   forall_edges(e,G)
  67.   { i = compnum[source(e)];
  68.     j = compnum[target(e)];
  69.     if (i!=j) G1.new_edge(V[i],V[j]);
  70.    }
  71.  
  72.   eliminate_parallel_edges(G1);
  73.   
  74.   // compute transitive closure of acyclic graph G1
  75.  
  76.   acyclic_transitive_closure(G1);
  77.  
  78.   edgelist el = G.all_edges();
  79.   forall(e,el) G.del_edge(e);
  80.   
  81.   node x,y;
  82.  
  83.   forall_nodes(v,G1)
  84.   { list(node) nl1 = *(G1[v]);
  85.     forall_adj_nodes(w,v)
  86.      { forall(x,nl1)
  87.          forall(y,*(G1[w])) G.new_edge(x,y);
  88.       }
  89.    }
  90.   
  91.    forall_nodes(v,G1) G1[v]->clear();
  92.   
  93.    delete V;
  94.  
  95.    return G;
  96. }
  97.  
  98.