#include <LEDA/graph/graph.h>
#include <LEDA/core/queue.h>


bool TOPSORT(const graph& G, node_array<int>& ord)
{ 
  int n = G.number_of_nodes();

  node_array<int> INDEG(G,0);

  queue<node> ZEROINDEG(n);

  int count=0;

  node v;
  forall_nodes(v,G) 
  { int d = G.indeg(v); 
    INDEG[v] = d;
    if (d == 0) ZEROINDEG.append(v); 
   }

  while (!ZEROINDEG.empty())
   { node u = ZEROINDEG.pop();
     ord[v] = ++count;
     node w;
     forall_adj_nodes(w,u) 
        if (--INDEG[w]==0) ZEROINDEG.append(w);
    }
  
  return count == n; 
}
     
     



// TOPSORT1 rearrange nodes and edges using bucket sort

bool TOPSORT1(graph& G)
{ 
  if (G.number_of_nodes()==0 || G.number_of_edges()==0) return true;

  node_array<int> node_ord(G);
  edge_array<int> edge_ord(G);

  if (TOPSORT(G,node_ord))
   { edge e;
     forall_edges(e,G) edge_ord[e] = node_ord[target(e)];
     G.bucket_sort_nodes(node_ord);
     G.bucket_sort_edges(edge_ord);
     return true;
    }

  return false;
}
 
LEDA_END_NAMESPACE