/*******************************************************************************
+
+  LEDA 3.5
+
+  _transclosure.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/


//------------------------------------------------------------------------------
// Transitive Closure
//                                                                              
// S. N"aher (1989)
//------------------------------------------------------------------------------


#include <LEDA/graph_alg.h>


static void acyclic_transitive_closure(graph& G)
{ // computes transitive closure of acyclic graph G

node v,w;

int i,j,k,h;
int n = G.number_of_nodes();

TOPSORT1(G); 

node_array<int> marked(G);
node_array<int> top_ord(G);   // topologic order
node_array<int> chain(G);     // chain[v] = i  iff  v in C[i]

node_list* C = new node_list[n+1];  // chains C[0], C[1], ...

node*      N = new node[n];         // N[i] = i-th node in topological order

int**      reach = new int*[n];     // reach[h][i] = min { j ; N[j] in C[h] and
                                    // there is a path from N[i] to N[j] }


for(i=0; i<n; i++) reach[i] = new int[n];

i=0;
forall_nodes(v,G) { marked[v]=1; top_ord[v] = i; N[i]=v; i++; }

// compute chain decomposition C[0], C[1], ..., C[k]

k=0;
forall_nodes(v,G) 
 { node v0 = v;
   if (marked[v0])
    {  C[k].append(v0);  
       chain[v0]=k;
       while (v0 != nil)
       { node u = nil;
         forall_adj_nodes(w,v0) 
           if (marked[w]) 
           {  u = w;
              break; 
            }

         if (u != nil) 
         { marked[u]=0;
           chain[u]=k;
           C[k].append(u);
          }
         v0=u;
        }
       k++;
    }
  }
k--;


for(h=0; h<n; h++)
  for(i=0; i<n; i++)
    reach[h][i] = n+1;

Forall_nodes(v,G)       //decreasing order
{ i=top_ord[v];
  forall_adj_nodes(w,v) //increasing order
  { j=top_ord[w];
    if (j <= reach[chain[w]][j])
     for(h=0; h<=k; h++)
       if (reach[h][j] < reach[h][i]) reach[h][i] = reach[h][j];
  }
  reach[chain[v]][i] = i;
}


G.del_all_edges();

forall_nodes(v,G)
  for(i=0; i<=k; i++)
    { j = reach[i][top_ord[v]];
      if ( j < n+1 )
        for(w = N[j]; w != nil; w = C[i].succ(w)) G.new_edge(v,w);
     }


for(i=0; i<=k; i++) C[i].clear();
delete[] C;

for(i=0; i<n; i++) delete reach[i];
delete reach;

delete N;

}


graph TRANSITIVE_CLOSURE(const graph& G0)
{
  node v,w;
  edge e;
  int i,j;

  graph G = G0;

  node_array<int> compnum(G);
  int k = STRONG_COMPONENTS(G,compnum);

/* reduce graph G to graph G1 = (V',E') 
   with V' = { V[0],V[1],...,V[k] } = set of scc's of G
   and (V[i],V[j]) in E' iff there is an edge from V[i] to V[j] in G

   G1.inf(V[i]) = set of nodes v in G with v in scc i (i.e. compum[v] = i)
*/

  GRAPH<list<node>*,int> G1;

  node*  V = new node[k];

  for(j=0; j < k; j++) V[j] = G1.new_node(new list<node>);

  forall_nodes(v,G) 
  { int i = compnum[v];
    G1[V[i]]->append(v);
   }
  
  forall_edges(e,G)
  { i = compnum[source(e)];
    j = compnum[target(e)];
    if (i!=j) G1.new_edge(V[i],V[j]);
   }

  Make_Simple(G1);  // eliminate parallel edges
  
  // compute transitive closure of acyclic graph G1

  acyclic_transitive_closure(G1);

  G.del_all_edges();

  forall_nodes(v,G1)
  { list<node>* plv = G1[v];
    forall_adj_nodes(w,v)
    { list<node>* plw = G1[w];
      list_item x,y;
      forall_items(x,*plv)
         forall_items(y,*plw) 
            G.new_edge(plv->inf(x),plw->inf(y));
     }
   }

   forall_nodes(v,G1) delete G1[v];
  
   delete V;

   return G;
}

