(* $Header: /home/pauillac/formel1/fpottier/cvs/typo/topological.mli,v 1.1 2001/08/17 17:04:35 fpottier Exp $ *)

module type Graph = sig

  type node

  (* The client must allow associating an integer degree with every graph node. *)

  val get: node -> int
  val set: int -> node -> unit

  (* The client must allow enumerating all nodes. *)

  val iter: (node -> unit) -> unit

  (* The client must allow enumerating all successors of a given node. *)

  val successors: (node -> unit) -> node -> unit

end

(* Given an acyclic graph $G$, this functor provides functions which allow iterating over the graph in topological
   order. Each graph traversal has complexity $O(V+E)$, where $V$ is the number of vertices in the graph, and $E$ is
   the number of its edges. The graph must be acyclic; otherwise, [Cycle] will be raised at some point during every
   traversal. *)

module Sort (G : Graph) : sig

  exception Cycle
  
  val iter: (G.node -> unit) -> unit
  val fold: (G.node -> 'a -> 'a) -> 'a -> 'a

end