/*******************************************************************************
+
+  LEDA 3.5
+
+  _topsort.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.
+ 
*******************************************************************************/


//------------------------------------------------------------------------------
// Topological Sorting 
//                                                                              
// S. N"aher (1989)
//------------------------------------------------------------------------------



#include <LEDA/graph_alg.h>


bool TOPSORT(const graph& G, node_array<int>& ord)
{ 
  node_array<int> INDEG(G,0);
  node_list ZEROINDEG;

  int count=0;
  node v,w;

  forall_nodes(v,G) if ((INDEG[v]=indeg(v))==0) ZEROINDEG.append(v); 

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



// 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;
    }

  else return false;
  
}
     

