/* ====================================================================== */
/*! \fn void trans(graphe * g, int x, boolean * Z)
    \param g (input): a graph
    \param x (input): a vertex of g
    \param Z (sortie): a subset of vertices of G (a Boolean array)
    \brief returns the transitive closure Z of the singleton {x} in g (as a Boolean array)
    \warning Z must be corectly allocated before the calls to trans (no verification is made)
*/
void trans(graphe * g, int x, boolean * Z)
/* ====================================================================== */
#undef F_NAME
#define F_NAME "CompFortConnexe"
{

  Lifo *X;    /* liste temporaire gérée en pile (Last In, First Out) */
  int y, z, n;
  pcell p;

  n = g->nsom;
  X = CreeLifoVide(n);  

  for (y = 0; y < n; y++) Z[y] = FALSE; 

  LifoPush(X, x);
  Z[x] = TRUE;
  while (!LifoVide(X))
  {
    y = LifoPop(X);
    for (p = g->gamma[y]; p != NULL; p = p->next)
    { /* for any successor z of y */
      z = p->som;
      if (!Z[z]) 
      {
        Z[z] = TRUE;
        LifoPush(X, z);
      }
    } // for p
  } // while (!LifoVide(T))
    
  LifoTermine(X);
} /* CompFortConnexe() */


/* ====================================================================== */
/*! \fn void scc(graphe * g, graphe * g1, int x, boolean * Cx)
    \param g (input): a graph
    \param g_1 (input): the symmetric of g
    \param x (input): a vertex of g
    \param Cx (sortie): a subset of the vertices of g (represented as a Boolean array) 
    \brief returns that is the strongly connected component Cx of g containing x (as a Boolean array)
    \warning Cx must be corectly allocated before the calls to scc (no verification is made)
*/
void scc(graphe * g, graphe *g_1, int x, boolean * Z){
  
  boolean * X;
  boolean * Y;
  int y, n;
  
  n = g->nsom;
  
  X = EnsembleVide(n);
  Y = EnsembleVide(n);

  trans(g, x, X);
  trans(g_1, x, Y);

  /* Set Z  to the intersection of X and Y */
  for (y = 0; y < n; y++) Z[y] = (X[y] && Y[y]);
  
  free(X);
  free(Y);
}