// File OrdinamentoTopologico.cpp
// Calcola l'ordinamento topologico du un grafo aciclico
// se il grafo contiene cicli a questi non viene assegnato alun ordine

#include <iostream.h>
#include "Grafo.h"
#include "Coda.h"

int* OrdinamentoTopologico(Grafo& g)
{
  //calcolo dell'indegree (num archi entranti) di ogni nodo;
  int* indegree = new int[g.NumNodi()];
  for (int i = 0; i < g.NumNodi(); i++)
    indegree[i] = 0;
  for (int i = 0; i < g.NumNodi(); i++) {
      Iteratore* itr = g.Successori(i);
      while (itr->HasNext()) {
        int j = itr->Next();
        indegree[j] = indegree[j] + 1;
      }
  }

  //calcolo dell'ordine topologico
  int* ordtopo = new int[g.NumNodi()];
  for (int i = 0; i < g.NumNodi(); i++)
    ordtopo[i] = -1;
  int n_ot = 0;
  Coda<int> c; //oppure Pila
  for (int i = 0; i < g.NumNodi(); i++)
    if (indegree[i] == 0) c.InCoda(i);

  while (!c.EstVuota()) {
    int i = c.Primo(); c.OutCoda();
    ordtopo[i] = n_ot;
    n_ot++;
    Iteratore* itr = g.Successori(i);
    while (itr->HasNext()) {
      int j = itr->Next();
      indegree[j] = indegree[j] - 1;
      if (indegree[j] == 0) c.InCoda(j);
    }
  }
  delete [] indegree;
  return ordtopo;
}