(* Topological sort, reverse topological sort.
   Copyright (C) 2003 Jean Goubault-Larrecq and LSV, CNRS UMR 8643 & ENS Cachan.

   This file is part of h1.

   h1 is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   h1 is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with h1; see the file COPYING.  If not, write to
   the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*)

open "topsort_h";

fun topsort (G, root) =
    let val nr = ref 0
	val numbering = ref {}
	fun ts n =
	    if n inset !numbering
		then ()
	    else (inc nr;
		  numbering := !numbering ++ {n => !nr};
		  iterate
		    ts suc
		  | suc in set if n inset G then ?G n else {}
		  end)
    in
	ts root;
	!numbering
    end;

fun revtopsort (G, root) =
    let val nr = ref 0
	val marked = ref {}
	val rev_numbering = ref {}
	fun rev_ts n =
	    if n inset !marked
		then ()
	    else (marked := !marked U {n};
		  iterate
		    rev_ts suc
		  | suc in set if n inset G then ?G n else {}
		  end;
		  inc nr;
		  rev_numbering := !rev_numbering ++ {n => !nr})
    in
	rev_ts root;
	!rev_numbering
    end;
